This article is cited in 4 papers

On the relative complexity of quantum and classical branching programs

A. F. Gainutdinova


Abstract: We give a definition of a quantum branching program. A well-known Boolean function $\operatorname{MOD}_p$ is considered. We prove that any deterministic branching program and any probabilistic ordered stable branching program which $(1/2+\varepsilon)$-compute the function $\operatorname{MOD}_p$ are of width no less than $p$. We construct a stable quantum branching program of width $O(\log p)$ which computes the function $\operatorname{MOD}_p$ with one-sided error $\varepsilon>0$.

UDC: 519.7

Received: 22.02.2002

DOI: 10.4213/dm258

 English version: Discrete Mathematics and Applications, 2002, 12:5, 515–526

Bibliographic databases:

• 
•