# Quantum Dynamic Programming

**Authors:** Jeongrak Son, Marek Gluza, Ryuji Takagi, Nelly H. Y. Ng  
**arXiv:** [2403.09187](https://arxiv.org/abs/2403.09187)  
**Date:** 2024-03-14  
**Summary page:** https://www.summarizepaper.com/en/arxiv-id/2403.09187v1/

## Key points

- Introduction of quantum extension of dynamic programming
- Coherent generation of unitaries using memorized intermediate quantum states
- Exponential reduction in circuit depth for fixed-point quantum recursions
- Application to double-bracket quantum algorithm for diagonalization
- Development of a new protocol for preparing a quantum state in its Schmidt basis
- Importance of placeholder memory in reducing computation runtime
- Demonstration of faster computations by reusing information from memorized states

## Summary

In their paper "Quantum Dynamic Programming," Jeongrak Son, Marek Gluza, Ryuji Takagi, and Nelly H. Y. Ng introduce a quantum extension of dynamic programming - a fundamental computational method for efficiently solving recursive problems using memory. The key innovation of their work lies in demonstrating how to coherently generate unitaries of recursion steps by utilizing memorized intermediate quantum states. This approach leads to an exponential reduction in circuit depth for a wide range of fixed-point quantum recursions, including a variant of Grover's search. Moreover, the researchers apply quantum dynamic programming to a recently proposed double-bracket quantum algorithm for diagonalization. This application results in the development of a new protocol for obliviously preparing a quantum state in its Schmidt basis. This advancement opens up possibilities for uncovering entanglement structures within unknown quantum states. The authors highlight the significance of placeholder memory in reducing computation runtime and draw parallels with classic examples like the Fibonacci sequence. By leveraging memorized intermediate states effectively, they demonstrate that reusing information can lead to significantly faster computations compared to recalculating values from scratch. Overall, this research sheds light on the potential of quantum dynamic programming as a powerful tool for optimizing computational processes and unlocking new pathways for exploring complex quantum systems and algorithms.