Speedup of high-order unconstrained binary optimization using quantum Z2 lattice gauge theory

Abstract

How to quickly solve the problem of high-order unconstrained binary optimization (HUBO)? This problem has attracted much attention because of its importance and wide-range applications. Here we present a quantum algorithm and its corresponding quantum-inspired classical algorithm for this problem, and achieve algorithmic speedup by using gauge symmetry. Specifically we map the HUBO problem to quantum Z2 lattice gauge theory defined on the dual graph, and propose the so-called gauged local quantum annealing (gLQA), which is the local quantum annealing (LQA) protected by the gauge symmetry. By running the quantum-inspired classical algorithm, we demonstrate that gLQA reduces the computational time by one order of magnitude from that of LQA.