Towards large-scale quantum optimization solvers with few qubits

Combinatorial optimizations are a major promise of quantum computation, but practical applicability before fault-tolerant devices appear is unclear. For example, classical algorithms based on tensor networks and belief propagation can simulate relevant large-scale quantum annealing processes, which I will briefly touch upon during the talk’s introduction. The main bulk of the talk will however be centered around methods to reduce the experimental requirements for near-term quantum solvers. First, I will discuss a variational quantum solver for binary optimizations of size m polynomially larger than the number of qubits n used. This features several technical advantages that lead to unprecedented performances. For instance, m=7000, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for m=2000 vertices, experiments with n=17 trapped-ion qubits feature MaxCut approximation ratios beyond the hardness threshold 0.941. To our knowledge, this is the highest quality attained via any quantum experiment at such sizes. Second, going beyond MaxCut, I will touch upon constrained optimizations. Solving these with quantum solvers require first reducing them to Quadratic Unconstraint Binary Optimizations (QUBOs). However, finding ‘good' QUBO reformulations is itself in general hard. Thus, I will present an efficient classical algorithm for QUBO reformulations with significant advantages in terms of Hamiltonian spectral properties. For portfolio optimization, for instance, the quantum runtime using the novel reformulation is orders of magnitude smaller than with existing approaches. Our findings offer novel heuristics for quantum-inspired solvers as well as a promising route towards styding quantum solvers at commercially-relevant scales on near term quantum devices.