Towards large-scale quantum optimization solvers with few qubits

Abstract

Quantum computers hold the promise of more efficient combinatorial optimization solvers, which could be game-changing for a broad range of applications. However, a bottleneck for materializing such advantages is that, in order to challenge classical algorithms in practice, mainstream approaches require a number of qubits prohibitively large for near-term hardware. Here we introduce a variational solver for MaxCut problems over <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>m</mml:mi> <mml:mo>=</mml:mo> <mml:mi>O</mml:mi> <mml:mrow><mml:mo>(</mml:mo> <mml:mrow> <mml:msup><mml:mrow><mml:mi>n</mml:mi></mml:mrow> <mml:mrow><mml:mi>k</mml:mi></mml:mrow> </mml:msup> </mml:mrow> <mml:mo>)</mml:mo></mml:mrow> </mml:math> binary variables using only n qubits, with tunable k > 1. The number of parameters and circuit depth display mild linear and sublinear scalings in m, respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. Altogether, this leads to high quantum-solver performances. For instance, for m = 7000, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for m = 2000, experiments with n = 17 trapped-ion qubits feature MaxCut approximation ratios estimated to be beyond the hardness threshold 0.941. Our findings offer an interesting heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near-term quantum devices.