Search Results

Documents authored by Shi, Jonathan

Document
DOI: 10.4230/LIPIcs.ITCS.2023.77
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses

Authors: Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, and Jonathan Shi

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We study random constraint satisfaction problems (CSPs) at large clause density. We relate the structure of near-optimal solutions for any Boolean Max-CSP to that for an associated spin glass on the hypercube, using the Guerra-Toninelli interpolation from statistical physics. The noise stability polynomial of the CSP’s predicate is, up to a constant, the mixture polynomial of the associated spin glass. We show two main consequences: 1) We prove that the maximum fraction of constraints that can be satisfied in a random Max-CSP at large clause density is determined by the ground state energy density of the corresponding spin glass. Since the latter value can be computed with the Parisi formula [Parisi, 1980; Talagrand, 2006; Auffinger and Chen, 2017], we provide numerical values for some popular CSPs. 2) We prove that a Max-CSP at large clause density possesses generalized versions of the overlap gap property if and only if the same holds for the corresponding spin glass. We transfer results from [Huang and Sellke, 2021] to obstruct algorithms with overlap concentration on a large class of Max-CSPs. This immediately includes local classical and local quantum algorithms [Chou et al., 2022].
Cite as

Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, and Jonathan Shi. Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 77:1-77:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jones_et_al:LIPIcs.ITCS.2023.77,
  author =	{Jones, Chris and Marwaha, Kunal and Sandhu, Juspreet Singh and Shi, Jonathan},
  title =	{{Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{77:1--77:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.77},
  URN =		{urn:nbn:de:0030-drops-175804},
  doi =		{10.4230/LIPIcs.ITCS.2023.77},
  annote =	{Keywords: spin glass, overlap gap property, constraint satisfaction problem, Guerra-Toninelli interpolation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.41
Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond

Authors: Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, and Jonathan Shi

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

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.
Cite as

Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, and Jonathan Shi. Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 41:1-41:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ICALP.2022.41},
  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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact