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 pro
tocols 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.
Ergodicity in quantum many-body systems is - despite its fundamental importance - still an open problem. Many-body localization provides a general framework for quantum ergodicity, and may therefore offer important insights. However, the characteriza
tion of many-body localization through simple observables is a difficult task. In this article, we introduce a measure for distances in Hilbert space for spin-1/2 systems that can be interpreted as a generalization of the Anderson localization length to the many-body Hilbert space. We show that this many-body localization length is equivalent to a simple local observable in real space, which can be measured in experiments of superconducting qubits, polar molecules, Rydberg atoms, and trapped ions. Using the many-body localization length and a necessary criterion for ergodicity that it provides, we study many-body localization and quantum ergodicity in power-law-interacting Ising models subject to disorder in the transverse field. Based on the nonequilibrium dynamical renormalization group, numerically exact diagonalization, and an analysis of the statistics of resonances we find a many-body localized phase at infinite temperature for small power-law exponents. Within the applicability of these methods, we find no indications of a delocalization transition.
