Probing Entanglement in Adiabatic Quantum Optimization with Trapped Ions

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.

v1: 10 pages+appendix, 6 figures. v2: added explanations; accepted in Frontiers in Physics, Research Topic on Useful Quantum Simulators

References in corpus (8)

• QuTiP 2: A Python framework for the dynamics of open quantum systems
• Experimental implementation of an adiabatic quantum optimization algorithm
• Optimal Surface-Electrode Trap Lattices for Quantum Simulation with Trapped Ions
• Tunable spin-spin interactions and entanglement of ions in separate wells
• Laserless trapped-ion quantum simulations without spontaneous scattering using microtrap arrays
• Multipartite entanglement detection via structure factors
• Experimental bath engineering for quantitative studies of quantum control
• Quantum Magnetism of Spin-Ladder Compounds with Trapped-Ion Crystals

Cited by in corpus (5)

• Quantum annealing with ultracold atoms in a multimode optical resonator
• Dynamical phase transitions in quantum spin models with antiferromagnetic long-range interactions
• Adiabatic quantum computing solution of the knapsack problem
• Quantum annealing of Cayley-tree Ising spins at small scales
• Assessing the quantumness of the annealing dynamics via Leggett Gargs inequalities: a weak measurement approach