Low-depth Clifford circuits approximately solve MaxCut

Manuel H. Muñoz-Arias; Stefanos Kourtis; Alexandre Blais

doi:10.1103/PhysRevResearch.6.023294

paper

Low-depth Clifford circuits approximately solve MaxCut

arXiv:2310.15022 · doi:10.1103/PhysRevResearch.6.023294

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, \emph{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 $N$ -vertex graph by building a depth $O (N)$ Clifford circuit. The algorithm has runtime complexity $O (N^{2})$ and $O (N^{3})$ for sparse and dense graphs, respectively, and space complexity $O (N^{2})$ , 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 $\sim 94%$ 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.

Revised version, several typos corrected, extended appendices

Low-depth Clifford circuits approximately solve MaxCut

Abstract

References in corpus (40)

Cited by in corpus (8)