Low-depth Clifford circuits approximately solve MaxCut
- URL: http://arxiv.org/abs/2310.15022v3
- Date: Sun, 9 Jun 2024 18:15:47 GMT
- Title: Low-depth Clifford circuits approximately solve MaxCut
- Authors: Manuel H. Muñoz-Arias, Stefanos Kourtis, Alexandre Blais,
- Abstract summary: We introduce a quantum-inspired approximation algorithm for MaxCut based on low-depth Clifford circuits.
Our algorithm finds an approximate solution of MaxCut on an $N$-vertex graph by building a depth $O(N)$ Clifford circuit.
- Score: 44.99833362998488
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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 $\sim94\%$ 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.
Related papers
- Laplace expansions and tree decompositions: polytime algorithm for shallow nearest-neighbour Boson Sampling [0.30693357740321775]
In a Boson Sampling quantum optical experiment we send $n$ individual photons into an $m$-mode interferometer and we measure the occupation pattern on the output.
We exploit the fact that for a nearest-neighbour shallow circuit, i.e. depth depth $D = mathcalO(log m)$, one can adapt the algorithm by Cifuentes & Parrilo to exploit the sparsity of the shallow interferometer.
arXiv Detail & Related papers (2024-12-24T19:34:26Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem.
We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
arXiv Detail & Related papers (2024-06-11T04:40:05Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
We compare 8 popular numerical black-box optimization algorithms on the $L_infty$ star discrepancy problem.
We show that all used solvers perform very badly on a large majority of the instances.
We suspect that state-of-the-art numerical black-box optimization techniques fail to capture the global structure of the problem.
arXiv Detail & Related papers (2023-06-29T14:57:56Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
We show the first tight characterization of the optimal Hessian-dependent sample complexity.
A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances.
The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
arXiv Detail & Related papers (2023-06-21T17:03:22Z) - A graph-state based synthesis framework for Clifford isometries [2.048226951354646]
We tackle the problem of synthesizing a Clifford isometry into an executable quantum circuit.
We propose a simple framework for synthesis that exploits the elementary properties of the Clifford group and one equation of the symplectic group.
We also propose practical synthesis algorithms for Clifford isometries with a focus on Clifford operators, graph states and codiagonalization of Pauli rotations.
arXiv Detail & Related papers (2022-12-13T22:50:24Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution.
We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines.
Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
arXiv Detail & Related papers (2022-05-24T03:49:10Z) - The Quantum Approximate Optimization Algorithm at High Depth for MaxCut
on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model [0.0]
The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to optimization problems.
We give an iterative formula to evaluate performance for any $D$ at any depth $p$.
We make an optimistic conjecture that the QAOA, as $p$ goes to infinity, will achieve the Parisi value.
arXiv Detail & Related papers (2021-10-27T06:35:59Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits.
Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering.
We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
arXiv Detail & Related papers (2021-06-22T11:07:38Z) - 6-qubit Optimal Clifford Circuits [8.024778381207128]
Clifford group elements can be used to perform magic state distillation and form randomized benchmarking protocols.
Finding short circuits is a hard problem; despite Clifford group being finite, its size grows quickly with the number of qubits.
We show how to extract arbitrary optimal 6-qubit Clifford circuit in $0.0009358$ and $0.0006274$ seconds using consumer- and enterprise-grade computers.
arXiv Detail & Related papers (2020-12-11T01:33:17Z) - Hadamard-free circuits expose the structure of the Clifford group [9.480212602202517]
The Clifford group plays a central role in quantum randomized benchmarking, quantum tomography, and error correction protocols.
We show that any Clifford operator can be uniquely written in the canonical form $F_HSF$.
A surprising connection is highlighted between random uniform Clifford operators and the Mallows distribution on the symmetric group.
arXiv Detail & Related papers (2020-03-20T17:51:36Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.