Quantum Dynamic Programming

Abstract

We introduce a quantum extension of dynamic programming, a fundamental computational method that efficiently solves recursive problems using memory. Our innovation lies in showing how to coherently generate recursion step unitaries by using memorized intermediate quantum states. Quantum dynamic programming achieves an exponential reduction in circuit depth for a broad class of fixed-point quantum recursions, though this comes at the cost of increased circuit width. Interestingly, the trade-off becomes more favourable when the initial state is pure. By hybridizing our approach with a conventional memoryless one, we can flexibly balance circuit depth and width to optimize performance on quantum devices with fixed hardware constraints. Finally, we showcase applications of quantum dynamic programming to several quantum recursions, including a variant of Grover's search, quantum imaginary-time evolution, and a new protocol for obliviously preparing a quantum state in its Schmidt basis.

arXiv comment32 pages; stronger results than v1, with significant rewriting of the main text

References in corpus (31)

• Concentrating Partial Entanglement by Local Operations
• Efficient classical simulation of slightly entangled quantum computations
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum principal component analysis
• Error mitigation for short-depth quantum circuits
• Hamiltonian Simulation by Qubitization
• Entanglement monotones
• Optimal Quantum Cloning Machines
• Quantum cloning
• Quantum Internet: Networking Challenges in Distributed Quantum Computing
• The General Quantum Interference Principle and the Duality Computer
• Direct detection of quantum entanglement
• Fixed-point quantum search with an optimal number of queries
• A different kind of quantum search
• Fundamental limits of quantum error mitigation
• Optimal purification of single qubits
• Measurement Protocol for the Entanglement Spectrum of Cold Atoms
• Hamiltonian Simulation with Optimal Sample Complexity
• Universal fault-tolerant gates on concatenated stabilizer codes
• Universal Sampling Lower Bounds for Quantum Error Mitigation
• Universal cost bound of quantum error mitigation based on quantum estimation theory
• Universal entanglement concentration
• Efficient Product Formulas for Commutators and Applications to Quantum Simulation
• Wave Matrix Lindbladization I: Quantum Programs for Simulating Markovian Dynamics
• Error rates and resource overheads of encoded three-qubit gates
• Double-bracket quantum algorithms for diagonalization
• Wave Matrix Lindbladization II: General Lindbladians, Linear Combinations, and Polynomials
• Streaming quantum state purification
• Higher-order quantum transformations of Hamiltonian dynamics
• Accelerating Quantum Algorithms with Precomputation
• Quantum approximated cloning-assisted density matrix exponentiation

Cited by in corpus (4)

• Double-bracket quantum algorithms for quantum imaginary-time evolution
• Double-bracket algorithm for quantum signal processing without post-selection
• Sample-based Hamiltonian and Lindbladian simulation: Non-asymptotic analysis of sample complexity
• Double-bracket quantum algorithms for high-fidelity ground state preparation