Quantum Programming of the Satisfiability Problem with Rydberg Atom Graphs
arXiv:2302.14369 · doi:10.1103/PhysRevResearch.5.043037
Abstract
Finding a quantum computing method to solve nondeterministic polynomial time (NP)-complete problems is currently of paramount importance in quantum information science. Here an experiment is presented to demonstrate the use of Rydberg atoms to solve (i.e., to program and obtain the solution of) the satisfiability (3-SAT) problem, which is the prototypical NP-complete problem allowing general programming of all NP problems. Boolean expressions of the 3-SAT problem are programmed with the blockade interactions of Rydberg atom graphs and their many-body ground states are experimentally obtained, to determine the satisfiabilities of the given 3-SAT problem instances quantum mechanically.
arXiv comment6 pages, 4 figures
References in corpus (18)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum Mechanics helps in searching for a needle in a haystack
- Ising formulations of many NP problems
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
- Programmable Quantum Simulations of Spin Systems with Trapped Ions
- Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Analysis of imperfections in the coherent optical excitation of single atoms to Rydberg states
- Quantum optimization with arbitrary connectivity using Rydberg atom arrays
- Knowledge and ignorance in incomplete quantum state tomography
- Experimental Performance of a Quantum Simulator: Optimizing Adiabatic Evolution and Identifying Many-Body Ground States
- Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
- Coherent and dissipative dynamics of entangled few-body systems of Rydberg atoms
- Quantum criticality of two-dimensional quantum magnets with long-range interactions
- Quantum simulation of Ising spins on Platonic graphs
- Adiabatic Spectroscopy and a Variational Quantum Adiabatic Algorithm
- Programmable Quantum Annealing Architectures with Ising Quantum Wires
Cited by in corpus (8)
- Rydberg superatoms: An artificial quantum system for quantum information processing and quantum optics
- A Rydberg-atom approach to the integer factorization problem
- Quantum Optimization on Rydberg Atom Arrays with Arbitrary Connectivity: Gadgets Limitations and a Heuristic Approach
- Replica symmetry breaking in spin glasses in the replica-free Keldysh formalism
- Topological order in symmetric blockade structures
- Krylov Spread Complexity of Quantum-Walks
- Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array
- A quantum wire approach to weighted combinatorial graph optimisation problems