License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.41
URN: urn:nbn:de:0030-drops-163822
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16382/
Chou, Chi-Ning ;
Love, Peter J. ;
Sandhu, Juspreet Singh ;
Shi, Jonathan
Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond
Abstract
We introduce a notion of generic local algorithm, which strictly generalizes existing frameworks of local algorithms such as factors of i.i.d. by capturing local quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA).
Motivated by a question of Farhi et al. [arXiv:1910.08187, 2019], we then show limitations of generic local algorithms including QAOA on random instances of constraint satisfaction problems (CSPs). Specifically, we show that any generic local algorithm whose assignment to a vertex depends only on a local neighborhood with o(n) other vertices (such as the QAOA at depth less than εlog(n)) cannot arbitrarily-well approximate boolean CSPs if the problem satisfies a geometric property from statistical physics called the coupled overlap-gap property (OGP) [Chen et al., Annals of Probability, 47(3), 2019]. We show that the random MAX-k-XOR problem has this property when k ≥ 4 is even by extending the corresponding result for diluted k-spin glasses.
Our concentration lemmas confirm a conjecture of Brandao et al. [arXiv:1812.04170, 2018] asserting that the landscape independence of QAOA extends to logarithmic depth - in other words, for every fixed choice of QAOA angle parameters, the algorithm at logarithmic depth performs almost equally well on almost all instances. One of these lemmas is a strengthening of McDiarmid’s inequality, applicable when the random variables have a highly biased distribution, and may be of independent interest.
BibTeX - Entry
@InProceedings{chou_et_al:LIPIcs.ICALP.2022.41,
author = {Chou, Chi-Ning and Love, Peter J. and Sandhu, Juspreet Singh and Shi, Jonathan},
title = {{Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {41:1--41:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16382},
URN = {urn:nbn:de:0030-drops-163822},
doi = {10.4230/LIPIcs.ICALP.2022.41},
annote = {Keywords: Quantum Algorithms, Spin Glasses, Hardness of Approximation, Local Algorithms, Concentration Inequalities, Overlap Gap Property}
}
|
Keywords: |
|
Quantum Algorithms, Spin Glasses, Hardness of Approximation, Local Algorithms, Concentration Inequalities, Overlap Gap Property |
|
Collection: |
|
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
28.06.2022 |
