Geodesic
Quantum and 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. 45-58
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The paper views a model of branching programs (BP). A model of classical probabilistic BP is considered along with two different models of quantum BP (once-measuring and many time measuring quantum BP). Three different methods of simulation of BPs are presented: method of classical simulation of quantum BPs and two different methods of quantum simulation of probabilistic BPs. Complexity of methods is proved. Comparative analysis of methods is presented.
Keywords: branching programs, computation complexity, quantum and classical simulation. 
@article{UZKU_2009_151_2_a5,
     author = {A. F. Gainutdinova},
     title = {Quantum and {Classical} {Simulation} of {Quantum} {Branching} {Programs}},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {45--58},
     year = {2009},
     volume = {151},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a5/}
}
TY  - JOUR
AU  - A. F. Gainutdinova
TI  - Quantum and Classical Simulation of Quantum Branching Programs
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2009
SP  - 45
EP  - 58
VL  - 151
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a5/
LA  - ru
ID  - UZKU_2009_151_2_a5
ER  - 
%0 Journal Article
%A A. F. Gainutdinova
%T Quantum and Classical Simulation of Quantum Branching Programs
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2009
%P 45-58
%V 151
%N 2
%U http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a5/
%G ru
%F UZKU_2009_151_2_a5
A. F. Gainutdinova. Quantum and 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. 45-58. http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a5/

[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] Ablayev F., Gainutdinova A., Karpinski M., “On Computational Power of Quantum Branching Programs”, Fundamentals of computation theory (FCT 2001), Proc. of the 13th Int. Symposium, Fundamentals of computation theory (Riga, Latvia, 2001), Lecture Notes in Comput. Sci., 2138, Springer, Berlin, 2001, 59–70 | DOI | MR | Zbl

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

[5] 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 Int. Conf. on Computing and Combinatorics, COCOON' 2000, Lecture Notes in Comput. Sci., 1858, Springer-Verlag, 2000, 467–476 | DOI | MR | Zbl

[6] Sauerhoff M., Sieling D., “Quantum branching programs and space-bounded nonuniform quantum complexity”, Theor. Comput. Sci., 334 (2005), 177–225 | DOI | MR | Zbl

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

[8] Gainutdinova A. F., “Modelirovanii kvantovykh i klassicheskikh binarnykh programm”, Diskr. analiz i issled. operatsii. Ser. 1, 13:1 (2006), 45–64 | MR

[9] Borodin A., Fischer M., Kirkpatrick D., Lynch N., Tompa M., “A time-space tradeoff for sorting on non-oblivious machines”, Proc. 20th Annual Symposium on Foundations of Computer Science, 1979, 319–327

[10] Ablayev F., Karpinski M., “On the power of randomized branching programs”, Proc. ICALP' 96, Lecture Notes in Comput. Sci., 1099, Springer, 1996, 348–356 | DOI | MR | Zbl

[11] Gruska J., Quantum computing, McGraw-Hill Publishing Company, 1999, 419 pp. | MR

[12] Sauerhoff M., Complexity theoretical results for randomized branching programs, Ph. D. Dissertation, 1998; http://ls2-www.cs.uni-dortmund.de/~sauerhof/publications.shtml

[13] Spalek R., Space complexity of quantum computation, Dissertation, 2002; http://eccc.hpi-web.de/eccc-local/ECCC-These/spalek.html