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

Kunal Marwaha1,2,3,4 and Stuart Hadfield1,2

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

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


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$.

► BibTeX data

► References

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

[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.

[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.

[4] A. E. Alaoui and A. Montanari. Algorithmic thresholds in mean field spin glasses. 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.

[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.

[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.

[8] B. Barak, A. Moitra, R. O'Donnell, et al. Beating the random assignment on constraint satisfaction problems of bounded degree. 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.

[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.

[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.

[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.

[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.

[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.

[15] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm. 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.

[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.

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

[19] S. Hadfield. Quantum Algorithms for Scientific Computing and Approximate Optimization. Columbia University, 2018, 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:/​/​​ 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.

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

[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.

[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.

[25] C. Y.-Y. Lin and Y. Zhu. Performance of QAOA on typical instances of constraint satisfaction problems with bounded degree. 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.

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

[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.

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

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

[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.

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

[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.

[34] M. Talagrand. The Parisi formula. Annals of Mathematics, 163:221–263, 2006. doi:10.4007/​annals.2006.163.221, URL https:/​/​​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.

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] Benjamin C B Symons, David Galvin, Emre Sahin, Vassil Alexandrov, and Stefano Mensa, "A practitioner’s guide to quantum algorithms for optimisation problems", Journal of Physics A: Mathematical and Theoretical 56 45, 453001 (2023).

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

[5] Nicolas PD Sawaya, Albert T Schmitz, and Stuart Hadfield, "Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems", Quantum 7, 1111 (2023).

[6] Stefan H. Sack and Daniel J. Egger, "Large-scale quantum approximate optimization on nonplanar graphs with machine learning noise mitigation", Physical Review Research 6 1, 013223 (2024).

[7] 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).

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

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

[10] Junaid ur Rehman, Hayder Al-Hraishawi, and Symeon Chatzinotas, ICC 2023 - IEEE International Conference on Communications 2674 (2023) ISBN:978-1-5386-7462-8.

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

[12] Maxime Dupont, Bram Evert, Mark J. Hodson, Bhuvanesh Sundar, Stephen Jeffrey, Yuki Yamaguchi, Dennis Feng, Filip B. Maciejewski, Stuart Hadfield, M. Sohaib Alam, Zhihui Wang, Shon Grabbe, P. Aaron Lott, Eleanor G. Rieffel, Davide Venturelli, and Matthew J. Reagor, "Quantum-enhanced greedy combinatorial optimization solver", Science Advances 9 45, eadi0487 (2023).

[13] 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).

[14] 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 2024-03-02 19:50:02) and SAO/NASA ADS (last updated successfully 2024-03-02 19:50:03). The list may be incomplete as not all publishers provide suitable and complete citation data.