Quantum-enhanced optimization (45' + 15')

• Ashley Montanaro (University of Bristol)

**Abstract**: Solving hard optimization problems has long been proposed as an application of quantum computing, but standard approaches like Grover's algorithm seem to require fault-tolerance and are not suitable for near-term quantum computers. In this talk, I will present an approach, which we term quantum-enhanced optimization, to accelerate classical optimization algorithms by leveraging quantum sampling. Our method uses quantum-generated samples from algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) as warm starts to classical heuristics for solving challenging combinatorial problems like Max-Cut and Maximum Independent Set (MIS). To implement the method efficiently, we introduce novel parameter-setting strategies, qubit-mapping techniques to reduce gate counts, and error-mitigation techniques. Experimental results, including on quantum hardware, showcase running time improvements compared with the original classical algorithm. We have implemented our approach in a full software stack that allows the solution of several graph-theoretic problems. This talk is based on joint work with Ieva Cepaite, Niam Vaishnav and Leo Zhou.