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.

arXiv comment30+12 pages, 14 figures, accepted into Quantum

References in corpus (104)

• Elementary gates for quantum computation
• Quantum information with Rydberg atoms
• 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
• Multidimensional quantum entanglement with large-scale integrated optics
• Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum computing with atomic qubits and Rydberg interactions: Progress and challenges
• Parallel implementation of high-fidelity multi-qubit gates with neutral atoms
• Synthetic three-dimensional atomic structures assembled atom by atom
• Experimental Comparison of Two Quantum Computing Architectures
• Qudits and high-dimensional quantum computing
• Quantum computing with neutral atoms
• ARC: An open-source library for calculating properties of alkali Rydberg atoms
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• High-Fidelity Entanglement and Detection of Alkaline-Earth Rydberg Atoms
• Provably-Secure and High-Rate Quantum Key Distribution with Time-Bin Qudits
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Quantum simulation and computing with Rydberg-interacting qubits
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Degenerate Fermi Gases of Ytterbium
• Realization of SU(2)*SU(6) Fermi System
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Analysis of a quantum logic device based on dipole-dipole interactions of optically trapped Rydberg atoms
• Low Depth Quantum Simulation of Electronic Structure
• Quantum Computer Systems for Scientific Discovery
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Quantum-state control in optical lattices
• High-Dimensional Single-Photon Quantum Gates: Concepts and Experiments
• Degenerate Fermi Gas of ${}^{87}$Sr
• Nuclear Spin Effects in Optical Lattice Clocks
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Electro-Optic Frequency Beamsplitters and Tritters for High-Fidelity Photonic Quantum Information Processing
• High-dimensional frequency-bin entangled photons in an optical microresonator on a chip
• Narrow-line cooling and imaging of Ytterbium atoms in an optical tweezer array
• Ultracold polar molecules as qudits
• Robust encoding of a qubit in a molecule
• Reachability Deficits in Quantum Approximate Optimization
• 2000-times repeated imaging of strontium atoms in clock-magic tweezer arrays
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Simultaneous dimerization and SU(4) symmetry breaking of 4-color fermions on the square lattice
• Coherent manipulation of a molecular Ln-based nuclear qudit coupled to an electron qubit
• Experimental Realization of a Quantum Integer-Spin Chain with Controllable Interactions
• Hyperfine quenching of the metastable ${}^3{P}_{0,2}$ states in divalent atoms
• Parameter Concentration in Quantum Approximate Optimization
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Excitation and coherent control of spin qudit modes with sub-MHz spectral resolution
• Three-sublattice order in the SU(3) Heisenberg model on the square and triangular lattice
• Computational speed-up with a single qudit
• Computational speed-up in a single qudit NMR quantum information processor
• MAXCUT QAOA performance guarantees for p >1
• Hybrid quantum-classical algorithms for approximate graph coloring
• Production of quantum degenerate strontium gases: Larger, better, faster, colder
• Enhanced atom-by-atom assembly of arbitrary tweezers arrays
• Scaling the neutral atom Rydberg gate quantum computer by collective encoding in Holmium atoms
• Multistart Methods for Quantum Approximate Optimization
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• On the Universality of the Quantum Approximate Optimization Algorithm
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• Experimental Observation of Tensor Monopoles with a Superconducting Qudit
• Scalable quantum computing with qudits on a graph
• 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
• Preparation of hundreds of microscopic atomic ensembles in optical tweezer arrays
• Parallelism for Quantum Computation with Qudits
• Sustained state-independent quantum contextual correlations from a single ion
• Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA
• The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
• Large Scale Correlation Clustering Optimization
• 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
• Classical and Quantum Bounded Depth Approximation Algorithms
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Competing states in the SU(3) Heisenberg model on the honeycomb lattice: Plaquette valence-bond crystal versus dimerized color-ordered state
• SU(6) Heisenberg model on the honeycomb lattice: competition between plaquette and chiral order
• Quantum fast Fourier transform using multilevel atoms
• A SWAP gate for qudits
• DMRG simulations of SU(N) Heisenberg chains using standard Young tableaux: fundamental representation and comparison with finite-size Bethe ansatz
• Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays
• Exact diagonalization of Heisenberg $SU(N)$ chains in the fully symmetric and antisymmetric representations
• An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer
• Unified Phase Diagram of Antiferromagnetic SU(N) Spin Ladders
• Variational Monte-Carlo investigation of SU($N$) Heisenberg chains
• Heralded creation of photonic qudits from parametric down conversion using linear optics
• Quantum Critical Spin-2 Chain with Emergent SU(3) Symmetry
• Linear Flavor-Wave Theory for Fully Antisymmetric $\mathrm{SU}(N)$ Irreducible Representations
• Structure of Spin Correlations in High Temperature SU($N$) Quantum Magnets
• Limitations of optimization algorithms on noisy quantum devices
• Rényi entanglement entropy of critical SU($N$) spin chains
• Effects of Quantum Noise on Quantum Approximate Optimization Algorithm
• Mott insulators of ultracold fermionic alkaline earth atoms in three dimensions
• Robustness to spontaneous emission of a variational quantum algorithm
• Realization of Universal Quantum Gates with Spin-Qudits in Colloidal Quantum Dots
• Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size
• The frequency of the ultranarrow ${}^1{\text{S}}_0-{}^3{\text{P}}_2$ transition in ${}^{87}\text{Sr}$
• Polynomial scaling of QAOA for ground-state preparation of the fully-connected p-spin ferromagnet
• 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