Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach

Abstract

We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits, which constitute a natural platform for such non-binary problems. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering, including Hamiltonian formulation of the algorithm, analysis of its performance, identification of a suitable level structure for ${}^{87}\mathrm{Sr}$ and specific gate design. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count. For single layer QAOA, we also prove (conjecture) a lower bound of $0.6367$ ($0.6699$) for the approximation ratio on 3-regular graphs. Our numerical studies evaluate the algorithm's performance by considering complete and Erdős-Rényi graphs of up to 7 vertices and clusters. We find that in all cases the QAOA surpasses the Swamy bound $0.7666$ for the approximation ratio for QAOA depths $p\ge 2$. Finally, by analysing the effect of errors when solving complete graphs we find that their inclusion severely limits the algorithm's performance.

30+12 pages, 14 figures, accepted into Quantum

References in corpus (31)

• A Quantum Approximate Optimization Algorithm
• Many-Body Physics with Individually-Controlled Rydberg Atoms
• An atom-by-atom assembler of defect-free arbitrary 2d atomic arrays
• Probing Topological Spin Liquids on a Programmable Quantum Simulator
• Experimental Comparison of Two Quantum Computing Architectures
• Quantum computing with neutral atoms
• Provably-Secure and High-Rate Quantum Key Distribution with Time-Bin Qudits
• Degenerate Fermi Gases of Ytterbium
• Nuclear Spin Effects in Optical Lattice Clocks
• High-dimensional frequency-bin entangled photons in an optical microresonator on a chip
• 2000-times repeated imaging of strontium atoms in clock-magic tweezer arrays
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Experimental Realization of a Quantum Integer-Spin Chain with Controllable Interactions
• Parameter Concentration in Quantum Approximate Optimization
• Production of quantum degenerate strontium gases: Larger, better, faster, colder
• Enhanced atom-by-atom assembly of arbitrary tweezers arrays
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Quantum approximate optimization is computationally universal
• Exact Diagonalization of Heisenberg SU(N) models
• Simplex solids in SU(N) Heisenberg models on the kagome and checkerboard lattices
• Efficient preparation and detection of microwave dressed-state qubits and qutrits with trapped ions
• Parallelism for Quantum Computation with Qudits
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Determining the parity of a permutation using an experimental NMR qutrit
• A blueprint for fault-tolerant quantum computation with Rydberg atoms
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Variational Monte-Carlo investigation of SU($N$) Heisenberg chains
• Structure of Spin Correlations in High Temperature SU($N$) Quantum Magnets
• Robustness to spontaneous emission of a variational quantum algorithm
• Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size
• Analytic Constructions of General n-Qubit Controlled Gates

Cited by in corpus (25)

• A universal qudit quantum processor with trapped ions
• Hardware efficient quantum simulation of non-abelian gauge theories with qudits on Rydberg platforms
• Proof-of-concept Quantum Simulator based on Molecular Spin Qudits
• Robust control and optimal Rydberg states for neutral atom two-qubit gates
• Narrow-line imaging of single strontium atoms in shallow optical tweezers
• Quantum approximate optimization algorithm for qudit systems
• Qudit entanglers using quantum optimal control
• Pulse based Variational Quantum Optimal Control for hybrid quantum computing
• Qudits for decomposing multiqubit gates and realizing quantum algorithms
• Continuous dynamical decoupling of optical ${}^{171}$Yb${}^{+}$ qudits with radiofrequency fields
• A native measurement-based QAOA algorithm, applied to the MAX K-CUT problem
• Data re-uploading with a single qudit
• Ability of error correlations to improve the performance of variational quantum algorithms
• Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem
• Compilation of Entangling Gates for High-Dimensional Quantum Systems
• Exact Synthesis of Multiqutrit Clifford-Cyclotomic Circuits
• Scaling W state circuits in the qudit Clifford hierarchy
• Quantifying Grover speed-ups beyond asymptotic analysis
• Measurement of the g factor of ground-state 87Sr at the parts-per-million level using co-trapped ultracold atoms
• Qudit vs. Qubit: Simulated performance of error correction codes in higher dimensions
• Barren plateaus are amplified by the dimension of qudits
• Continuous-wave quantum light control via engineered Rydberg-induced dephasing
• Continuous-wave all-optical single-photon transistor based on a Rydberg-atom ensemble
• Entanglement swapping for partially entangled qudits and the role of quantum complementarity
• Transversal AND in Quantum Codes