Iterative quantum optimization of spin glass problems with rapidly oscillating transverse fields

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.