---
_id: '13125'
abstract:
- lang: eng
text: 'The quantum approximate optimization algorithm (QAOA) is a variational quantum
algorithm, where a quantum computer implements a variational ansatz consisting
of p layers of alternating unitary operators and a classical computer is used
to optimize the variational parameters. For a random initialization, the optimization
typically leads to local minima with poor performance, motivating the search for
initialization strategies of QAOA variational parameters. Although numerous heuristic
initializations exist, an analytical understanding and performance guarantees
for large p remain evasive.We introduce a greedy initialization of QAOA which
guarantees improving performance with an increasing number of layers. Our main
result is an analytic construction of 2p + 1 transition states—saddle points with
a unique negative curvature direction—for QAOA with p + 1 layers that use the
local minimum of QAOA with p layers. Transition states connect to new local minima,
which are guaranteed to lower the energy compared to the minimum found for p layers.
We use the GREEDY procedure to navigate the exponentially increasing with p number
of local minima resulting from the recursive application of our analytic construction.
The performance of the GREEDY procedure matches available initialization strategies
while providing a guarantee for the minimal energy to decrease with an increasing
number of layers p. '
acknowledgement: 'We thank V. Verteletskyi for a joint collaboration on numerical
studies of the QAOA during his internship at ISTA that inspired analytic results
on TS reported in this work. We acknowledge A. A. Mele and M. Brooks for discussions
and D. Egger, P. Love, and D. Wierichs for valuable feedback on the manuscript.
S.H.S., R.A.M., and M.S. acknowledge support by the European Research Council (ERC)
under the European Union’s Horizon 2020 research and innovation program (Grant Agreement
No. 850899). R.K. is supported by the SFB BeyondC (Grant No. F7107-N38) and the
project QuantumReady (FFG 896217). '
article_number: '062404'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Stefan
full_name: Sack, Stefan
id: dd622248-f6e0-11ea-865d-ce382a1c81a5
last_name: Sack
orcid: 0000-0001-5400-8508
- first_name: Raimel A
full_name: Medina Ramos, Raimel A
id: CE680B90-D85A-11E9-B684-C920E6697425
last_name: Medina Ramos
orcid: 0000-0002-5383-2869
- first_name: Richard
full_name: Kueng, Richard
last_name: Kueng
- first_name: Maksym
full_name: Serbyn, Maksym
id: 47809E7E-F248-11E8-B48F-1D18A9856A87
last_name: Serbyn
orcid: 0000-0002-2399-5827
citation:
ama: Sack S, Medina Ramos RA, Kueng R, Serbyn M. Recursive greedy initialization
of the quantum approximate optimization algorithm with guaranteed improvement.
Physical Review A. 2023;107(6). doi:10.1103/physreva.107.062404
apa: Sack, S., Medina Ramos, R. A., Kueng, R., & Serbyn, M. (2023). Recursive
greedy initialization of the quantum approximate optimization algorithm with guaranteed
improvement. Physical Review A. American Physical Society. https://doi.org/10.1103/physreva.107.062404
chicago: Sack, Stefan, Raimel A Medina Ramos, Richard Kueng, and Maksym Serbyn.
“Recursive Greedy Initialization of the Quantum Approximate Optimization Algorithm
with Guaranteed Improvement.” Physical Review A. American Physical Society,
2023. https://doi.org/10.1103/physreva.107.062404.
ieee: S. Sack, R. A. Medina Ramos, R. Kueng, and M. Serbyn, “Recursive greedy initialization
of the quantum approximate optimization algorithm with guaranteed improvement,”
Physical Review A, vol. 107, no. 6. American Physical Society, 2023.
ista: Sack S, Medina Ramos RA, Kueng R, Serbyn M. 2023. Recursive greedy initialization
of the quantum approximate optimization algorithm with guaranteed improvement.
Physical Review A. 107(6), 062404.
mla: Sack, Stefan, et al. “Recursive Greedy Initialization of the Quantum Approximate
Optimization Algorithm with Guaranteed Improvement.” Physical Review A,
vol. 107, no. 6, 062404, American Physical Society, 2023, doi:10.1103/physreva.107.062404.
short: S. Sack, R.A. Medina Ramos, R. Kueng, M. Serbyn, Physical Review A 107 (2023).
corr_author: '1'
date_created: 2023-06-07T06:57:32Z
date_published: 2023-06-02T00:00:00Z
date_updated: 2026-10-15T22:31:12Z
day: '02'
ddc:
- '530'
department:
- _id: MaSe
doi: 10.1103/physreva.107.062404
ec_funded: 1
external_id:
arxiv:
- '2209.01159'
isi:
- '001016927100012'
file:
- access_level: open_access
checksum: 0d71423888eeccaa60d8f41197f26306
content_type: application/pdf
creator: dernst
date_created: 2023-06-13T07:28:36Z
date_updated: 2023-06-13T07:28:36Z
file_id: '13131'
file_name: 2023_PhysRevA_Sack.pdf
file_size: 2524611
relation: main_file
success: 1
file_date_updated: 2023-06-13T07:28:36Z
fulldoi: https://doi.org/10.1103/physreva.107.062404
has_accepted_license: '1'
intvolume: ' 107'
isi: 1
issue: '6'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 23841C26-32DE-11EA-91FC-C7463DDC885E
call_identifier: H2020
grant_number: '850899'
name: 'Non-Ergodic Quantum Matter: Universality, Dynamics and Control'
publication: Physical Review A
publication_identifier:
eissn:
- 2469-9934
issn:
- 2469-9926
publication_status: published
publisher: American Physical Society
quality_controlled: '1'
related_material:
record:
- id: '17208'
relation: dissertation_contains
status: public
- id: '14622'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Recursive greedy initialization of the quantum approximate optimization algorithm
with guaranteed improvement
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 107
year: '2023'
...