Probing Entanglement in Adiabatic Quantum Optimization with Trapped Ions
arXiv:1411.7933 · doi:10.3389/fphy.2015.00021
Abstract
Adiabatic quantum optimization has been proposed as a route to solve NP-complete problems, with a possible quantum speedup compared to classical algorithms. However, the precise role of quantum effects, such as entanglement, in these optimization protocols is still unclear. We propose a setup of cold trapped ions that allows one to quantitatively characterize, in a controlled experiment, the interplay of entanglement, decoherence, and non-adiabaticity in adiabatic quantum optimization. We show that, in this way, a broad class of NP-complete problems becomes accessible for quantum simulations, including the knapsack problem, number partitioning, and instances of the max-cut problem. Moreover, a general theoretical study reveals correlations of the success probability with entanglement at the end of the protocol. From exact numerical simulations for small systems and linear ramps, however, we find no substantial correlations with the entanglement during the optimization. For the final state, we derive analytically a universal upper bound for the success probability as a function of entanglement, which can be measured in experiment. The proposed trapped-ion setups and the presented study of entanglement address pertinent questions of adiabatic quantum optimization, which may be of general interest across experimental platforms.
arXiv commentv1: 10 pages+appendix, 6 figures. v2: added explanations; accepted in Frontiers in Physics, Research Topic on Useful Quantum Simulators
References in corpus (37)
- Ising formulations of many NP problems
- QuTiP 2: A Python framework for the dynamics of open quantum systems
- The logarithmic negativity: A full entanglement monotone that is not convex
- Quantum computation with ions in thermal motion
- Engineered 2D Ising interactions on a trapped-ion quantum simulator with hundreds of spins
- Effective quantum spin systems with ion traps
- Entanglement, Non-linear Dynamics, and the Heisenberg Limit
- Quantum annealing with more than one hundred qubits
- Non-local propagation of correlations in long-range interacting quantum systems
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Search by Local Adiabatic Evolution
- Universal digital quantum simulation with trapped ions
- Defining and detecting quantum speedup
- Emergence and Frustration of Magnetic Order with Variable-Range Interactions in a Trapped Ion Quantum Simulator
- Ion-trap quantum logic using long-wavelength radiation
- Experimental signature of programmable quantum annealing
- Anderson localization casts clouds over adiabatic quantum optimization
- Microscopic diagonal entropy and its connection to basic thermodynamic relations
- Experimental implementation of an adiabatic quantum optimization algorithm
- Quantum Simulation of Spin Models on an Arbitrary Lattice with Trapped Ions
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- Designer Spin Pseudomolecule Implemented with Trapped Ions in a Magnetic Gradient
- Thermally assisted adiabatic quantum computation
- Optimal Surface-Electrode Trap Lattices for Quantum Simulation with Trapped Ions
- Experimental determination of Ramsey numbers
- Tunable spin-spin interactions and entanglement of ions in separate wells
- Laserless trapped-ion quantum simulations without spontaneous scattering using microtrap arrays
- Measuring entanglement in condensed matter systems
- Multipartite entanglement detection via structure factors
- Many-body localization and quantum ergodicity in disordered long-range Ising models
- Experimental bath engineering for quantitative studies of quantum control
- Frustrated Quantum Spin Models with Cold Coulomb Crystals
- Quantum Catalysis of Magnetic Phase Transitions in a Quantum Simulator
- Quantum Magnetism of Spin-Ladder Compounds with Trapped-Ion Crystals
- Hidden Frustrated Interactions and Quantum Annealing in Trapped Ion Spin-Phonon Chains
- Adiabatic quantum simulation with a segmented ion trap: Application to long-distance entanglement in quantum spin systems
- How Fast Can Quantum Annealers Count?
Cited by in corpus (28)
- Adiabatic Quantum Computing
- Perspectives of quantum annealing: Methods and implementations
- Quantum Annealing for Industry Applications: Introduction and Review
- Quantum annealing with longitudinal bias fields
- Quantum annealing for the number partitioning problem using a tunable spin glass of ions
- Maximum-Entropy Inference with a Programmable Annealer
- Quantum annealing with ultracold atoms in a multimode optical resonator
- Scaling overhead of embedding optimization problems in quantum annealing
- Trapped-ion quantum simulation of excitation transport: disordered, noisy, and long-range connected quantum networks
- Quantum approximate optimization algorithm for qudit systems
- Relation between quantum fluctuations and the performance enhancement of quantum annealing in a nonstoquastic Hamiltonian
- Dynamical phase transitions in quantum spin models with antiferromagnetic long-range interactions
- Dominant Reaction Pathways by Quantum Computing
- Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
- Hybrid annealing using a quantum simulator coupled to a classical computer
- Adiabatic quantum computing solution of the knapsack problem
- Unraveling the origin of higher success probabilities in quantum versus semi-classical annealing
- Semiclassical approach to finite temperature quantum annealing with trapped ions
- Genuine Multipartite Entanglement in Quantum Optimization
- The quantum annealing gap and quench dynamics in the exact cover problem
- A numerical approach for calculating exact non-adiabatic terms in quantum dynamics
- Quantum annealing sampling with a bias field
- Quantum annealing of Cayley-tree Ising spins at small scales
- Boosting quantum annealing performance through direct polynomial unconstrained binary optimization
- Accessing eigenstate spin-glass order from reduced density matrices
- Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
- Relativistic meson spectra on ion-trap quantum simulators
- Assessing the quantumness of the annealing dynamics via Leggett Gargs inequalities: a weak measurement approach