Quantum Dynamic Programming
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909603663446016 |
|---|---|
| author | Son, Jeongrak Gluza, Marek Takagi, Ryuji Ng, Nelly H. Y. |
| author_facet | Son, Jeongrak Gluza, Marek Takagi, Ryuji Ng, Nelly H. Y. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_09187 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum Dynamic Programming Son, Jeongrak Gluza, Marek Takagi, Ryuji Ng, Nelly H. Y. Quantum Physics 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. |
| title | Quantum Dynamic Programming |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2403.09187 |