Large-scale quantum annealing simulation with tensor networks and belief propagation

Quantum annealing and quantum approximate optimization algorithms hold a great potential to speed-up optimization problems. This could be game-changing for a plethora of applications. Yet, in order to hope to beat classical solvers, quantum circuits must scale up to sizes and performances much beyond current hardware. In that quest, intense experimental effort has been recently devoted to optimizations on 3-regular graphs, which are computationally hard but experimentally relatively amenable. However, even there, the amount and quality of quantum resources required for quantum solvers to outperform classical ones is unclear. Here, we show that quantum annealing for 3-regular graphs can be classically simulated even at scales of 1000 qubits and 5000000 two-qubit gates with all-to-all connectivity. To this end, we develop a graph tensor-network quantum annealer (GTQA) able of high-precision simulations of Trotterized circuits of near-adiabatic evolutions. Based on a recently proposed belief-propagation technique for tensor canonicalization, GTQA is equipped with re-gauging and truncation primitives that keep approximation errors small in spite of the circuits generating significant amounts of entanglement. As a result, even with a maximal bond dimension as low as 4, GTQA produces solutions competitive with those of state-of-the-art classical solvers. For non-degenerate instances, the unique solution can be read out from the final reduced single-qubit states. In contrast, for degenerate problems, such as MaxCut, we introduce an approximate measurement simulation algorithm for graph tensor-network states. On one hand, our findings showcase the potential of GTQA as a powerful quantum-inspired optimizer. On the other hand, they considerably raise the bar required for experimental demonstrations of quantum speed-ups in combinatorial optimizations.