Number Partitioning with Grover's Algorithm in Central Spin Systems

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.

23 pages, 13 figures, typos corrected, edits for clarity

References in corpus (11)

• Strong atom-field coupling for Bose-Einstein condensates in an optical cavity on a chip
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• High-speed linear optics quantum computing using active feed-forward
• Operating Quantum States in Single Magnetic Molecules: Implementation of Grover's Quantum Algorithm
• Coherent many-body spin dynamics in a long-range interacting Ising chain
• Deterministic entanglement of two neutral atoms via Rydberg blockade
• Transverse-Field Ising Dynamics in a Rydberg-Dressed Atomic Gas
• Anyonic interferometry and protected memories in atomic spin lattices
• Implementing Grover's Quantum Search on a Para-Hydrogen based Pure State NMR Quantum Computer
• Arbitrary Dicke-State Control of Symmetric Rydberg Ensembles
• 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