Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices

The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems. Despite its promise for near-term quantum applications, not much is currently understood about the QAOA’s performance beyond its lowest-de...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, Mikhail D. Lukin
Formato:	article
Lenguaje:	EN
Publicado:	American Physical Society 2020
Materias:	Physics QC1-999
Acceso en línea:	https://doaj.org/article/256c0de117684ce3a4c4cd6a38721212
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:256c0de117684ce3a4c4cd6a38721212
record_format	dspace
spelling	oai:doaj.org-article:256c0de117684ce3a4c4cd6a387212122021-12-02T11:46:23ZQuantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices10.1103/PhysRevX.10.0210672160-3308https://doaj.org/article/256c0de117684ce3a4c4cd6a387212122020-06-01T00:00:00Zhttp://doi.org/10.1103/PhysRevX.10.021067http://doi.org/10.1103/PhysRevX.10.021067https://doaj.org/toc/2160-3308The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems. Despite its promise for near-term quantum applications, not much is currently understood about the QAOA’s performance beyond its lowest-depth variant. An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization. We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations. Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O[poly(p)] time, whereas the standard strategy of random initialization requires 2^{O(p)} optimization runs to achieve similar performance. We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps. The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps. Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA. When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices. We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.Leo ZhouSheng-Tao WangSoonwon ChoiHannes PichlerMikhail D. LukinAmerican Physical SocietyarticlePhysicsQC1-999ENPhysical Review X, Vol 10, Iss 2, p 021067 (2020)
institution	DOAJ
collection	DOAJ
language	EN
topic	Physics QC1-999
spellingShingle	Physics QC1-999 Leo Zhou Sheng-Tao Wang Soonwon Choi Hannes Pichler Mikhail D. Lukin Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
description	The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems. Despite its promise for near-term quantum applications, not much is currently understood about the QAOA’s performance beyond its lowest-depth variant. An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization. We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations. Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O[poly(p)] time, whereas the standard strategy of random initialization requires 2^{O(p)} optimization runs to achieve similar performance. We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps. The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps. Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA. When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices. We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.
format	article
author	Leo Zhou Sheng-Tao Wang Soonwon Choi Hannes Pichler Mikhail D. Lukin
author_facet	Leo Zhou Sheng-Tao Wang Soonwon Choi Hannes Pichler Mikhail D. Lukin
author_sort	Leo Zhou
title	Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
title_short	Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
title_full	Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
title_fullStr	Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
title_full_unstemmed	Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
title_sort	quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices
publisher	American Physical Society
publishDate	2020
url	https://doaj.org/article/256c0de117684ce3a4c4cd6a38721212
work_keys_str_mv	AT leozhou quantumapproximateoptimizationalgorithmperformancemechanismandimplementationonneartermdevices AT shengtaowang quantumapproximateoptimizationalgorithmperformancemechanismandimplementationonneartermdevices AT soonwonchoi quantumapproximateoptimizationalgorithmperformancemechanismandimplementationonneartermdevices AT hannespichler quantumapproximateoptimizationalgorithmperformancemechanismandimplementationonneartermdevices AT mikhaildlukin quantumapproximateoptimizationalgorithmperformancemechanismandimplementationonneartermdevices
_version_	1718395215653371904

Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices

Ejemplares similares