Number Partitioning with Grover's Algorithm in Central Spin Systems
arXiv:2009.05549 · doi:10.1103/PRXQuantum.2.020319
Abstract
Numerous conceptually important quantum algorithms rely on a black-box device known as an oracle, which is typically difficult to construct without knowing the answer to the problem that the algorithm is intended to solve. A notable example is Grover's search algorithm. Here we propose a Grover search for solutions to a class of NP-complete decision problems known as subset sum problems, including the special case of number partitioning. Each problem instance is encoded in the couplings of a set of qubits to a central spin or boson, which enables a realization of the oracle without knowledge of the solution. The algorithm provides a quantum speedup across a known phase transition in the computational complexity of the partition problem, and we identify signatures of the phase transition in the simulated performance. Whereas the naive implementation of our algorithm requires a spectral resolution that scales exponentially with system size for NP-complete problems, we also present a recursive algorithm that enables scalability. We propose and analyze implementation schemes with cold atoms, including Rydberg-atom and cavity-QED platforms.
arXiv comment23 pages, 13 figures, typos corrected, edits for clarity
References in corpus (58)
- Quantum Mechanics helps in searching for a needle in a haystack
- Strengths and Weaknesses of Quantum Computing
- Experimental One-Way Quantum Computing
- Tight bounds on quantum searching
- Entanglement of two individual neutral atoms using Rydberg blockade
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Strong atom-field coupling for Bose-Einstein condensates in an optical cavity on a chip
- Quantum jumps of light recording the birth and death of a photon in a cavity
- Grover's quantum searching algorithm is optimal
- Parallel implementation of high-fidelity multi-qubit gates with neutral atoms
- Defining and detecting quantum speedup
- Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer
- Experimental Demonstration of Blind Quantum Computing
- ARC: An open-source library for calculating properties of alkali Rydberg atoms
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- High-Fidelity Entanglement and Detection of Alkaline-Earth Rydberg Atoms
- High-speed linear optics quantum computing using active feed-forward
- Operating Quantum States in Single Magnetic Molecules: Implementation of Grover's Quantum Algorithm
- Many-body interferometry of a Rydberg-dressed spin lattice
- Entangling Atomic Spins with a Strong Rydberg-Dressed Interaction
- Soundness and completeness of quantum root-mean-square errors
- Complete 3-Qubit Grover Search on a Programmable Quantum Computer
- Coherent many-body spin dynamics in a long-range interacting Ising chain
- Entanglement with Negative Wigner Function of Three Thousand Atoms Heralded by One Photon
- Phase Transition in the Number Partitioning Problem
- Implementation of Grover's Quantum Search Algorithm in a Scalable System
- Deterministic entanglement of two neutral atoms via Rydberg blockade
- Hardware-efficient quantum random access memory with hybrid quantum acoustic systems
- Grover's search algorithm: An optical approach
- Efficient multiparticle entanglement via asymmetric Rydberg blockade
- Near-optimal quantum circuit for Grover's unstructured search using a transverse field
- Towards quantum simulation with circular Rydberg atoms
- Microscopy of a scalable superatom
- Random access quantum information processors
- Photon-Mediated Quantum Gate between Two Trapped Neutral Atoms in an Optical Cavity
- Transverse-Field Ising Dynamics in a Rydberg-Dressed Atomic Gas
- Deterministic generation of multiparticle entanglement by quantum Zeno dynamics
- Implementation of a three-quantum-bit search algorithm
- Anyonic interferometry and protected memories in atomic spin lattices
- Random Costs in Combinatorial Optimization
- Two-Atom Rydberg Blockade using Direct 6S to nP Excitation
- Carving complex many-atom entangled states by single-photon detection
- Superconducting circuit quantum computing with nanomechanical resonators as storage
- A programmable two-qubit solid-state quantum processor under ambient conditions
- Asymmetric blockade and multi-qubit gates via dipole-dipole interactions
- Variationally Learning Grover's Quantum Search Algorithm
- Efficient Grover search with Rydberg blockade
- Protecting Spin Coherence in a Tunable Heisenberg Model
- Free-Space Quantum Electrodynamics with a single Rydberg superatom
- Quantum Rydberg Central Spin Model
- Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays
- Implementing Grover's Quantum Search on a Para-Hydrogen based Pure State NMR Quantum Computer
- Quantum Sampling Algorithms for Near-Term Devices
- A tunable High-Q millimeter wave cavity for hybrid circuit and cavity QED experiments
- The Grover search as a naturally occurring phenomenon
- Arbitrary Dicke-State Control of Symmetric Rydberg Ensembles
- Painting Non-Classical States of Spin or Motion with Shaped Single Photons
- Improved quantum algorithm for the random subset sum problem
Cited by in corpus (20)
- Programmable Interactions and Emergent Geometry in an Atomic Array
- Tweezer-programmable 2D quantum walks in a Hubbard-regime lattice
- Quantum approximate optimization algorithm for qudit systems
- Universal Quantum Optimization with Cold Atoms in an Optical Cavity
- Quantum simulation of the central spin model with a Rydberg atom and polar molecules in optical tweezers
- Non-Gaussian dynamics of quantum fluctuations and mean-field limit in open quantum central spin systems
- Optomechanical self-organization in a mesoscopic atom array
- Efficient preparation of entangled states in cavity QED with Grover's algorithm
- A many-body singlet prepared by a central spin qubit
- Topologically protected Grover's oracle for the partition problem
- Entanglement Dynamics between Ising Spins and a Central Ancilla
- Optimal spatial searches with long-range tunneling
- Grover's search meets Ising models: a quantum algorithm for finding low-energy states
- Atom Cavity Encoding for NP-Complete Problems
- Revisiting semiconductor bulk hamiltonians using quantum computers
- Deterministic carving of quantum states with Grover's algorithm
- Quantum mutual information redistribution by Number Partitioning algorithm
- Generalized Parity Measurements and Efficient Large Multi-component Cat State Preparation with Quantum Signal Processing
- Phases and phase transition in Grover's algorithm with systematic noise
- Large-scale Sustainable Search on Unconventional Computing Hardware