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
Voir la notice du chapitre de livre provenant de la source Math-Net.Ru
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},
publisher = {mathdoc},
volume = {151},
number = {2},
year = {2009},
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 PB - mathdoc 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 %I mathdoc %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/