Bounds on approximating Max $k$XOR with quantum and classical local algorithms

Kunal Marwaha; Stuart Hadfield

doi:10.22331/q-2022-07-07-757

Bounds on approximating Max $k$XOR with quantum and classical local algorithms

Kunal Marwaha^1,2,3,4 and Stuart Hadfield^1,2

¹Quantum Artificial Intelligence Laboratory (QuAIL), NASA Ames Research Center, Moffett Field, CA
²USRA Research Institute for Advanced Computer Science (RIACS), Mountain View, CA
³Berkeley Center for Quantum Information and Computation, University of California, Berkeley, CA
⁴Department of Computer Science, University of Chicago, Chicago, IL

Published:	2022-07-07, volume 6, page 757
Eprint:	arXiv:2109.10833v3
Doi:	https://doi.org/10.22331/q-2022-07-07-757
Citation:	Quantum 6, 757 (2022).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We consider the power of local algorithms for approximately solving Max $k$XOR, a generalization of two constraint satisfaction problems previously studied with classical and quantum algorithms (MaxCut and Max E3LIN2). In Max $k$XOR each constraint is the XOR of exactly $k$ variables and a parity bit. On instances with either random signs (parities) or no overlapping clauses and $D+1$ 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 $k$$\gt$$4$.

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 $k$XOR instances by numerically calculating the ground state energy density $P(k)$ of a mean-field $k$-spin glass [arXiv:1606.02365]. The upper bound grows with $k$ 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 $k=3$, generalizing a result of Bravyi et al [arXiv:1910.08980] when $k=2$. We conjecture that a similar obstruction exists for all $k$.

Featured image: Comparison of the satisfying fraction (performance) of the threshold algorithm and the depth-1 QAOA for Max kXOR at large $D$ (and $D \gg k$). The constant $C_k$ for QAOA grows more quickly with $k$ than for the threshold algorithm. Although the threshold algorithm outperforms the depth-1 QAOA for $k \in \{2,3,4\}$, at all other k, the QAOA is the better algorithm.

► BibTeX data

@article{Marwaha2022boundsapproximating,
  doi = {10.22331/q-2022-07-07-757},
  url = {https://doi.org/10.22331/q-2022-07-07-757},
  title = {Bounds on approximating {M}ax {$k$}{XOR} with quantum and classical local algorithms},
  author = {Marwaha, Kunal and Hadfield, Stuart},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {757},
  month = jul,
  year = {2022}
}

► References

[1] A. Auffinger and W.-K. Chen. On properties of Parisi measures. arXiv:1303.3573, doi:10.1007/s00440-014-0563-y.
https://doi.org/10.1007/s00440-014-0563-y
arXiv:1303.3573

[2] A. Auffinger and W.-K. Chen. The Parisi formula has a unique minimizer. Communications in Mathematical Physics, 335(3):1429–1444, Nov 2014. arXiv:1402.5132, doi:10.1007/s00220-014-2254-z.
https://doi.org/10.1007/s00220-014-2254-z
arXiv:1402.5132

[3] 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.
https://doi.org/10.1214/16-aop1173
arXiv:1606.05335

[4] A. E. Alaoui and A. Montanari. Algorithmic thresholds in mean field spin glasses. arXiv:2009.11481.
arXiv:2009.11481

[5] A. E. Alaoui, A. Montanari, and M. Sellke. Optimization of mean-field spin glasses. arXiv:2001.00904, doi:10.1214/21-aop1519.
https://doi.org/10.1214/21-aop1519
arXiv:2001.00904

[6] 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.
https://doi.org/10.1103/PhysRevLett.125.260505
arXiv:1910.08980

[7] 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.
https://doi.org/10.4230/LIPIcs.ITCS.2022.14
arXiv:2106.05900

[8] B. Barak, A. Moitra, R. O'Donnell, et al. Beating the random assignment on constraint satisfaction problems of bounded degree. arXiv:1505.03424.
arXiv:1505.03424

[9] 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.
https://doi.org/10.1214/18-aop1291
arXiv:1707.05386

[10] 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.
arXiv:2108.06049

[11] 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.
https://doi.org/10.1103/physreve.65.046137
arXiv:cond-mat/0111037

[12] B. Derrida. Random-energy model: An exactly solvable model of disordered systems. Phys. Rev. B, 24:2613–2626, Sep 1981. doi:10.1103/PhysRevB.24.2613.
https://doi.org/10.1103/PhysRevB.24.2613

[13] A. Dembo, A. Montanari, and S. Sen. Extremal cuts of sparse random graphs. The Annals of Probability, 45(2):1190–1217, 2017. arXiv:1503.03923, doi:10.1214/15-aop1084.
https://doi.org/10.1214/15-aop1084
arXiv:1503.03923

[14] 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.
https://doi.org/10.1109/focs.2017.46
arXiv:1510.02082

[15] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm. arXiv:1411.4028.
arXiv:1411.4028

[16] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. arXiv:1412.6062.
arXiv:1412.6062

[17] E. Farhi, D. Gamarnik, and S. Gutmann. The quantum approximate optimization algorithm needs to see the whole graph: A typical case. arXiv:2004.09002.
arXiv:2004.09002

[18] J. Friedman. A proof of Alon's second eigenvalue conjecture and related problems. arXiv:cs/0405020, doi:10.1090/memo/0910.
https://doi.org/10.1090/memo/0910
arXiv:cs/0405020

[19] S. Hadfield. Quantum Algorithms for Scientific Computing and Approximate Optimization. Columbia University, 2018, arXiv:1805.03265.
arXiv:1805.03265

[20] J. Håstad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):798–859, 2001. doi:10.1145/258533.258536, URL http://www.cs.umd.edu/ gasarch/BLOGPAPERS/max3satl.pdf.
https://doi.org/10.1145/258533.258536
http://www.cs.umd.edu/~gasarch/BLOGPAPERS/max3satl.pdf

