|
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
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
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
Linking options:
https://www.mathnet.ru/eng/ivm9050 https://www.mathnet.ru/eng/ivm/y2015/i11/p32
|
Statistics & downloads: |
Abstract page: | 148 | Full-text PDF : | 50 | References: | 33 | First page: | 6 |
|