Iterative quantum optimization of spin glass problems with rapidly oscillating transverse fields
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914911322374144 |
|---|---|
| author | Barton, Brandon Sagal, Jacob Feeney, Sean Grattan, George Patnaik, Pratik Oganesyan, Vadim Carr, Lincoln D Kapit, Eliot |
| author_facet | Barton, Brandon Sagal, Jacob Feeney, Sean Grattan, George Patnaik, Pratik Oganesyan, Vadim Carr, Lincoln D Kapit, Eliot |
| contents | In this work, we introduce a new iterative quantum algorithm, called Iterative Symphonic Tunneling for Satisfiability problems (IST-SAT), which solves quantum spin glass optimization problems using high-frequency oscillating transverse fields. IST-SAT operates as a sequence of iterations, in which bitstrings returned from one iteration are used to set spin-dependent phases in oscillating transverse fields in the next iteration. Over several iterations, the novel mechanism of the algorithm steers the system toward the problem ground state. We benchmark IST-SAT on sets of hard MAX-3-XORSAT problem instances with exact state vector simulation, and report polynomial speedups over trotterized adiabatic quantum computation (TAQC) and the best known semi-greedy classical algorithm. When IST-SAT is seeded with a sufficiently good initial approximation, the algorithm converges to exact solution(s) in a polynomial number of iterations. Our numerical results identify a critial Hamming radius(CHR), or quality of initial approximation, where the time-to-solution crosses from exponential to polynomial scaling in problem size. By combining IST-SAT with future classical or quantum approximation algorithms, larger gains may be achieved. The mechanism we present in this work thus presents a new path toward achieving quantum advantage in optimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_06571 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Iterative quantum optimization of spin glass problems with rapidly oscillating transverse fields Barton, Brandon Sagal, Jacob Feeney, Sean Grattan, George Patnaik, Pratik Oganesyan, Vadim Carr, Lincoln D Kapit, Eliot Quantum Physics In this work, we introduce a new iterative quantum algorithm, called Iterative Symphonic Tunneling for Satisfiability problems (IST-SAT), which solves quantum spin glass optimization problems using high-frequency oscillating transverse fields. IST-SAT operates as a sequence of iterations, in which bitstrings returned from one iteration are used to set spin-dependent phases in oscillating transverse fields in the next iteration. Over several iterations, the novel mechanism of the algorithm steers the system toward the problem ground state. We benchmark IST-SAT on sets of hard MAX-3-XORSAT problem instances with exact state vector simulation, and report polynomial speedups over trotterized adiabatic quantum computation (TAQC) and the best known semi-greedy classical algorithm. When IST-SAT is seeded with a sufficiently good initial approximation, the algorithm converges to exact solution(s) in a polynomial number of iterations. Our numerical results identify a critial Hamming radius(CHR), or quality of initial approximation, where the time-to-solution crosses from exponential to polynomial scaling in problem size. By combining IST-SAT with future classical or quantum approximation algorithms, larger gains may be achieved. The mechanism we present in this work thus presents a new path toward achieving quantum advantage in optimization. |
| title | Iterative quantum optimization of spin glass problems with rapidly oscillating transverse fields |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2408.06571 |