Low-depth Clifford circuits approximately solve MaxCut

Manuel H. Muñoz-Arias

doi:10.1103/PhysRevResearch.6.023294

2024-06-20

Manuel H. Muñoz-Arias *

Stefanos Kourtis

Alexandre Blais

DOI：10.1103/PhysRevResearch.6.023294

原文链接

原文求助

摘要

En 中文

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 N-vertex graph by building a depth O(N) Clifford circuit. The algorithm has runtime complexity O(N2) and O(N3) for sparse and dense graphs, respectively, and space complexity O(N2), 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 similar to 94% of the Parisi value in the thermodynamic limit. The case of positive weights is investigated by comparing the cut found by ADAPTClifford 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.

Keyword:

POLYNOMIAL-TIME APPROXIMATION

MAXIMUM CUT

HEURISTICS

INSTANCES