A Quantum N-Queens Solver
arXiv:1803.00735 · doi:10.22331/q-2019-06-03-149
Abstract
The N-queens problem is to find the position of N queens on an N by N chess board such that no queens attack each other. The excluded diagonals N-queens problem is a variation where queens cannot be placed on some predefined fields along diagonals. This variation is proven NP-complete and the parameter regime to generate hard instances that are intractable with current classical algorithms is known. We propose a special purpose quantum simulator that implements the excluded diagonals N-queens completion problem using atoms in an optical lattice and cavity-mediated long-range interactions. Our implementation has no overhead from the embedding allowing to directly probe for a possible quantum advantage in near term devices for optimization problems.
arXiv comment22 pages, 8 figures
References in corpus (41)
- Quantum Computing in the NISQ era and beyond
- Cold bosonic atoms in optical lattices
- Quantum Simulation
- Probing many-body dynamics on a 51-atom quantum simulator
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- Adiabatic Quantum Computing
- A quantum gas microscope - detecting single atoms in a Hubbard regime optical lattice
- Single-Atom Resolved Fluorescence Imaging of an Atomic Mott Insulator
- Characterizing Quantum Supremacy in Near-Term Devices
- Cold atoms in cavity-generated dynamical optical potentials
- Quantum Computational Supremacy
- Quantum annealing with more than one hundred qubits
- Quantum computing with atomic qubits and Rydberg interactions: Progress and challenges
- Observation of mesoscopic crystalline structures in a two-dimensional Rydberg gas
- Quantum phases from competing short- and long-range interactions in an optical lattice
- Cavity Nonlinear Optics at Low Photon Numbers from Collective Atomic Motion
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- Tunable-range, photon-mediated atomic interactions in multimode cavity QED
- QuantumOptics.jl: A Julia framework for simulating open quantum systems
- Cold atom dynamics in a quantum optical lattice potential
- Frustration and glassiness in spin models with cavity-mediated interactions
- Ultracold atoms in optical lattices generated by quantized light fields
- Bose-glass phases of ultracold atoms due to cavity backaction
- Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
- Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass
- Quantum Annealing for Constrained Optimization
- Observation of many-body long-range tunneling after a quantum quench
- A Coherent Quantum Annealer with Rydberg Atoms
- REVIEW. Quantum optics with ultracold quantum gases: towards the full quantum regime of the light-matter interaction
- Accurate mapping of multilevel Rydberg atoms on interacting spin- particles for the quantum simulation of Ising models
- QND measurements and state preparation in quantum gases by light detection
- On the Computational Complexity of Curing the Sign Problem
- Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
- Stabilisers as a design tool for new forms of Lechner-Hauke-Zoller Annealer
- Quantum annealing with ultracold atoms in a multimode optical resonator
- Quantum simulators based on the global collective light-matter interaction
- Scalable effective temperature reduction for quantum annealers via nested quantum annealing correction
- Two-local qubit Hamiltonians: when are they stoquastic?
- Self-ordering dynamics of ultracold atoms in multicolored cavity fields
- Realizable Quantum Adiabatic Search
Cited by in corpus (15)
- Perspectives of quantum annealing: Methods and implementations
- Cavity QED with Quantum Gases: New Paradigms in Many-Body Physics
- Super-radiant and Sub-radiant Cavity Scattering by Atom Arrays
- Entanglement and replica symmetry breaking in a driven-dissipative quantum spin glass
- Non-Markovian Quantum Dynamics in Strongly Coupled Multimode Cavities Conditioned on Continuous Measurement
- Emergent Quasicrystalline Symmetry in Light-Induced Quantum Phase Transitions
- Quantum Metropolis Solver: A Quantum Walks Approach to Optimization Problems
- Unraveling the origin of higher success probabilities in quantum versus semi-classical annealing
- Spectral theory of non-Markovian dissipative phase transitions
- Optomechanical self-organization in a mesoscopic atom array
- Genuine Quantum effects in Dicke-type Models at large atom numbers
- Self-ordering and cavity cooling using a train of ultrashort pulses
- The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
- Effect of Quantum Statistics on Computational Power of Atomic Quantum Annealers
- Stochastic Schrödinger equation for a homodyne measurement setup of strongly correlated systems