2002/01/30 by Farid Ablayev, Cristopher Moore, Ablayev, Farid +3
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0201139
12 pages
openalex publication_date 2002/01/30 · arxiv created 2004/01/03 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we show that one qubit polynomial time computations are at least as powerful as \NC1 circuits. More precisely, we define syntactic models for quantum and stochastic branching programs of bounded width and prove upper and lower bounds on their power. We show any \NC1 language can be accepted exactly by a width-2 quantum branching program of polynomial length, in contrast to the classical case where width 5 is necessary unless \NC1=\ACC. This separates width-2 quantum programs from width-2 doubly stochastic programs as we show the latter cannot compute the middle bit of multiplication. Finally, we show that bounded-width quantum and stochastic programs can be simulated by classical programs of larger but bounded width, and thus are in \NC1. The change in the revised version is the addition of the syntactic condition.