Approximating maximum independent set on Rydberg atom arrays using local detunings
arXiv:2402.09180 · doi:10.1002/qute.202400291
Abstract
Rydberg atom arrays operated by a quantum adiabatic principle are among the most promising quantum simulating platforms due to their scalability and long coherence time. From the perspective of combinatorial optimization, they offer an efficient solution for an intrinsic maximum independent set problem because of the resemblance between the Rydberg Hamiltonian and the cost function of the maximum independent set problem. In this study, a strategy is suggested to approximate maximum independent sets by adjusting local detunings on the Rydberg Hamiltonian according to each vertex's vertex support, which is a quantity that represents connectivity between vertices. By doing so, the strategy successfully reduces the error rate three times for the checkerboard graphs with defects when the adiabaticity is sufficient. In addition, the strategy decreases the error rate for random graphs even when the adiabaticity is relatively insufficient. Moreover, it is shown that the strategy helps to prepare a quantum many-body ground state by raising the fidelity between the evolved quantum state and a 2D cat state on a square lattice. Finally, the strategy is combined with the non-abelian adiabatic mixing and this approach is highly successful in finding maximum independent sets compared to the conventional adiabatic evolution with local detunings.
References in corpus (31)
- Probing many-body dynamics on a 51-atom quantum simulator
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Adiabatic Quantum Computing
- Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
- Realizing quantum Ising models in tunable two-dimensional arrays of single Rydberg atoms
- Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Generation and manipulation of Schrödinger cat states in Rydberg atom arrays
- Quantum Search by Local Adiabatic Evolution
- 10-qubit entanglement and parallel logic operations with a superconducting circuit
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- An overview of the transmission capacity of wireless networks
- Deterministic creation of entangled atom-light Schrödinger-cat states
- A concise review of Rydberg atom based quantum computation and quantum simulation
- Breeding the optical Schroedinger's cat state
- Consistency of the Adiabatic Theorem
- Quantum Speedup by Quantum Annealing
- Quantum optimization with arbitrary connectivity using Rydberg atom arrays
- The quantitative condition is necessary in guaranteeing the validity of the adiabatic approximation
- Experimental Performance of a Quantum Simulator: Optimizing Adiabatic Evolution and Identifying Many-Body Ground States
- Quantum-Enhanced Greedy Combinatorial Optimization Solver
- Solving optimization problems with Rydberg analog quantum computers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks
- Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
- Breaking the quantum adiabatic speed limit by jumping along geodesics
- Adiabatic theorem revisited: the unexpectedly good performance of adiabatic passage
- Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization
- Solving optimization problems with local light shift encoding on Rydberg quantum annealers
- Quantum independent set problem and non-abelian adiabatic mixing
- Quantum Algorithm for Approximating Maximum Independent Sets
- Adiabatic quantum simulations with driven superconducting qubits
- Adiabatically controlled motional states of a ground-state cooled CaO and Ca trapped ion chain