Share Email Print
cover

Proceedings Paper

On computational power of classical and quantum branching programs
Author(s): Farid Ablayev
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 31 May 2006
PDF: 10 pages
Proc. SPIE 6264, Quantum Informatics 2005, 626401 (31 May 2006); doi: 10.1117/12.683111
Show Author Affiliations
Farid Ablayev, Kazan State Univ. (Russia)


Published in SPIE Proceedings Vol. 6264:
Quantum Informatics 2005
Yuri I. Ozhigov, Editor(s)

© SPIE. Terms of Use
Back to Top