[21] 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.
https://doi.org/10.26421/qic13.5-6-3
arXiv:1201.3387

[22] M. B. Hastings. Classical and quantum bounded depth approximation algorithms. arXiv:1905.07047, doi:10.26421/qic19.13-14-3.
https://doi.org/10.26421/qic19.13-14-3
arXiv:1905.07047

[23] 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.
https://doi.org/10.21468/scipostphys.6.3.029
arXiv:1803.00026

[24] 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–21, 2017. arXiv:1402.2543, doi:10.37236/6862.
https://doi.org/10.37236/6862
arXiv:1402.2543

[25] C. Y.-Y. Lin and Y. Zhu. Performance of QAOA on typical instances of constraint satisfaction problems with bounded degree. arXiv:1601.01744.
arXiv:1601.01744

[26] 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.
https://doi.org/10.22331/q-2021-04-20-437
arXiv:2101.05513

[27] A. Montanari. Optimization of the Sherrington–Kirkpatrick Hamiltonian. arXiv:1812.10897, doi:10.1109/focs.2019.00087.
https://doi.org/10.1109/focs.2019.00087
arXiv:1812.10897

[28] P. Obszarski and A. Jastrzȩbski. Edge-coloring of 3-uniform hypergraphs. Discrete Applied Mathematics, 217:48–52, 2017, Combinatorial Optimization: Theory, Computation, and Applications. doi:10.1016/j.dam.2016.06.009.
https://doi.org/10.1016/j.dam.2016.06.009

[29] D. Panchenko. Introduction to the SK model. arXiv:1412.0170, doi:10.4310/cdm.2014.v2014.n1.a4.
https://doi.org/10.4310/cdm.2014.v2014.n1.a4
arXiv:1412.0170

[30] D. Panchenko. On the $k$-sat model with large number of clauses. arXiv:1608.06256, doi:10.1002/rsa.20748.
https://doi.org/10.1002/rsa.20748
arXiv:1608.06256

[31] 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–L121, apr 1980. doi:10.1088/0305-4470/13/4/009.
https://doi.org/10.1088/0305-4470/13/4/009

[32] S. Sen. Optimization on sparse random hypergraphs and spin glasses. arXiv:1606.02365, doi:10.1002/rsa.20774.
https://doi.org/10.1002/rsa.20774
arXiv:1606.02365

[33] R. Shaydulin, S. Hadfield, T. Hogg, and I. Safro. Classical symmetries and the quantum approximate optimization algorithm. Quantum Information Processing, 20(11):1–28, 2021. arXiv:2012.04713, doi:10.1007/s11128-021-03298-4.
https://doi.org/10.1007/s11128-021-03298-4
arXiv:2012.04713

[34] M. Talagrand. The Parisi formula. Annals of Mathematics, 163:221–263, 2006. doi:10.4007/annals.2006.163.221, URL https://annals.math.princeton.edu/wp-content/uploads/annals-v163-n1-p04.pdf.
https://doi.org/10.4007/annals.2006.163.221
https://annals.math.princeton.edu/wp-content/uploads/annals-v163-n1-p04.pdf

[35] 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.
https://doi.org/10.1103/PhysRevA.97.022304
arXiv:1706.02998

Cited by

[1] Ramin Fakhimi and Hamidreza Validi, Encyclopedia of Optimization 1 (2023) ISBN:978-3-030-54621-2.

[2] Rizwanul Alam, George Siopsis, Rebekah Herrman, James Ostrowski, Phillip C. Lotshaw, and Travis S. Humble, "Solving MaxCut with quantum imaginary time evolution", Quantum Information Processing 22 7, 281 (2023).

[3] Taylor L. Patti, Jean Kossaifi, Anima Anandkumar, and Susanne F. Yelin, "Variational quantum optimization with multibasis encodings", Physical Review Research 4 3, 033142 (2022).

[4] Stefan H. Sack, Raimel A. Medina, Richard Kueng, and Maksym Serbyn, "Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement", Physical Review A 107 6, 062404 (2023).

[5] Ojas Parekh, "Synergies Between Operations Research and Quantum Information Science", INFORMS Journal on Computing 35 2, 266 (2023).

[6] Camille Grange, Michael Poss, and Eric Bourreau, "An introduction to variational quantum algorithms for combinatorial optimization problems", 4OR 21 3, 363 (2023).

[7] Stuart Hadfield, Tad Hogg, and Eleanor G Rieffel, "Analytical framework for quantum alternating operator ansätze", Quantum Science and Technology 8 1, 015017 (2023).

[8] Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou, "The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model", arXiv:2110.14206, (2021).

[9] Yash J. Patel, Sofiene Jerbi, Thomas Bäck, and Vedran Dunjko, "Reinforcement Learning Assisted Recursive QAOA", arXiv:2207.06294, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2023-09-28 02:09:38) and SAO/NASA ADS (last updated successfully 2023-09-28 02:09:39). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.