Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Izv. Vyssh. Uchebn. Zaved. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2015, Number 11, Pages 32–43 (Mi ivm9050)  

This article is cited in 13 scientific papers (total in 13 papers)

Comparative complexity of quantum and classical OBDDs for total and partial functions

A. F. Gainutdinova

Chair of Theoretical Cybernetics, Kazan (Volga Region) Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia
References:
Abstract: We consider a model of computation for discrete functions – Ordered Binary Decision Diagrams (OBDD). We investigate comparative complexity of quantum, deterministic, probabilistic and nondeterministic (quantum and classical) OBDDs for total and partial functions. The measure of complexity is a width of OBDD. It is known that for total functions bounded error quantum OBDDs can be exponentially more effective than deterministic and bounded error probabilistic OBDDs. We show that such quantum OBDDs also can be exponentially more effective than nondeterministic OBDDs (both quantum and classical). For partial functions the gap can be more significant. For partial function depending on parameter $k$ exact quantum OBDD has the width two. Deterministic and bounded error probabilistic OBDD for this function must have width exponentially depending on $k$.
Keywords: ordered binary decision diagrams, partial functions, quantum computation, nondeterminism, probabilistic OBDDs, complexity.
Received: 26.03.2014
English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2015, Volume 59, Issue 11, Pages 26–35
DOI: https://doi.org/10.3103/S1066369X15110031
Bibliographic databases:
Document Type: Article
UDC: 519.7
Language: Russian
Citation: A. F. Gainutdinova, “Comparative complexity of quantum and classical OBDDs for total and partial functions”, Izv. Vyssh. Uchebn. Zaved. Mat., 2015, no. 11, 32–43; Russian Math. (Iz. VUZ), 59:11 (2015), 26–35
Citation in format AMSBIB
\Bibitem{Gai15}
\by A.~F.~Gainutdinova
\paper Comparative complexity of quantum and classical OBDDs for total and partial functions
\jour Izv. Vyssh. Uchebn. Zaved. Mat.
\yr 2015
\issue 11
\pages 32--43
\mathnet{http://mi.mathnet.ru/ivm9050}
\transl
\jour Russian Math. (Iz. VUZ)
\yr 2015
\vol 59
\issue 11
\pages 26--35
\crossref{https://doi.org/10.3103/S1066369X15110031}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84945200566}
Linking options:
  • https://www.mathnet.ru/eng/ivm9050
  • https://www.mathnet.ru/eng/ivm/y2015/i11/p32
  • This publication is cited in the following 13 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Известия высших учебных заведений. Математика Russian Mathematics (Izvestiya VUZ. Matematika)
    Statistics & downloads:
    Abstract page:148
    Full-text PDF :50
    References:33
    First page:6
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024