(Sub)Exponential Quantum Speedup for Optimization
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917992627961856 |
|---|---|
| author | Leng, Jiaqi Wu, Kewen Wu, Xiaodi Zheng, Yufan |
| author_facet | Leng, Jiaqi Wu, Kewen Wu, Xiaodi Zheng, Yufan |
| contents | We demonstrate provable (sub)exponential quantum speedups in both discrete and continuous optimization, achieved through simple and natural quantum optimization algorithms, namely the quantum adiabatic algorithm for discrete optimization and quantum Hamiltonian descent for continuous optimization. Our result builds on the Gilyén--Hastings--Vazirani (sub)exponential oracle separation for adiabatic quantum computing. With a sequence of perturbative reductions, we compile their construction into two standalone objective functions, whose oracles can be directly leveraged by the plain adiabatic evolution and Schrödinger operator evolution for discrete and continuous optimization, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_14841 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | (Sub)Exponential Quantum Speedup for Optimization Leng, Jiaqi Wu, Kewen Wu, Xiaodi Zheng, Yufan Quantum Physics Computational Complexity Optimization and Control We demonstrate provable (sub)exponential quantum speedups in both discrete and continuous optimization, achieved through simple and natural quantum optimization algorithms, namely the quantum adiabatic algorithm for discrete optimization and quantum Hamiltonian descent for continuous optimization. Our result builds on the Gilyén--Hastings--Vazirani (sub)exponential oracle separation for adiabatic quantum computing. With a sequence of perturbative reductions, we compile their construction into two standalone objective functions, whose oracles can be directly leveraged by the plain adiabatic evolution and Schrödinger operator evolution for discrete and continuous optimization, respectively. |
| title | (Sub)Exponential Quantum Speedup for Optimization |
| topic | Quantum Physics Computational Complexity Optimization and Control |
| url | https://arxiv.org/abs/2504.14841 |