Казанский (Приволжский) федеральный университет, КФУ
КАЗАНСКИЙ
ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
 
RSS Ins Вконтакте twitter facebook
VERY NARROW QUANTUM OBDDS AND WIDTH HIERARCHIES FOR CLASSICAL OBDDS
Форма представленияСтатьи в зарубежных журналах и сборниках
Год публикации2014
Языкрусский
  • Аблаев Фарид Мансурович, автор
  • Гайнутдинова Аида Фаритовна, автор
  • Хадиев Камиль Равилевич, автор
  • Библиографическое описание на языке оригинала Farid Ablayev, Aida Gainutdinova, Kamil Khadiev, Abuzer Yakaryılmaz, «Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs«, LNCS vol. 8614 pp. 53-64, 2014
    Аннотация In the paper we investigate a model for computing of Boolean functions ? Ordered Binary Decision Diagrams (OBDDs), which is a restricted version of Branching Programs. We present several results on the comparative complexity for several variants of OBDD models. We present some results on the comparative complexity of classical and quantum OBDDs. We consider a partial function depending on a parameter k such that for any k > 0 this function is computed by an exact quantum OBDD of width 2, but any classical OBDD (deterministic or stable bounded-error probabilistic) needs width 2 k + 1. We consider quantum and classical nondeterminism. We show that quantum nondeterminism can be more efficient than classical nondeterminism. In particular, an explicit function is presented which is computed by a quantum nondeterministic OBDD with constant width, but any classical nondeterministic OBDD for this function needs non-constant width. We also present new hierarchies on widths of determ. & nonde
    Ключевые слова quantum computation, OBDD, nondeterminism
    Название журнала Lecture Notes in Computer Science
    URL http://link.springer.com/chapter/10.1007/978-3-319-09704-6_6
    Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку https://repository.kpfu.ru/?p_id=84826

    Полная запись метаданных