Low-depth Clifford circuits approximately solve MaxCut

Abstract

We introduce a quantum-inspired approximation algorithm for MaxCut based on low-depth Clifford circuits. We start by showing that the solution unitaries found by the adaptive quantum approximation optimization algorithm (ADAPT-QAOA) for the MaxCut problem on weighted fully connected graphs are (almost) Clifford circuits. Motivated by this observation, we devise an approximation algorithm for MaxCut, ADAPT-Clifford, that searches through the Clifford manifold by combining a minimal set of generating elements of the Clifford group. Our algorithm finds an approximate solution of MaxCut on an <a:math xmlns:a="http://www.w3.org/1998/Math/MathML"><a:mi>N</a:mi></a:math>-vertex graph by building a depth <b:math xmlns:b="http://www.w3.org/1998/Math/MathML"><b:mrow><b:mi>O</b:mi><b:mo>(</b:mo><b:mi>N</b:mi><b:mo>)</b:mo></b:mrow></b:math> Clifford circuit. The algorithm has runtime complexity <c:math xmlns:c="http://www.w3.org/1998/Math/MathML"><c:mrow><c:mi>O</c:mi><c:mo>(</c:mo><c:msup><c:mi>N</c:mi><c:mn>2</c:mn></c:msup><c:mo>)</c:mo></c:mrow></c:math> and <d:math xmlns:d="http://www.w3.org/1998/Math/MathML"><d:mrow><d:mi>O</d:mi><d:mo>(</d:mo><d:msup><d:mi>N</d:mi><d:mn>3</d:mn></d:msup><d:mo>)</d:mo></d:mrow></d:math> for sparse and dense graphs, respectively, and space complexity <e:math xmlns:e="http://www.w3.org/1998/Math/MathML"><e:mrow><e:mi>O</e:mi><e:mo>(</e:mo><e:msup><e:mi>N</e:mi><e:mn>2</e:mn></e:msup><e:mo>)</e:mo></e:mrow></e:math>, with improved solution quality achieved at the expense of more demanding runtimes. We implement ADAPT-Clifford and characterize its performance on graphs with positive and signed weights. The case of signed weights is illustrated with the paradigmatic Sherrington-Kirkpatrick model, for which our algorithm finds solutions with ground-state mean energy density corresponding to <f:math xmlns:f="http://www.w3.org/1998/Math/MathML"><f:mrow><f:mo>∼</f:mo><f:mn>94</f:mn><f:mo>%</f:mo></f:mrow></f:math> of the Parisi value in the thermodynamic limit. The case of positive weights is investigated by comparing the cut found by ADAPT-Clifford with the cut found with the Goemans-Williamson (GW) algorithm. For both sparse and dense instances we provide copious evidence that, up to hundreds of nodes, ADAPT-Clifford finds cuts of lower energy than GW. Published by the American Physical Society 2024

Topics & Concepts