{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T16:15:32Z","timestamp":1762272932275,"version":"3.40.5"},"reference-count":35,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T00:00:00Z","timestamp":1657152000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"(USRA) NAMS Student R&D Program","award":["NNA16BD14C"],"award-info":[{"award-number":["NNA16BD14C"]}]},{"name":"DARPA-NASA","award":["IAA 8839, Annex 114"],"award-info":[{"award-number":["IAA 8839, Annex 114"]}]},{"name":"NSF","award":["DGE-1746045"],"award-info":[{"award-number":["DGE-1746045"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We consider the power of local algorithms for approximately solving Max <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><\/mml:math>XOR, a generalization of two constraint satisfaction problems previously studied with classical and quantum algorithms (MaxCut and Max E3LIN2). In Max <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><\/mml:math>XOR each constraint is the XOR of exactly <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><\/mml:math> variables and a parity bit. On instances with either random signs (parities) or no overlapping clauses and <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>D<\/mml:mi><mml:mo>+<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:math> clauses per variable, we calculate the expected satisfying fraction of the depth-1 QAOA from Farhi et al [arXiv:1411.4028] and compare with a generalization of the local threshold algorithm from Hirvonen et al [arXiv:1402.2543]. Notably, the quantum algorithm outperforms the threshold algorithm for <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><\/mml:math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mo>&amp;#x003E;<\/mml:mo><\/mml:math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mn>4<\/mml:mn><\/mml:math>.On the other hand, we highlight potential difficulties for the QAOA to achieve computational quantum advantage on this problem. We first compute a tight upper bound on the maximum satisfying fraction of nearly all large random regular Max <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><\/mml:math>XOR instances by numerically calculating the ground state energy density <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>P<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>k<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> of a mean-field <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><\/mml:math>-spin glass [arXiv:1606.02365]. The upper bound grows with <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><\/mml:math> much faster than the performance of both one-local algorithms. We also identify a new obstruction result for low-depth quantum circuits (including the QAOA) when <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><mml:mo>=<\/mml:mo><mml:mn>3<\/mml:mn><\/mml:math>, generalizing a result of Bravyi et al [arXiv:1910.08980] when <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><mml:mo>=<\/mml:mo><mml:mn>2<\/mml:mn><\/mml:math>. We conjecture that a similar obstruction exists for all <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><\/mml:math>.<\/jats:p>","DOI":"10.22331\/q-2022-07-07-757","type":"journal-article","created":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T12:07:47Z","timestamp":1657195667000},"page":"757","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":22,"title":["Bounds on approximating Max <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><\/mml:math>XOR with quantum and classical local algorithms"],"prefix":"10.22331","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9084-6971","authenticated-orcid":false,"given":"Kunal","family":"Marwaha","sequence":"first","affiliation":[{"name":"Quantum Artificial Intelligence Laboratory (QuAIL), NASA Ames Research Center, Moffett Field, CA"},{"name":"USRA Research Institute for Advanced Computer Science (RIACS), Mountain View, CA"},{"name":"Berkeley Center for Quantum Information and Computation, University of California, Berkeley, CA"},{"name":"Department of Computer Science, University of Chicago, Chicago, IL"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4607-3921","authenticated-orcid":false,"given":"Stuart","family":"Hadfield","sequence":"additional","affiliation":[{"name":"Quantum Artificial Intelligence Laboratory (QuAIL), NASA Ames Research Center, Moffett Field, CA"},{"name":"USRA Research Institute for Advanced Computer Science (RIACS), Mountain View, CA"}]}],"member":"9598","published-online":{"date-parts":[[2022,7,7]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"A. Auffinger and W.-K. Chen. On properties of Parisi measures. arXiv:1303.3573, doi:10.1007\/s00440-014-0563-y.","DOI":"10.1007\/s00440-014-0563-y"},{"key":"1","doi-asserted-by":"publisher","unstructured":"A. Auffinger and W.-K. Chen. The Parisi formula has a unique minimizer. Communications in Mathematical Physics, 335(3):1429\u20131444, Nov 2014. arXiv:1402.5132, doi:10.1007\/s00220-014-2254-z.","DOI":"10.1007\/s00220-014-2254-z"},{"key":"2","doi-asserted-by":"publisher","unstructured":"A. Auffinger and W.-K. Chen. Parisi formula for the ground state energy in the mixed p-spin model. arXiv:1606.05335, doi:10.1214\/16-aop1173.","DOI":"10.1214\/16-aop1173"},{"key":"3","unstructured":"A. E. Alaoui and A. Montanari. Algorithmic thresholds in mean field spin glasses. arXiv:2009.11481."},{"key":"4","doi-asserted-by":"publisher","unstructured":"A. E. Alaoui, A. Montanari, and M. Sellke. Optimization of mean-field spin glasses. arXiv:2001.00904, doi:10.1214\/21-aop1519.","DOI":"10.1214\/21-aop1519"},{"key":"5","doi-asserted-by":"publisher","unstructured":"S. Bravyi, A. Kliesch, R. Koenig, and E. Tang. Obstacles to state preparation and variational optimization from symmetry protection. arXiv preprint, 2019. arXiv:1910.08980.","DOI":"10.1103\/PhysRevLett.125.260505"},{"key":"6","doi-asserted-by":"publisher","unstructured":"B. Barak and K. Marwaha. Classical algorithms and quantum limitations for maximum cut on high-girth graphs. arXiv:2106.05900, doi:10.4230\/LIPIcs.ITCS.2022.14.","DOI":"10.4230\/LIPIcs.ITCS.2022.14"},{"key":"7","unstructured":"B. Barak, A. Moitra, R. O&apos;Donnell, et al. Beating the random assignment on constraint satisfaction problems of bounded degree. arXiv:1505.03424."},{"key":"8","doi-asserted-by":"publisher","unstructured":"W.-K. Chen, D. Gamarnik, D. Panchenko, and M. Rahman. Suboptimality of local algorithms for a class of max-cut problems. The Annals of Probability, 47(3), May 2019. arXiv:1707.05386, doi:10.1214\/18-aop1291.","DOI":"10.1214\/18-aop1291"},{"key":"9","unstructured":"C.-N. Chou, P. J. Love, J. S. Sandhu, and J. Shi. Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond. arXiv:2108.06049."},{"key":"10","doi-asserted-by":"publisher","unstructured":"A. Crisanti and T. Rizzo. Analysis of the $\\infty$-replica symmetry breaking solution of the Sherrington-Kirkpatrick model. Physical Review E, 65(4), Apr 2002. arXiv:cond-mat\/0111037, doi:10.1103\/physreve.65.046137.","DOI":"10.1103\/physreve.65.046137"},{"key":"11","doi-asserted-by":"publisher","unstructured":"B. Derrida. Random-energy model: An exactly solvable model of disordered systems. Phys. Rev. B, 24:2613\u20132626, Sep 1981. doi:10.1103\/PhysRevB.24.2613.","DOI":"10.1103\/PhysRevB.24.2613"},{"key":"12","doi-asserted-by":"publisher","unstructured":"A. Dembo, A. Montanari, and S. Sen. Extremal cuts of sparse random graphs. The Annals of Probability, 45(2):1190\u20131217, 2017. arXiv:1503.03923, doi:10.1214\/15-aop1084.","DOI":"10.1214\/15-aop1084"},{"key":"13","doi-asserted-by":"publisher","unstructured":"L. Eldar and A. W. Harrow. Local Hamiltonians whose ground states are hard to approximate. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), Oct 2017. arXiv:1510.02082, doi:10.1109\/focs.2017.46.","DOI":"10.1109\/focs.2017.46"},{"key":"14","unstructured":"E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm. arXiv:1411.4028."},{"key":"15","unstructured":"E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. arXiv:1412.6062."},{"key":"16","unstructured":"E. Farhi, D. Gamarnik, and S. Gutmann. The quantum approximate optimization algorithm needs to see the whole graph: A typical case. arXiv:2004.09002."},{"key":"17","doi-asserted-by":"publisher","unstructured":"J. Friedman. A proof of Alon&apos;s second eigenvalue conjecture and related problems. arXiv:cs\/0405020, doi:10.1090\/memo\/0910.","DOI":"10.1090\/memo\/0910"},{"key":"18","unstructured":"S. Hadfield. Quantum Algorithms for Scientific Computing and Approximate Optimization. Columbia University, 2018, arXiv:1805.03265."},{"key":"19","doi-asserted-by":"publisher","unstructured":"J. H\u00e5stad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):798\u2013859, 2001. doi:10.1145\/258533.258536, URL http:\/\/www.cs.umd.edu\/ gasarch\/BLOGPAPERS\/max3satl.pdf.","DOI":"10.1145\/258533.258536"},{"key":"20","doi-asserted-by":"publisher","unstructured":"M. B. Hastings. Trivial low energy states for commuting Hamiltonians, and the quantum PCP conjecture. Quantum Information & Computation, 13, 2013. arXiv:1201.3387, doi:10.26421\/qic13.5-6-3.","DOI":"10.26421\/qic13.5-6-3"},{"key":"21","doi-asserted-by":"publisher","unstructured":"M. B. Hastings. Classical and quantum bounded depth approximation algorithms. arXiv:1905.07047, doi:10.26421\/qic19.13-14-3.","DOI":"10.26421\/qic19.13-14-3"},{"key":"22","doi-asserted-by":"publisher","unstructured":"W. W. Ho and T. H. Hsieh. Efficient variational simulation of non-trivial quantum states. arXiv:1803.00026, doi:10.21468\/scipostphys.6.3.029.","DOI":"10.21468\/scipostphys.6.3.029"},{"key":"23","doi-asserted-by":"publisher","unstructured":"J. Hirvonen, J. Rybicki, S. Schmid, and J. Suomela. Large cuts with local algorithms on triangle-free graphs. The Electronic Journal of Combinatorics, pages P4\u201321, 2017. arXiv:1402.2543, doi:10.37236\/6862.","DOI":"10.37236\/6862"},{"key":"24","unstructured":"C. Y.-Y. Lin and Y. Zhu. Performance of QAOA on typical instances of constraint satisfaction problems with bounded degree. arXiv:1601.01744."},{"key":"25","doi-asserted-by":"publisher","unstructured":"K. Marwaha. Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs. Quantum, 5:437, Apr. 2021. arXiv:2101.05513, doi:10.22331\/q-2021-04-20-437.","DOI":"10.22331\/q-2021-04-20-437"},{"key":"26","doi-asserted-by":"publisher","unstructured":"A. Montanari. Optimization of the Sherrington\u2013Kirkpatrick Hamiltonian. arXiv:1812.10897, doi:10.1109\/focs.2019.00087.","DOI":"10.1109\/focs.2019.00087"},{"key":"27","doi-asserted-by":"publisher","unstructured":"P. Obszarski and A. Jastrz\u0229bski. Edge-coloring of 3-uniform hypergraphs. Discrete Applied Mathematics, 217:48\u201352, 2017, Combinatorial Optimization: Theory, Computation, and Applications. doi:10.1016\/j.dam.2016.06.009.","DOI":"10.1016\/j.dam.2016.06.009"},{"key":"28","doi-asserted-by":"publisher","unstructured":"D. Panchenko. Introduction to the SK model. arXiv:1412.0170, doi:10.4310\/cdm.2014.v2014.n1.a4.","DOI":"10.4310\/cdm.2014.v2014.n1.a4"},{"key":"29","doi-asserted-by":"publisher","unstructured":"D. Panchenko. On the $k$-sat model with large number of clauses. arXiv:1608.06256, doi:10.1002\/rsa.20748.","DOI":"10.1002\/rsa.20748"},{"key":"30","doi-asserted-by":"publisher","unstructured":"G. Parisi. A sequence of approximated solutions to the S-K model for spin glasses. Journal of Physics A: Mathematical and General, 13(4):L115\u2013L121, apr 1980. doi:10.1088\/0305-4470\/13\/4\/009.","DOI":"10.1088\/0305-4470\/13\/4\/009"},{"key":"31","doi-asserted-by":"publisher","unstructured":"S. Sen. Optimization on sparse random hypergraphs and spin glasses. arXiv:1606.02365, doi:10.1002\/rsa.20774.","DOI":"10.1002\/rsa.20774"},{"key":"32","doi-asserted-by":"publisher","unstructured":"R. Shaydulin, S. Hadfield, T. Hogg, and I. Safro. Classical symmetries and the quantum approximate optimization algorithm. Quantum Information Processing, 20(11):1\u201328, 2021. arXiv:2012.04713, doi:10.1007\/s11128-021-03298-4.","DOI":"10.1007\/s11128-021-03298-4"},{"key":"33","doi-asserted-by":"publisher","unstructured":"M. Talagrand. The Parisi formula. Annals of Mathematics, 163:221\u2013263, 2006. doi:10.4007\/annals.2006.163.221, URL https:\/\/annals.math.princeton.edu\/wp-content\/uploads\/annals-v163-n1-p04.pdf.","DOI":"10.4007\/annals.2006.163.221"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel. Quantum approximate optimization algorithm for maxcut: A fermionic view. Phys. Rev. A, 97:022304, Feb 2018. arXiv:1706.02998, doi:10.1103\/PhysRevA.97.022304.","DOI":"10.1103\/PhysRevA.97.022304"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-07-07-757\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T12:07:56Z","timestamp":1657195676000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-07-07-757\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,7]]},"references-count":35,"URL":"https:\/\/doi.org\/10.22331\/q-2022-07-07-757","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"type":"electronic","value":"2521-327X"}],"subject":[],"published":{"date-parts":[[2022,7,7]]},"article-number":"757"}}