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

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIEMay 24, 20061 citation

Quantum branching programs and space-bounded nonuniform quantum complexity

Martin Sauerhoff, Detlef Sieling

arXiv:quant-ph/0403164Theoretical Computer ScienceFeb 8, 200541 citations

Width Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams with Repeated Test

Kamil Ravilevich Khadiev, Rishat Ibrahimov

We consider quantum, nondterministic and probabilistic versions of known computational model Ordered Read- $k$ -times Branching Programs or Ordered Binary Decision Diagrams with repeated test ( $k$ -QOBDD, $k$ -NOBDD and $k$ -POBDD). We show width hierarchy for complexity classes of Boolean function computed by these models and discuss relation between different variants of $k$ -OBDD.We consider quantum, nondterministic and probabilistic versions of known computational model Ordered Read-$k$-times Branching Programs or Ordered Binary Decision Diagrams with repeated test ($k$-QOBDD, $k$-NOBDD and $k$-POBDD). We show width hierarchy for complexity classes of Boolean function computed by these models and discuss relation between different variants of $k$-OBDD.

arXiv:1703.07891Mar 23, 20172 citations

On Computational Power of Quantum Branching Programs

Farid Mansurovich Ablayev, Aida Gainutdinova, Marek Karpiński

arXiv:quant-ph/0302022Lecture notes in computer scienceJan 1, 200141 citations

Algorithms for Quantum Branching Programs Based on Fingerprinting

Farid Mansurovich Ablayev, Alexander Vasiliev

In the paper we develop a method for constructing quantum algorithms for computing Boolean functions by quantum ordered read-once branching programs (quantum OBDDs). Our method is based on fingerprinting technique and representation of Boolean functions by their characteristic polynomials. We use circuit notation for branching programs for desired algorithms presentation. For several known functions our approach provides optimal QOBDDs. Namely we consider such functions as Equality, Palindrome, and Permutation Matrix Test. We also propose a generalization of our method and apply it to the Boolean variant of the Hidden Subgroup Problem.In the paper we develop a method for constructing quantum algorithms for computing Boolean functions by quantum ordered read-once branching programs (quantum OBDDs). Our method is based on fingerprinting technique and representation of Boolean functions by their characteristic polynomials. We use circuit notation for branching programs for desired algorithms presentation. For several known functions our approach provides optimal QOBDDs. Namely we consider such functions as Equality, Palindrome, and Permutation Matrix Test. We also propose a generalization of our method and apply it to the Boolean variant of the Hidden Subgroup Problem.

arXiv:0911.2317Electronic Proceedings in Theoretical Computer ScienceNov 15, 200929 citations

We consider quantum, nondterministic and probabilistic versions of known computational model Ordered Read-

k

-times Branching Programs or Ordered Binary Decision Diagrams with repeated test (

k

-QOBDD,

k

-NOBDD and

k

-POBDD). We show width hierarchy for complexity classes of Boolean function computed by these models and discuss relation between different variants of

k

-OBDD.