Dynamic adaptive quantum approximate optimization algorithm for shallow, noise-resilient circuits

Abstract

The quantum approximate optimization algorithm (QAOA) is an appealing proposal to solve NP problems on noisy intermediate-scale quantum (NISQ) hardware. Making NISQ implementations of the QAOA resilient to noise requires short ansatz circuits with as few controlled- () gates as possible. Here we present the dynamic adaptive quantum approximate optimization algorithm (Dynamic-ADAPT-QAOA). Our algorithm significantly reduces the circuit depth and the count of standard ADAPT-QAOA, a leading proposal for near-term implementations of the QAOA. Throughout our algorithm, the decision to apply -intensive operations is made dynamically, based on algorithmic benefits. Using density-matrix simulations, we benchmark the noise resilience of ADAPT-QAOA and Dynamic-ADAPT-QAOA. We compute the gate-error probability <a:math xmlns:a="http://www.w3.org/1998/Math/MathML"><a:msubsup><a:mi>p</a:mi><a:mrow><a:mtext>gate</a:mtext></a:mrow><a:mi>★</a:mi></a:msubsup></a:math> below which these algorithms provide, on average, more accurate solutions than the classical, polynomial-time approximation algorithm by Goemans and Williamson. For small systems with six to ten qubits, we show that <b:math xmlns:b="http://www.w3.org/1998/Math/MathML"><b:mrow><b:msubsup><b:mi>p</b:mi><b:mrow><b:mtext>gate</b:mtext></b:mrow><b:mi>★</b:mi></b:msubsup><b:mo>&gt;</b:mo><b:msup><b:mn>10</b:mn><b:mrow><b:mo>−</b:mo><b:mn>3</b:mn></b:mrow></b:msup></b:mrow></b:math> for Dynamic-ADAPT-QAOA. Compared to standard ADAPT-QAOA, this constitutes an order-of-magnitude improvement in noise resilience. This improvement should make Dynamic-ADAPT-QAOA viable for implementations on superconducting NISQ hardware, even in the absence of error mitigation. Published by the American Physical Society 2024

Topics & Concepts