This article is cited in 1 paper

The XV International Conference "Problems of Theoretical Cybernetics"

Quantum and Classical Simulation of Quantum Branching Programs

A. F. Gainutdinova

Kazan State University, The Faculty of Computer Science and Cybernetics

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

UDC: 519.71

Received: 27.02.2009