The XV International Conference "Problems of Theoretical Cybernetics"

On Complexity of Classical Simulation of Quantum Branching Programs

F. M. Ablayev

Kazan State University, The Faculty of Computer Science and Cybernetics

Abstract: 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.

UDC: 519.71

Received: 30.03.2009