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.

Probing entanglement in adiabatic quantum optimization with trapped ions / Hauke, Philipp; Bonnes, Lars; Heyl, Markus; Lechner, Wolfgang. - In: FRONTIERS IN PHYSICS. - ISSN 2296-424X. - ELETTRONICO. - 3:(2015), pp. 21.1-21.15. [10.3389/fphy.2015.00021]

Probing entanglement in adiabatic quantum optimization with trapped ions

Hauke, Philipp;
2015-01-01

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.
2015
Hauke, Philipp; Bonnes, Lars; Heyl, Markus; Lechner, Wolfgang
Probing entanglement in adiabatic quantum optimization with trapped ions / Hauke, Philipp; Bonnes, Lars; Heyl, Markus; Lechner, Wolfgang. - In: FRONTIERS IN PHYSICS. - ISSN 2296-424X. - ELETTRONICO. - 3:(2015), pp. 21.1-21.15. [10.3389/fphy.2015.00021]
File in questo prodotto:
File Dimensione Formato  
fphy-03-00021.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Creative commons
Dimensione 1.71 MB
Formato Adobe PDF
1.71 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/254445
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 24
  • ???jsp.display-item.citation.isi??? 23
social impact