  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.
