Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints

Abstract

Semidefinite programs are optimization methods with a wide array of applications, such as approximating difficult combinatorial problems. One such semidefinite program is the Goemans-Williamson algorithm, a popular integer relaxation technique. We introduce a variational quantum algorithm for the Goemans-Williamson algorithm that uses only <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>+</mml:mo></mml:mrow><mml:mn>1</mml:mn></mml:math> qubits, a constant number of circuit preparations, and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>poly</mml:mtext><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> expectation values in order to approximately solve semidefinite programs with up to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi><mml:mo>=</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mi>n</mml:mi></mml:msup></mml:math> variables and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>M</mml:mi><mml:mo>&amp;#x223C;</mml:mo><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>N</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> constraints. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit, a technique known as the Hadamard Test. The Hadamard Test enables us to optimize the objective function by estimating only a single expectation value of the ancilla qubit, rather than separately estimating exponentially many expectation values. Similarly, we illustrate that the semidefinite programming constraints can be effectively enforced by implementing a second Hadamard Test, as well as imposing a polynomial number of Pauli string amplitude constraints. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems, including MaxCut. Our method exceeds the performance of analogous classical methods on a diverse subset of well-studied MaxCut problems from the GSet library.