Atom Cavity Encoding for NP-Complete Problems

Abstract

We consider an atom-cavity system having long-range atomic interactions mediated by cavity modes. It has been shown that quantum simulations of spin models with this system can naturally be used to solve number partition problems. Here, we present encoding schemes for numerous NP-complete problems, encompassing the majority of Karp's 21 NP-complete problems. We find a number of such computation problems can be encoded by the atom-cavity system at a linear cost of atom number. There are still certain problems that cannot be encoded by the atom-cavity as efficiently, such as quadratic unconstrained binary optimization (QUBO), and the Hamiltonian cycle. For these problems, we provide encoding schemes with a quadratic or quartic cost in the atom number. We expect this work to provide important guidance to search for the practical quantum advantage of the atom-cavity system in solving NP-complete problems. Moreover, the encoding schemes we develop here may also be adopted in other optical systems for solving NP-complete problems, where a similar form of Mattis-type spin glass Hamiltonian as in the atom-cavity system can be implemented.

25 pages, 1 table

References in corpus (34)

• Variational Quantum Algorithms
• Ising formulations of many NP problems
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Circuit Quantum Electrodynamics
• Adiabatic Quantum Computing
• Shortcuts to adiabaticity: concepts, methods, and applications
• A rigorous and robust quantum speed-up in supervised machine learning
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Large-scale photonic Ising machine by spatial light modulation
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Warm-starting quantum optimization
• Programmable Interactions and Emergent Geometry in an Atomic Array
• Resource-Efficient Quantum Algorithm for Protein Folding
• Quantum optimization with arbitrary connectivity using Rydberg atom arrays
• Shortcuts to Adiabaticity in Digitized Adiabatic Quantum Computing
• Modernizing Quantum Annealing using Local Searches
• A Coherent Quantum Annealer with Rydberg Atoms
• Quantum-enhanced Markov chain Monte Carlo
• Dynamics of reverse annealing for the fully-connected $p$-spin model
• Quantum simulation of Ising spins on Platonic graphs
• Adiabatic Spectroscopy and a Variational Quantum Adiabatic Algorithm
• Programmable Quantum Annealing Architectures with Ising Quantum Wires
• Antiferromagnetic spatial photonic Ising machine through optoelectronic correlation computing
• Quantum Adiabatic Algorithm Design using Reinforcement Learning
• Quadrature Photonic Spatial Ising Machine
• Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
• Universal Quantum Computation in Globally Driven Rydberg Atom Arrays
• Rydberg blockade based parity quantum optimization
• Number Partitioning with Grover's Algorithm in Central Spin Systems
• Hybrid Quantum Annealing via Molecular Dynamics
• Tuneable spin-glass optical simulator based on multiple light scattering
• Solving optimization problems with local light shift encoding on Rydberg quantum annealers
• Universal Quantum Optimization with Cold Atoms in an Optical Cavity
• Hard instance learning for quantum adiabatic prime factorization