2026-07-22T16:00:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16382 2024-03-06T10:57:20Z ddc:004 open_access

Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond Chou, Chi-Ning Love, Peter J. Sandhu, Juspreet Singh Shi, Jonathan Quantum Algorithms Spin Glasses Hardness of Approximation Local Algorithms Concentration Inequalities Overlap Gap Property 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chi-Ning Chou and Peter J. Love and Juspreet Singh Sandhu and Jonathan Shi 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.41 urn:nbn:de:0030-drops-163822 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.41 eng https://creativecommons.org/licenses/by/4.0/legalcode