Quantum algorithm for dynamic programming approach for DAGs and applications
From MaRDI portal
Abstract: In this paper, we present a quantum algorithm for the dynamic programming approach for problems on directed acyclic graphs (DAGs). The running time of the algorithm is , and the running time of the best known deterministic algorithm is , where is the number of vertices, is the number of vertices with at least one outgoing edge; is the number of edges. We show that we can solve problems that use OR, AND, NAND, MAX, and MIN functions as the main transition steps. The approach is useful for a couple of problems. One of them is computing a Boolean formula that is represented by Zhegalkin polynomial, a Boolean circuit with shared input and non-constant depth evaluation. Another two are the single source longest paths search for weighted DAGs and the diameter search problem for unweighted DAGs.
Cites work
- scientific article; zbMATH DE number 6667586 (Why is no real title available?)
- scientific article; zbMATH DE number 5788514 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 2103524 (Why is no real title available?)
- A panoply of quantum algorithms
- Algebraic logic. Transl. from the Russian by Robert H. Silverman
- An optimal quantum algorithm for the oracle identification problem
- Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
- Automata, Languages and Programming
- Classical and Quantum Algorithms for Assembling a Text from a Dictionary
- Classical and quantum algorithms for constructing text from dictionary problem
- Computational Complexity
- Error-Free Affine, Unitary, and Probabilistic OBDDs
- Error-free affine, unitary, and probabilistic OBDDs
- Exponential separation of quantum and classical online space complexity
- Improved constructions of quantum automata
- Introduction to algorithms
- Lower bounds and hierarchies for quantum memoryless communication protocols and quantum ordered binary decision diagrams with repeated test
- On quantum realisation of Boolean functions by the fingerprinting technique
- On the quantum and classical complexity of solving subtraction games
- Quantum Algorithms for Matching and Network Flows
- Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
- Quantum Query Complexity of Some Graph Problems
- Quantum algorithm for Dyck language with multiple types of brackets
- Quantum algorithm for dynamic programming approach for DAGs. Applications for Zhegalkin polynomial evaluation and some problems on DAGs
- Quantum algorithms for matching problems
- Quantum algorithms for string processing
- Quantum computation and quantum information. 10th anniversary edition
- Quantum online algorithms with respect to space and advice complexity
- Quantum online streaming algorithms with logarithmic memory
- Quantum-over-classical advantage in solving multiplayer games
- Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
- The quantum query complexity of read-many formulas
- Two-way and one-way quantum and classical automata with advice for online minimization problems
- Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
Cited in
(3)
This page was built for publication: Quantum algorithm for dynamic programming approach for DAGs and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6043927)
