Enhancement of quantum annealing via <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> -local catalysts

The potential quantum speedup in solving optimization problems via adiabatic quantum annealing is often hindered by the closing of the energy gap during the anneal, especially when this gap scales exponentially with system size. In this work, we alleviate this bottleneck by demonstrating that for the NP-complete Maximum Weighted Independent Set (MWIS) problem, an informed choice of <a:math xmlns:a="http://www.w3.org/1998/Math/MathML"> <a:mi>n</a:mi> </a:math> -local catalysts (operators involving <b:math xmlns:b="http://www.w3.org/1998/Math/MathML"> <b:mi>n</b:mi> </b:math> qubits) can reopen the gap during the annealing process. By analyzing first-order phase transitions in toy instances of the MWIS problem, we first identify direct-tunneling catalysts that effectively eliminate the transition and provide an analytical discussion on when the sign of the catalyst influences its impact. We then reveal that <c:math xmlns:c="http://www.w3.org/1998/Math/MathML"> <c:mi>n</c:mi> </c:math> -local catalysts exponentially improve gap scaling and in certain scenarios are as effective as direct-tunnel coupling between two minima. Utilizing this understanding, we show that they also increase the efficiency of ground-state preparation via adiabatic quantum annealing in random graphs and analytically demonstrate the necessity of their placement across unfrustrated loops in the graph for effective performance in MWIS problems. Additionally, using a circuit implementation of the <d:math xmlns:d="http://www.w3.org/1998/Math/MathML"> <d:mi>n</d:mi> </d:math> -local catalyst (requiring <e:math xmlns:e="http://www.w3.org/1998/Math/MathML"> <e:mrow> <e:mn>2</e:mn> <e:mi>n</e:mi> </e:mrow> </e:math> nearest-neighbor gates), we demonstrate that both the circuit depth and the total number of gates required to solve the problem are reduced by several orders of magnitude when compared to the discrete-time version of traditional quantum annealing using local drivers. Our analysis suggests that nonlocal quantum fluctuations entangling multiple qubits as a catalyst are key to achieving the desired quantum advantage.