Optimization by Decoded Quantum Interferometry
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_ | 1866909864279670784 |
|---|---|
| author | Jordan, Stephen P. Shutty, Noah Wootters, Mary Zalcman, Adam Schmidhuber, Alexander King, Robbie Isakov, Sergei V. Khattar, Tanuj Babbush, Ryan |
| author_facet | Jordan, Stephen P. Shutty, Noah Wootters, Mary Zalcman, Adam Schmidhuber, Alexander King, Robbie Isakov, Sergei V. Khattar, Tanuj Babbush, Ryan |
| contents | Achieving superpolynomial speedups for optimization has long been a central goal for quantum algorithms. Here we introduce Decoded Quantum Interferometry (DQI), a quantum algorithm that uses the quantum Fourier transform to reduce optimization problems to decoding problems. For approximating optimal polynomial fits over finite fields, DQI achieves a superpolynomial speedup over known classical algorithms. The speedup arises because the problem's algebraic structure is reflected in the decoding problem, which can be solved efficiently. We then investigate whether this approach can achieve speedup for optimization problems that lack algebraic structure but have sparse clauses. These problems reduce to decoding LDPC codes, for which powerful decoders are known. To test this, we construct a max-XORSAT instance where DQI finds an approximate optimum significantly faster than general-purpose classical heuristics, such as simulated annealing. While a tailored classical solver can outperform DQI on this instance, our results establish that combining quantum Fourier transforms with powerful decoding primitives provides a promising new path toward quantum speedups for hard optimization problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_08292 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimization by Decoded Quantum Interferometry Jordan, Stephen P. Shutty, Noah Wootters, Mary Zalcman, Adam Schmidhuber, Alexander King, Robbie Isakov, Sergei V. Khattar, Tanuj Babbush, Ryan Quantum Physics Achieving superpolynomial speedups for optimization has long been a central goal for quantum algorithms. Here we introduce Decoded Quantum Interferometry (DQI), a quantum algorithm that uses the quantum Fourier transform to reduce optimization problems to decoding problems. For approximating optimal polynomial fits over finite fields, DQI achieves a superpolynomial speedup over known classical algorithms. The speedup arises because the problem's algebraic structure is reflected in the decoding problem, which can be solved efficiently. We then investigate whether this approach can achieve speedup for optimization problems that lack algebraic structure but have sparse clauses. These problems reduce to decoding LDPC codes, for which powerful decoders are known. To test this, we construct a max-XORSAT instance where DQI finds an approximate optimum significantly faster than general-purpose classical heuristics, such as simulated annealing. While a tailored classical solver can outperform DQI on this instance, our results establish that combining quantum Fourier transforms with powerful decoding primitives provides a promising new path toward quantum speedups for hard optimization problems. |
| title | Optimization by Decoded Quantum Interferometry |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2408.08292 |