On computational power of classical and quantum branching programs

Farid Ablayev

doi:10.1117/12.683111

31 May 2006 On computational power of classical and quantum branching programs

Farid Ablayev

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 (2^{c(δ)(n-log n)}) lower bound for the width of quantum OBDDs depending on the error δ allowed.

Citation Download Citation

Farid Ablayev "On computational power of classical and quantum branching programs", Proc. SPIE 6264, Quantum Informatics 2005, 626401 (31 May 2006); https://doi.org/10.1117/12.683111

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available