Quantum algorithm for dynamic programming approach for DAGs and applications
DOI10.1134/s1995080223020191arXiv2212.14433OpenAlexW4377234995MaRDI QIDQ6043927
No author found.
Publication date: 25 May 2023
Published in: Lobachevskii Journal of Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2212.14433
computational complexitygraphdynamic programmingquantum computationquantum algorithmZhegalkin polynomialDAGBoolean formulaquery modelDNFquantum modelsNANDBoolean formula evaluationclassical vs. quantumand-or-not formula
Theory of computing (68Qxx) Graph theory (05Cxx) Foundations, quantum information and its processing, quantum axioms, and philosophy (81Pxx)
Cites Work
- Quantum online algorithms with respect to space and advice complexity
- Exponential separation of quantum and classical online space complexity
- Error-free affine, unitary, and probabilistic OBDDs
- Quantum algorithms for matching problems
- Improved constructions of quantum automata
- Algebraic logic. Transl. from the Russian by Robert H. Silverman
- Quantum-over-classical advantage in solving multiplayer games
- Quantum algorithms for string processing
- Two-way and one-way quantum and classical automata with advice for online minimization problems
- Quantum algorithm for Dyck language with multiple types of brackets
- Quantum online streaming algorithms with logarithmic memory
- Quantum algorithm for dynamic programming approach for DAGs. Applications for Zhegalkin polynomial evaluation and some problems on DAGs
- On the quantum and classical complexity of solving subtraction games
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
- The Quantum Query Complexity of Read-Many Formulas
- Quantum Computation and Quantum Information
- Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
- On quantum realisation of Boolean functions by the fingerprinting technique
- Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
- Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test
- Computational Complexity
- Quantum Algorithms for Matching and Network Flows
- Automata, Languages and Programming
- Quantum Query Complexity of Some Graph Problems
- Classical and quantum algorithms for constructing text from dictionary problem
- Classical and Quantum Algorithms for Assembling a Text from a Dictionary
- Error-Free Affine, Unitary, and Probabilistic OBDDs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Quantum algorithm for dynamic programming approach for DAGs and applications
