Very narrow quantum OBDDs and width hierarchies for classical OBDDs

DOI10.1134/S199508021606007XzbMath1407.68159OpenAlexW2952645538MaRDI QIDQ2361670

Yanyan Li

Publication date: 30 June 2017

Published in: Lobachevskii Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s199508021606007x

zbMATH Keywords

partial functionsquantum computationnondeterminismOBDDwidth hierarchy

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

Unary probabilistic and quantum automata on promise problems, 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, Quantum versus classical online streaming algorithms with logarithmic size of memory, Quantum algorithm for dynamic programming approach for DAGs and applications, Deterministic construction of QFAs based on the quantum fingerprinting technique, Classical and Quantum Computations with Restricted Memory, Error-Free Affine, Unitary, and Probabilistic OBDDs, Quantum online algorithms with respect to space and advice complexity, Quantum online streaming algorithms with logarithmic memory, New size hierarchies for two way automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Superiority of exact quantum automata for promise problems
• Unbounded-error quantum computation with small space bounds
• Width hierarchy for \(k\)-OBDD of small width
• The power of nondeterminism and randomness for oblivious branching programs
• Quantum branching programs and space-bounded nonuniform quantum complexity
• On the complexity of simulating space-bounded quantum computations
• On the computational power of probabilistic and quantum branching program
• Implications of Quantum Automata for Contextuality
• Branching Programs and Binary Decision Diagrams
• Elementary methods in the study of the distribution of prime numbers
• Developments in Language Theory
• Classical Automata on Promise Problems
• Analogies and differences between quantum and stochastic automata