Solving hard optimization problems using quantum walks*

Quantum versions of random walks (QW) have long been known to solve the unordered search problem.
Recently, we showed that QW can also solve more realistic hard problems using many repeats of short runs. This is promising for practical application on realistic noisy quantum hardware, either purpose-built quantum annealers, or using QAOA algorithms. By exploiting the correlations in the problem, we find numerically that QW provide a better scaling than search for spin glass ground state problems [Callison et al, NJP, 21 123022, 2019], MAX2SAT, and maximum independent set. However, the most important comparison is with state-of-the-art classical algorithms for the same problems. By this metric, pure QW do not beat the best classical. However, hard problem instances for classical algorithms are not necessarily hard for QW, and vice versa: correlation of problem hardness (at testable sizes) is weak. This points to hybrid algorithms as the best approach for speeding up practical optimisation problems, both quantum-classical, and quantum-quantum, generalizing QW to rapid quenches [Callison et al, arXiv:2007.11599].