Fast Convex Optimization with Quantum Gradient Methods
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918045222436864 |
|---|---|
| author | Augustino, Brandon Herman, Dylan Fontana, Enrico Kim, Junhyung Lyle Watkins, Jacob Chakrabarti, Shouvanik Pistoia, Marco |
| author_facet | Augustino, Brandon Herman, Dylan Fontana, Enrico Kim, Junhyung Lyle Watkins, Jacob Chakrabarti, Shouvanik Pistoia, Marco |
| contents | We study quantum algorithms based on quantum (sub)gradient estimation using noisy function evaluation oracles, and demonstrate the first dimension-independent query complexities (up to poly-logarithmic factors) for zeroth-order convex optimization in both smooth and nonsmooth settings. Interestingly, only using noisy function evaluation oracles, we match the first-order query complexities of classical gradient descent, thereby exhibiting exponential separation between quantum and classical zeroth-order optimization. We then generalize these algorithms to work in non-Euclidean settings by using quantum (sub)gradient estimation to instantiate mirror descent and its variants, including dual averaging and mirror prox. By leveraging a connection between semidefinite programming and eigenvalue optimization, we use our quantum mirror descent method to give a new quantum algorithm for solving semidefinite programs, linear programs, and zero-sum games. We identify a parameter regime in which our zero-sum games algorithm is faster than any existing classical or quantum approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_17356 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast Convex Optimization with Quantum Gradient Methods Augustino, Brandon Herman, Dylan Fontana, Enrico Kim, Junhyung Lyle Watkins, Jacob Chakrabarti, Shouvanik Pistoia, Marco Quantum Physics We study quantum algorithms based on quantum (sub)gradient estimation using noisy function evaluation oracles, and demonstrate the first dimension-independent query complexities (up to poly-logarithmic factors) for zeroth-order convex optimization in both smooth and nonsmooth settings. Interestingly, only using noisy function evaluation oracles, we match the first-order query complexities of classical gradient descent, thereby exhibiting exponential separation between quantum and classical zeroth-order optimization. We then generalize these algorithms to work in non-Euclidean settings by using quantum (sub)gradient estimation to instantiate mirror descent and its variants, including dual averaging and mirror prox. By leveraging a connection between semidefinite programming and eigenvalue optimization, we use our quantum mirror descent method to give a new quantum algorithm for solving semidefinite programs, linear programs, and zero-sum games. We identify a parameter regime in which our zero-sum games algorithm is faster than any existing classical or quantum approach. |
| title | Fast Convex Optimization with Quantum Gradient Methods |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2503.17356 |