This article is cited in 2 papers

On simulating the quantum and classical branching programs

A. F. Gainutdinova

N. G. Chebotarev Research Institute of Mathematics and Mechanics, Kazan State University

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

UDC: 519.72

Received: 24.05.2005

 English version: Journal of Applied and Industrial Mathematics, 2007, 1:1, 33–44

Bibliographic databases:

• 
• 
•