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

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

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},
     publisher = {mathdoc},
     volume = {151},
     number = {2},
     year = {2009},
     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
PB  - mathdoc
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
%I mathdoc
%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/