31 May 2006 On computational power of classical and quantum branching programs
Author Affiliations +
Proceedings Volume 6264, Quantum Informatics 2005; 626401 (2006) https://doi.org/10.1117/12.683111
Event: Quantum Informatics 2005, 2005, Moscow, Russian Federation
Abstract
We present a classical stochastic simulation technique of quantum Branching programs. This technique allows to prove the following relations among complexity classes: PrQP-BP &subuline; PP-BP and BQP-BP &subuline; PP-BP. Here BPP-BP and PP-BP stands for the classes of functions computable with bounded error and unbounded error respectively by stochastic branching program of polynomial size. BQP-BP and PrQP-BP stands the classes of functions computable with bounded error and unbounded error respectively by quantum branching program of polynomial size. Second. We present two different types, of complexity lower bounds for quantum nonuniform automata (OBDDs). We call them "metric" and "entropic" lower bounds in according to proof technique used. We present explicit Boolean functions that show that these lower bounds are tight enough. We show that when considering "almost all Boolean functions" on n variables our entropic lower bounds gives exponential (2c(δ)(n-log n)) lower bound for the width of quantum OBDDs depending on the error δ allowed.
© (2006) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Farid Ablayev, Farid Ablayev, } "On computational power of classical and quantum branching programs", Proc. SPIE 6264, Quantum Informatics 2005, 626401 (31 May 2006); doi: 10.1117/12.683111; https://doi.org/10.1117/12.683111
PROCEEDINGS
10 PAGES


SHARE
RELATED CONTENT

Extended topological quantum computing
Proceedings of SPIE (May 27 2013)
Mathematical models of quantum noise
Proceedings of SPIE (January 07 2013)
The Fibonacci model and the Temperley-Lieb algebra
Proceedings of SPIE (April 27 2009)
On classical stimulation of quantum machines
Proceedings of SPIE (May 31 2005)

Back to Top