Iterative optimization of hard spin glass problems with high frequency AC drives (Part II)*

In this talk, we benchmark the IST-SAT algorithm using sets of hard MAX3-XORSAT instances, which are exponentially difficult for both exact and approximate optimization for all known classical and quantum methods. Using the Fujitsu Quantum Simulator–a classical HPC system–we estimate the average time to solution for IST-SAT through large scale numerical simulations of up to N = 30 qubit problems. We find that when IST-SAT is "seeded" using high-depth QAOA to set initial parameters, it demonstrates significant polynomial speedups over both QAOA (which performs relatively poorly for these problems) and the best reported classical algorithms. More sophisticated initial seeding algorithms can produce even larger gains. The mechanism for IST-SAT is fairly generic and we expect it should generalize to other quantum optimization problems which are bottlenecked by exponentially small gaps and first-order transitions.