Geodesic
Comparative complexity of quantum and classical OBDDs for total and partial functions
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 11 (2015), pp. 32-43 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{IVM_2015_11_a2,
     author = {A. F. Gainutdinova},
     title = {Comparative complexity of quantum and classical {OBDDs} for total and partial functions},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {32--43},
     year = {2015},
     number = {11},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2015_11_a2/}
}
TY  - JOUR
AU  - A. F. Gainutdinova
TI  - Comparative complexity of quantum and classical OBDDs for total and partial functions
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2015
SP  - 32
EP  - 43
IS  - 11
UR  - http://geodesic.mathdoc.fr/item/IVM_2015_11_a2/
LA  - ru
ID  - IVM_2015_11_a2
ER  - 
%0 Journal Article
%A A. F. Gainutdinova
%T Comparative complexity of quantum and classical OBDDs for total and partial functions
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2015
%P 32-43
%N 11
%U http://geodesic.mathdoc.fr/item/IVM_2015_11_a2/
%G ru
%F IVM_2015_11_a2
A. F. Gainutdinova. Comparative complexity of quantum and classical OBDDs for total and partial functions. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 11 (2015), pp. 32-43. http://geodesic.mathdoc.fr/item/IVM_2015_11_a2/

[1] Manin Yu. I., Vychislimoe i nevychislimoe, Sov. radio, M., 1980 | MR

[2] Feynman R., “Simulating physics with computers”, Intern. J. Theor. Phys., 21:6–7 (1982), 467–488 | DOI | MR

[3] Nilsen M., Chang I., Kvantovye vychisleniya i kvantovaya informatsiya, Mir, M., 2006

[4] Shor P., “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM J. Comput., 26:5 (1997), 1484–1509 | DOI | MR | Zbl

[5] Grover L., “A fast quantum mechanical algorithm for database search”, Proc. of 28th STOC (Philadelphia, PA, USA, 1996), ACM, New York, 1996, 212–219 | MR | Zbl

[6] Wegener I., Branching programs and binary decision diagrams, SIAM, 2000 | MR | Zbl

[7] Ablayev F., Gainutdinova A., Karpinski M., “On computational power of quantum branching programs”, Proc. of the 13th Intern. Symposium “Fundamentals of computation theory”, FCT (Riga, Latvia, 2001), Lecture Notes in Computer Science, 2138, Springer-Verlag, 2001, 59–70 | DOI | MR | Zbl

[8] Barrington D., “Vetvyaschiesya programmy ogranichennoi shiriny, imeyuschie polinomialnuyu slozhnost, raspoznayut v tochnosti yazyki iz $NC^1$”, Kiberneticheskii sbornik, 28, Mir, M., 1991, 94–113

[9] Nakanishi M., Hamaguchi K., Kashiwabara T., “Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction”, Proc. of the 6th Annual Intern. Conf. on Computing and Combinatorics COCOON'2000, Lecture Notes in Computer Science, 1858, Springer-Verlag, 2000, 467–476 | DOI | MR | Zbl

[10] Sauerhoff M., Sieling D., “Quantum branching programs and space-bounded nonuniform quantum complexity”, Theoret. Comput. Sci., 334:1–3 (2005), 177–225 ; arXiv: quant-ph/0403164 | DOI | MR | Zbl

[11] Gainutdinova A. F., “O sravnitelnoi slozhnosti kvantovykh i klassicheskikh binarnykh programm”, Diskr. matem., 14:3 (2002), 109–121 | DOI | MR | Zbl

[12] Ablayev F., Gainutdinova A., Karpinski M., Moore C., Pollette C., “On the computational power of probabilistic and quantum branching program”, Inform. and Comput., 203:2 (2005), 145–162 | DOI | MR | Zbl

[13] Sholomov L. A., Osnovy teorii diskretnykh logicheskikh i vychislitelnykh ustroistv, Nauka, M., 1980

[14] Ambainis A., Yakaryılmaz A., “Superiority of exact quantum automata for promise problems”, Inform. Process. Lett., 112:7 (2012), 289–291 | DOI | MR | Zbl

[15] Kemeny J. G., Snell J. L., Finite Markov Chains, Van Nostrand Company, inc., 1960 | MR | Zbl