Geodesic
On the relative complexity of quantum and classical branching programs
Diskretnaya Matematika, Tome 14 (2002) no. 3, pp. 109-121.

Voir la notice de l'article provenant de la source Math-Net.Ru

We give a definition of a quantum branching program. A well-known Boolean function $\operatorname{MOD}_p$ is considered. We prove that any deterministic branching program and any probabilistic ordered stable branching program which $(1/2+\varepsilon)$-compute the function $\operatorname{MOD}_p$ are of width no less than $p$. We construct a stable quantum branching program of width $O(\log p)$ which computes the function $\operatorname{MOD}_p$ with one-sided error $\varepsilon>0$. 
@article{DM_2002_14_3_a10,
     author = {A. F. Gainutdinova},
     title = {On the relative complexity of quantum and classical branching programs},
     journal = {Diskretnaya Matematika},
     pages = {109--121},
     publisher = {mathdoc},
     volume = {14},
     number = {3},
     year = {2002},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2002_14_3_a10/}
}
TY  - JOUR
AU  - A. F. Gainutdinova
TI  - On the relative complexity of quantum and classical branching programs
JO  - Diskretnaya Matematika
PY  - 2002
SP  - 109
EP  - 121
VL  - 14
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2002_14_3_a10/
LA  - ru
ID  - DM_2002_14_3_a10
ER  - 
%0 Journal Article
%A A. F. Gainutdinova
%T On the relative complexity of quantum and classical branching programs
%J Diskretnaya Matematika
%D 2002
%P 109-121
%V 14
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2002_14_3_a10/
%G ru
%F DM_2002_14_3_a10
A. F. Gainutdinova. On the relative complexity of quantum and classical branching programs. Diskretnaya Matematika, Tome 14 (2002) no. 3, pp. 109-121. http://geodesic.mathdoc.fr/item/DM_2002_14_3_a10/

[1] Barrington D., “Vetvyaschiesya programmy ogranichennoi shiriny, imeyuschie polinomialnuyu slozhnost, raspoznayut v tochnosti yazyki iz $NC^1$”, Kibern. sb., 28 (1991), 94–113

[2] Valiev V. A., Kokin A. A., Kvantovye kompyutery: nadezhdy i realnost, NIS, Izhevsk, 2001

[3] Kemeni D., Snell D., Konechnye tsepi Markova, Nauka, Moskva, 1970

[4] Kitaev A., Shen A., Vyalyi M., Klassicheskie i kvantovye vychisleniya, MTsNMO, Moskva, 1999

[5] Manin Yu. I., Vychislimoe i nevychislimoe, Sov. radio, Moskva, 1980 | MR

[6] Okolnishnikova E. A., “Nizhnie otsenki slozhnosti realizatsii kharakteristicheskikh funktsii dvoichnykh kodov binarnymi programmami”, Metody diskretnogo analiza v sinteze realizatsii bulevykh funktsii, 51 (1991), 61–83 | MR

[7] Ablayev F., Gainutdinova A., Karpinski M., “On computational power of quantum branching programs”, Lect. Notes Computer Sci., 2138, 2001, 59–70 | MR | Zbl

[8] Ablayev F., Karpinski M., “On the power of randomized branching programs”, Lect. Notes Computer Sci., 1099, 1996, 348–356 | MR | Zbl

[9] Ambainis A., Freivalds R., “1-way quantum finite automata: strengths, weaknesses and generalization”, 39th Annual Symp. Found. Computer Sci., 1998, 332–342

[10] Borodin A., Fischer M., Kirkpatrick D., Lynch N., Tompa M., “A time-space tradeoff for sorting on non-oblivious machines”, Proc. 20th Annual Symp. Found. Computer Sci., 1979, 319–327

[11] Brodsky A., Pippenger N., Characterization of 1-way quantum finite automata, http://www.lanl.gov/archive/quant-ph/9903014

[12] Feynman R., Intern. J. Theoretical Physics, 21, 1982

[13] Grover L., “A fast quantum mechanical algorithm for database search”, Proc. 28th STOC, 1996, 212–219 | MR | Zbl

[14] Gruska J., Quantum computing, McGraw–Hill, New York, 1999 | MR

[15] Kondacs A., Watrous J., “On the power of quantum finite state automata”, Proc. 38th Annual Symp. Found. Computer Sci., 1997, 66–75

[16] Moore C., Nilson M., Some notes on parallel quantum computing

[17] Nakanishi M., Hamaguchi K., Kashiwabara T., “Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction” (Proc. 6th Annual Intern. Conf. Computing and Combinatorics, COCOON'2000), Lect. Notes Computer Sci., 1858, 2000, 467–476 | MR | Zbl

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

[19] Wegener I., Branching programs and binary decision diagrams. Theory and applications, SIAM, Philadelphia, 2000 | MR

[20] Yao A., “Quantum circuit complexity”, Proc. 34th Annual Symp. Found. Computer Sci., 1993, 352–361 | MR