On simulating the quantum and classical branching programs
Aida Gainutdinova · Journal of Applied and Industrial Mathematics · 2007
The complexity classes defined on the basis of branching programs are considered. Some basic relations are established between the complexity classes defined by the probabilistic and quantum branching programs (measure-once, as well as measure-many), computing with bounded or unbounded error. To prove these relations, we developed a method of “linear simulation” of a quantum branching program and a method of “quantum simulation” of a probabilistic branching program.