Geodesic
On Complexity of Classical Simulation of Quantum Branching Programs
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 151 (2009) no. 2, pp. 7-15
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The paper considers syntactical quantum branching programs that compute Boolean functions with bounded error. Classical simulation technique is presented for such quantum programs and complexity of such simulation is estimated. The estimation of simulation complexity is shown to be close to optimal on the example of $\mathrm{MOD}_m$ function. Classical simulation technique for quantum programs presents constructive approach for proving inclusion of class of functions, computed with bounded error by syntactical quantum branching programs, into the complexity class $NC^1$.
Keywords: quantum algorithms, simulation complexity, branching program. 
@article{UZKU_2009_151_2_a1,
     author = {F. M. Ablayev},
     title = {On {Complexity} of {Classical} {Simulation} of {Quantum} {Branching} {Programs}},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {7--15},
     year = {2009},
     volume = {151},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a1/}
}
TY  - JOUR
AU  - F. M. Ablayev
TI  - On Complexity of Classical Simulation of Quantum Branching Programs
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2009
SP  - 7
EP  - 15
VL  - 151
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a1/
LA  - ru
ID  - UZKU_2009_151_2_a1
ER  - 
%0 Journal Article
%A F. M. Ablayev
%T On Complexity of Classical Simulation of Quantum Branching Programs
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2009
%P 7-15
%V 151
%N 2
%U http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a1/
%G ru
%F UZKU_2009_151_2_a1
F. M. Ablayev. On Complexity of Classical Simulation of Quantum Branching Programs. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 151 (2009) no. 2, pp. 7-15. http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a1/

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

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

[3] Valiev K. A., Kokin A. A., Kvantovye kompyutery: nadezhdy i realnost, NITs “Regulyarnaya i khaoticheskaya dinamika”, Izhevsk, 2001, 352 pp.

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

[5] Ozhigov Yu. I., Kvantovye vychisleniya, Izd-vo fak. VMiK Mosk. un-ta, M., 2003, 104 pp.

[6] Nielsen M. A., Chuang I. L., Quantum Computation and Quantum Information, Cambridge Univ. Press, Cambridge, 2000, 676 pp. | MR | Zbl

[7] Wegener I., Branching Programs and Binary Decision Diagrams, Society for Industrial and Applied Mathematics, Philadelphia, 2000, 408 pp. | MR | Zbl

[8] Ablayev F., Moore C., Pollett C., “Quantum and Stochastic Branching Programs of Bounded Width”, Proc. of the Intern. Colloquium on Automata, Languages and Programming (ICALP' 2002), Lecture Notes in Computer Science, 2380, Springer-Verlag, Berlin, 2002, 343–354 | MR | Zbl

[9] Ablaev F. M., “O slozhnosti klassicheskikh i kvantovykh modelei vychislenii”, Matem. vopr. kibernetiki, 13, 2004, 137–146 | MR | Zbl

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

[11] Aleksandrov P. S., Vvedenie v teoriyu mnozhestv i obschuyu topologiyu, Nauka, M., 1977, 368 pp. | MR

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