Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
ACM Transactions on Quantum Computing · 30.09.2023 · 4 (3) · 1-15
DOI: 10.1145/3584706 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Quantum Computing, online erschienen am 24.04.2023. Verfasst von Ruslan Shaydulin und 4 weiteren Autor:innen. Die Arbeit wurde bisher 97-mal zitiert (Crossref) und nennt 38 Literaturangaben. Gefördert von: Defense Advanced Research Project Agency ONISQ program, Air Force Office of Scientific Research award, National Science Foundation award.
Abstract (Originalsprache)
Finding high-quality parameters is a central obstacle to using the quantum approximate optimization algorithm (QAOA). Previous work partially addresses this issue for QAOA on unweighted MaxCut problems by leveraging similarities in the objective landscape among different problem instances. However, we show that the more general weighted MaxCut problem has significantly modified objective landscapes, with a proliferation of poor local optima. Our main contribution is a simple rescaling scheme that overcomes these deleterious effects of weights. We show that for a given QAOA depth, a single “typical” vector of QAOA parameters can be successfully transferred to weighted MaxCut instances. This transfer leads to a median decrease in the approximation ratio of only 2.0 percentage points relative to a considerably more expensive direct optimization on a dataset of 34,701 instances with up to 20 nodes and multiple weight distributions. This decrease can be reduced to 1.2 percentage points at the cost of only 10 additional QAOA circuit evaluations with parameters sampled from a pretrained metadistribution, or the transferred parameters can be used as a starting point for a single local optimization run to obtain approximation ratios equivalent to those achieved by exhaustive optimization in 96.35% of our cases.
Förderung
- Defense Advanced Research Project Agency ONISQ program
- Air Force Office of Scientific Research award
- National Science Foundation award
- U.S. Department of Energy (DOE), Office of Science, Office of Advanced Scientific Computing Research AIDE-QC and FAR-QC
- Argonne LDRD program
Zitieren
APA
Shaydulin, R., Lotshaw, P. C., Larson, J., Ostrowski, J., & Humble, T. S. (2023). Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut. ACM Transactions on Quantum Computing, 4(3), 1-15. https://doi.org/10.1145/3584706
Vancouver
Shaydulin R, Lotshaw PC, Larson J, Ostrowski J, Humble TS. Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut. ACM Transactions on Quantum Computing. 2023;4(3):1-15. doi:10.1145/3584706
BibTeX
@article{Shaydulin2023,
author = {Shaydulin, Ruslan and Lotshaw, Phillip C. and Larson, Jeffrey and Ostrowski, James and Humble, Travis S.},
title = {Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut},
journal = {ACM Transactions on Quantum Computing},
year = {2023},
volume = {4},
number = {3},
pages = {1--15},
doi = {10.1145/3584706}
}
EUVIMED