Towards quantum advantage by classical solving quantum-preconditioned problems

State-of-the-art classical optimization solvers set a high bar for quantum computers to deliver utility in this domain. We introduce a quantum preconditioning approach, which uses the quantum approximate optimization algorithm, to transform the input problem for a classical solver into a form that is easier to tackle. We demonstrate that best-in-class classical heuristics such as simulated annealing and the Burer-Monteiro algorithm can converge more rapidly when given quantum preconditioned input for various academic problems and a real-world grid energy problem, and test its experimental implementation on a superconducting device. We show that quantum preconditioning has a quantum-inspired advantage for random 3-regular graph maximum-cut problems through quantum circuit emulations, and identify challenges and discuss the prospects for a hardware-based quantum advantage.