On the computational power of probabilistic and quantum branching program

DOI10.1016/j.ic.2005.04.003zbMath1105.68037OpenAlexW2050426534WikidataQ62039561 ScholiaQ62039561MaRDI QIDQ2581534

Farid M. Ablayev, Aida Gainutdinova, Marek Karpinski, Christopher Pollett, Moore, Cristopher

Publication date: 10 January 2006

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2005.04.003

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Related Items (16)

Unary probabilistic and quantum automata on promise problems ⋮ Very narrow quantum OBDDs and width hierarchies for classical OBDDs ⋮ On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs ⋮ Two-way and one-way quantum and classical automata with advice for online minimization problems ⋮ Nondeterministic unitary OBDDs ⋮ Reordering method and hierarchies for quantum and classical ordered binary decision diagrams ⋮ Computing Boolean Functions via Quantum Hashing ⋮ Quantum versus classical online streaming algorithms with logarithmic size of memory ⋮ Deterministic construction of QFAs based on the quantum fingerprinting technique ⋮ On quantum realisation of Boolean functions by the fingerprinting technique ⋮ Classical and Quantum Computations with Restricted Memory ⋮ Error-Free Affine, Unitary, and Probabilistic OBDDs ⋮ Comparative complexity of quantum and classical OBDDs for total and partial functions ⋮ Quantum online algorithms with respect to space and advice complexity ⋮ Quantum online streaming algorithms with logarithmic memory ⋮ Width hierarchy for \(k\)-OBDD of small width

Cites Work

• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• A lower bound for integer multiplication on randomized ordered read-once branching programs.
• Quantum automata and quantum grammars
• Circuits and expressions with nonassociative gates
• Quantum branching programs and space-bounded nonuniform quantum complexity
• On lower bounds for read-\(k\)-times branching programs
• Computing with highly mixed states (extended abstract)
• Finite monoids and the fine structure of NC ¹
• Finite Continuous Time Markov Chains
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Branching Programs and Binary Decision Diagrams
• A Property of Finite Simple Non-Abelian Groups
• Probabilistic automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the computational power of probabilistic and quantum branching program