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

Related Items (12)

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

This page was built for publication: Very narrow quantum OBDDs and width hierarchies for classical OBDDs