On the computational power of probabilistic and quantum branching program
DOI10.1016/J.IC.2005.04.003zbMATH Open1105.68037OpenAlexW2050426534WikidataQ62039561 ScholiaQ62039561MaRDI QIDQ2581534FDOQ2581534
Authors: F. Ablayev, Aida Gainutdinova, Marek Karpinski, Christopher Pollett, Cristopher Moore 
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
Recommendations
- scientific article; zbMATH DE number 1839432
- scientific article; zbMATH DE number 2095528
- Complexity bounds on some fundamental computational problems for quantum branching programs.
- scientific article; zbMATH DE number 6004860
- On complexity of classical simulation of quantum branching programs
- Quantum branching programs and space-bounded nonuniform quantum complexity
- Quantum and classical simulation of quantum branching programs
- Stochastic Algorithms: Foundations and Applications
- scientific article; zbMATH DE number 1696662
- scientific article; zbMATH DE number 2086634
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)
Cites Work
- A course in combinatorics.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Probabilistic automata
- Branching Programs and Binary Decision Diagrams
- Circuits and expressions with nonassociative gates
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- On lower bounds for read-\(k\)-times branching programs
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Finite Continuous Time Markov Chains
- Title not available (Why is that?)
- Finite monoids and the fine structure of NC 1
- Quantum automata and quantum grammars
- Quantum branching programs and space-bounded nonuniform quantum complexity
- A Property of Finite Simple Non-Abelian Groups
- Computing with highly mixed states (extended abstract)
- A lower bound for integer multiplication on randomized ordered read-once branching programs.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (20)
- Quantum online streaming algorithms with logarithmic memory
- Title not available (Why is that?)
- On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
- Error-Free Affine, Unitary, and Probabilistic OBDDs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Nondeterministic unitary OBDDs
- Title not available (Why is that?)
- On quantum realisation of Boolean functions by the fingerprinting technique
- Title not available (Why is that?)
- 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
- Quantum online algorithms with respect to space and advice complexity
- Width hierarchy for \(k\)-OBDD of small width
- Comparative complexity of quantum and classical OBDDs for total and partial functions
- Two-way and one-way quantum and classical automata with advice for online minimization problems
- Classical and Quantum Computations with Restricted Memory
This page was built for publication: On the computational power of probabilistic and quantum branching program
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2581534)
