Faster quantum and classical SDP approximations for quadratic binary optimization

Fernando G.S L. Brandão1,2,3, Richard Kueng1,2,4, and Daniel Stilck França5,6

1Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA, USA
2Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA, USA
3AWS Center for Quantum Computing, Pasadena, CA, USA
4Institute for Integrated Circuits, Johannes Kepler University Linz, Austria
5QMATH, Department of Mathematical Sciences, University of Copenhagen, Denmark
6Department of Mathematics, Technische Universität München, Germany

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


We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. Such instances include approximating the ground state of spin glasses and MaxCut on Erdös-Rényi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem.

Quadratic unconstrained binary optimization problems (QUBO) are prototypical NP-complete problems. Many hard combinatorial problems like the maximum cut of a graph can be easily formulated in this framework, and they find applications in many areas of science and industry. We don’t expect computers – including quantum computers – to solve general QUBOs efficiently. However, the pioneering work of Goemans and Williamson has shown that they do admit an efficient relaxation in the form of a semidefinite program (SDP). Remarkably, by solving this relaxation, it is possible to obtain a solution that is a constant fraction away from the optimal one.

In contrast to QUBOs, classical SDP solvers do not require exponential resources. Runtime and memory do, however, scale superlinearly in problem size (dimension and number of constraints). Recent works have shown that quantum computers hold the promise of further speeding up the solution of SDPs. However, these assertions depend on the underlying problem structure. When applied to SDP relaxations of QUBOs, the obtained runtime is not competitive.

This work bridges this gap and shows how to obtain quantum speedups for this important class of problems by developing a new quantum algorithm. It has a better runtime for random instance of QUBOs when compared to both existing classical and quantum approaches. To achieve this speedup, the authors exploit that the constraints of the SDP have a natural interpretation in quantum information theory: the feasible points are approximately indistinguishable from the maximally mixed state when measured in the computational basis. This interpretation gives rise to a simple way of checking whether a candidate solution is feasible on a quantum computer and how to update it accordingly if it is not.

► BibTeX data

► References

[1] S. Aaronson, X. Chen, E. Hazan, S. Kale, and A. Nayak. Online learning of quantum states. Journal of Statistical Mechanics: Theory and Experiment, 2019 (12): 124019, 2019. 10.1088/​1742-5468/​ab3988. URL https:/​/​​10.1088.

[2] N. Alon and A. Naor. Approximating the cut-norm via Grothendieck's inequality. SIAM J. Comput., 35 (4): 787–803, 2006. ISSN 0097-5397. 10.1137/​S0097539704441629. URL https:/​/​​10.1137/​S0097539704441629.

[3] N. Alon, W. Fernandez de la Vega, R. Kannan, and M. Karpinski. Random sampling and approximation of MAX-CSPs. volume 67, pages 212–243. 2003. 10.1016/​S0022-0000(03)00008-4. URL https:/​/​​10.1016/​S0022-0000(03)00008-4.

[4] S. Apers and R. de Wolf. Quantum speedup for graph sparsification, cut approximation and laplacian solving. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 637–648, 2020. 10.1109/​FOCS46700.2020.00065.

[5] H. Araki and E. H. Lieb. Entropy inequalities. Communications in Mathematical Physics, 18 (2): 160–170, jun 1970. 10.1007/​bf01646092.

[6] S. Arora and S. Kale. A combinatorial, primal-dual approach to semidefinite programs. J. ACM, 63 (2): Art. 12, 35, 2016. ISSN 0004-5411. 10.1145/​2837020. URL https:/​/​​10.1145/​2837020.

[7] S. Arora, E. Hazan, and S. Kale. Fast algorithms for approximate semidefinite programming using the multiplicative weights update method. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pages 339–348, 2005. 10.1109/​SFCS.2005.35.

[8] K. Banaszek, M. Cramer, and D. Gross. Focus on quantum tomography. New Journal of Physics, 15 (12): 125020, 2013. 10.1088/​1367-2630/​15/​12/​125020. URL https:/​/​​10.1088.

[9] D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders. Efficient quantum algorithms for simulating sparse Hamiltonians. Comm. Math. Phys., 270 (2): 359–371, 2007. ISSN 0010-3616. 10.1007/​s00220-006-0150-x. URL https:/​/​​10.1007/​s00220-006-0150-x.

[10] R. Bhatia. Matrix analysis, volume 169 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1997. ISBN 0-387-94846-5. 10.1007/​978-1-4612-0653-8. URL https:/​/​​10.1007/​978-1-4612-0653-8.

[11] N. Boumal, V. Voroninski, and A. Bandeira. The non-convex Burer-Monteiro approach works on smooth semidefinite programs. In Advances in Neural Information Processing Systems 29, pages 2757–2765. Curran Associates, Inc., 2016. URL https:/​/​​doi/​abs/​10.5555/​3157382.3157407.

[12] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge University Press, Cambridge, 2004. ISBN 0-521-83378-7. 10.1017/​CBO9780511804441. URL https:/​/​​10.1017/​CBO9780511804441.

[13] F. G. Brandao and K. M. Svore. Quantum speed-ups for solving semidefinite programs. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2017. 10.1109/​focs.2017.45.

[14] F. G. S. L. Brandão, A. Kalev, T. Li, C. Y.-Y. Lin, K. M. Svore, and X. Wu. Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:14, 2019. ISBN 978-3-95977-109-2. 10.4230/​LIPIcs.ICALP.2019.27. URL http:/​/​​opus/​volltexte/​2019/​10603.

[15] S. Bubeck. Convex Optimization: Algorithms and Complexity. Foundations and Trends® in Machine Learning, 8 (3-4): 231–357, 2015. ISSN 1935-8237. 10.1561/​2200000050. URL http:/​/​​article/​Details/​MAL-050.

[16] S. Burer and R. D. C. Monteiro. Local minima and convergence in low-rank semidefinite programming. Math. Program., 103 (3, Ser. A): 427–444, 2005. ISSN 0025-5610. 10.1007/​s10107-004-0564-1. URL https:/​/​​10.1007/​s10107-004-0564-1.

[17] M. Charikar and A. Wirth. Maximizing Quadratic Programs: Extending Grothendieck's Inequality. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 54–60. IEEE, 2004. ISBN 0-7695-2228-9. 10.1109/​FOCS.2004.39. URL http:/​/​​document/​1366224/​.

[18] A. M. Childs and N. Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Inf. Comput., 12 (11-12): 901–924, 2012. ISSN 1533-7146. 10.26421/​qic12.11-12.

[19] A. N. Chowdhury and R. D. Somma. Quantum algorithms for Gibbs sampling and hitting-time estimation. Quantum Inf. Comput., 17 (1-2): 41–64, 2017. ISSN 1533-7146. 10.26421/​QIC17.1-2-3.

[20] A. Dembo, A. Montanari, and S. Sen. Extremal Cuts of Sparse Random Graphs. The Annals of Probability, 45 (2): 1190–1217, Mar. 2017. ISSN 0091-1798. 10.1214/​15-AOP1084.

[21] S. T. Flammia, D. Gross, Y.-K. Liu, and J. Eisert. Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators. New Journal of Physics, 14 (9): 095022, 2012. 10.1088/​1367-2630/​14/​9/​095022. URL https:/​/​​10.1088.

[22] D. S. França, F. G. S. L. Brandão, and R. Kueng. Fast and robust quantum state tomography from few basis measurements. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2021, July 5-8, 2021, Virtual Conference, volume 197 of LIPIcs, pages 7:1–7:13, 2021. 10.4230/​LIPIcs.TQC.2021.7. URL https:/​/​​10.4230/​LIPIcs.TQC.2021.7.

[23] D. S. França. Perfect sampling for quantum Gibbs states. Quantum Inf. Comput., 18 (5-6): 361–388, 2018. ISSN 1533-7146. 10.26421/​qic18.5-6.

[24] A. Frieze and R. Kannan. Quick approximation to matrices and applications. Combinatorica, 19 (2): 175–220, 1999. ISSN 0209-9683. 10.1007/​s004930050052. URL https:/​/​​10.1007/​s004930050052.

[25] V. Giovannetti, S. Lloyd, and L. Maccone. Quantum random access memory. Phys. Rev. Lett., 100 (16): 160501, 4, 2008. ISSN 0031-9007. 10.1103/​PhysRevLett.100.160501. URL https:/​/​​10.1103/​PhysRevLett.100.160501.

[26] A. Gittens. Topics in Randomized Numerical Linear Algebra. ProQuest LLC, Ann Arbor, MI, 2013. ISBN 978-1303-68348-0. 10.7907/​3K1S-R458. URL http:/​/​​openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/​fmt:kev:mtx:dissertation&res_dat=xri:pqm&rft_dat=xri:pqdiss:3609482. Thesis (Ph.D.)–California Institute of Technology.

[27] M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach., 42 (6): 1115–1145, 1995. ISSN 0004-5411. 10.1145/​227683.227684. URL https:/​/​​10.1145/​227683.227684.

[28] M. Guţă, J. Kahn, R. Kueng, and J. A. Tropp. Fast state tomography with optimal error bounds. Journal of Physics A: Mathematical and Theoretical, 53 (20): 204001, May 2020. ISSN 1751-8113, 1751-8121. 10.1088/​1751-8121/​ab8111. URL https:/​/​​article/​10.1088/​1751-8121/​ab8111.

[29] J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu. Sample-optimal tomography of quantum states. IEEE Transactions on Information Theory, 2017. 10.1109/​tit.2017.2719044.

[30] E. Hazan. Introduction to Online Convex Optimization. now Publishers Inc, 2016. 10.1561/​9781680831719. URL https:/​/​​10.1561.

[31] A. Javanmard, A. Montanari, and F. Ricci-Tersenghi. Phase transitions in semidefinite relaxations. Proceedings of the National Academy of Sciences, 113 (16): E2218–E2223, mar 2016. 10.1073/​pnas.1523097113. URL https:/​/​​10.1073.

[32] M. J. Kastoryano and F. G. S. L. Brandão. Quantum Gibbs samplers: the commuting case. Comm. Math. Phys., 344 (3): 915–957, 2016. ISSN 0010-3616. 10.1007/​s00220-016-2641-8. URL https:/​/​​10.1007/​s00220-016-2641-8.

[33] I. Kerenidis and A. Prakash. A Quantum Interior Point Method for LPs and SDPs. ACM Transactions on Quantum Computing, 1 (1): 1–32, Dec. 2020. ISSN 2643-6809, 2643-6817. 10.1145/​3406306. URL https:/​/​​doi/​10.1145/​3406306.

[34] C. King. Inequalities for trace norms of $2\times 2$ block matrices. Comm. Math. Phys., 242 (3): 531–545, 2003. ISSN 0010-3616. 10.1007/​s00220-003-0955-9. URL https:/​/​​10.1007/​s00220-003-0955-9.

[35] A. Knowles and J. Yin. The isotropic semicircle law and deformation of Wigner matrices. Communications on Pure and Applied Mathematics, 66 (11): 1663–1749, apr 2013. 10.1002/​cpa.21450. URL https:/​/​​10.1002.

[36] T. G. Kolda. Limited-memory matrix methods with applications. PhD thesis, University of Michigan, 1998.

[37] R. Kueng and J. A. Tropp. Binary component decomposition Part II: the asymmetric case. arXiv preprint arXiv:1907.13602, 2019.

[38] R. Kueng and J. A. Tropp. Binary component decomposition part I: the positive-semidefinite case. SIAM J. Math. Data Sci., 3 (2): 544–572, 2021. 10.1137/​19M1278612. URL https:/​/​​10.1137/​19M1278612.

[39] R. Kueng, H. Rauhut, and U. Terstiege. Low rank matrix recovery from rank one measurements. Appl. Comput. Harmon. Anal., 42 (1): 88–116, 2017. ISSN 1063-5203. 10.1016/​j.acha.2015.07.007. URL https:/​/​​10.1016/​j.acha.2015.07.007.

[40] D. Kunisky and A. S. Bandeira. A tight degree 4 sum-of-squares lower bound for the Sherrington–Kirkpatrick Hamiltonian. Mathematical Programming, Nov. 2020. ISSN 0025-5610, 1436-4646. 10.1007/​s10107-020-01558-2. URL http:/​/​​10.1007/​s10107-020-01558-2.

[41] R. Kyng, Y. T. Lee, R. Peng, S. Sachdeva, and D. A. Spielman. Sparsified Cholesky and multigrid solvers for connection Laplacians. In STOC'16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 842–850. ACM, New York, 2016. 10.1145/​2897518.2897640.

[42] R. Latala. Some estimates of norms of random matrices. Proc. Amer. Math. Soc., 133 (5): 1273–1282, 2005. ISSN 0002-9939. 10.1090/​S0002-9939-04-07800-1. URL https:/​/​​10.1090/​S0002-9939-04-07800-1.

[43] J. R. Lee, P. Raghavendra, and D. Steurer. Lower bounds on the size of semidefinite programming relaxations. In STOC'15—Proceedings of the 2015 ACM Symposium on Theory of Computing, pages 567–576. ACM, New York, 2015a. 10.1145/​2746539.2746599.

[44] Y. T. Lee, A. Sidford, and S. C.-W. Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015, pages 1049–1065. IEEE Computer Soc., Los Alamitos, CA, 2015b. 10.1109/​FOCS.2015.68.

[45] G. H. Low. Hamiltonian simulation with nearly optimal dependence on spectral norm. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019, pages 491–502, New York, New York, USA, 2019. ACM Press. ISBN 9781450367059. 10.1145/​3313276.3316386. URL http:/​/​​citation.cfm?doid=3313276.3316386.

[46] S. Mei, T. Misiakiewicz, A. Montanari, and R. I. Oliveira. Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality. In Conference on learning theory, pages 1476–1515. PMLR, 2017. URL https:/​/​​v65/​mei17a.html.

[47] A. Montanari. Optimization of the Sherrington-Kirkpatrick hamiltonian. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1417–1433, 2019. 10.1109/​FOCS.2019.00087.

[48] A. Montanari and S. Sen. Semidefinite programs on sparse random graphs and their application to community detection. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 814–827, Cambridge MA USA, June 2016. ACM. ISBN 978-1-4503-4132-5. 10.1145/​2897518.2897548. URL https:/​/​​doi/​10.1145/​2897518.2897548.

[49] M. A. Nielsen and I. L. Chuang. Quantum computation and quantum information. Cambridge University Press, Cambridge, 2000. ISBN 0-521-63235-8; 0-521-63503-9.

[50] V. Nikiforov. Cut-norms and spectra of matrices. arXiv preprint arXiv:0912.0336, 2009.

[51] R. O'Donnell and J. Wright. Efficient quantum tomography. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 899–912, New York, NY, USA, 2016. ACM. ISBN 978-1-4503-4132-5. 10.1145/​2897518.2897544. URL http:/​/​​10.1145/​2897518.2897544.

[52] D. O'Leary and S. Peleg. Digital image compression by outer product expansion. IEEE Transactions on Communications, 31 (3): 441–444, 1983. ISSN 0090-6778. 10.1109/​TCOM.1983.1095823.

[53] D. Panchenko. The Sherrington-Kirkpatrick model. Springer Monographs in Mathematics. Springer, New York, 2013. ISBN 978-1-4614-6288-0; 978-1-4614-6289-7. 10.1007/​978-1-4614-6289-7. URL https:/​/​​10.1007/​978-1-4614-6289-7.

[54] D. Poulin and P. Wocjan. Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer. Phys. Rev. Lett., 103 (22): 220502, 4, 2009. ISSN 0031-9007. 10.1103/​PhysRevLett.103.220502. URL https:/​/​​10.1103/​PhysRevLett.103.220502.

[55] A. Prakash. Quantum algorithms for linear algebra and machine learning. PhD thesis, University of California, Berkeley, 2014.

[56] E. Rebrova and R. Vershynin. Norms of random matrices: local and global problems. Adv. Math., 324: 40–83, 2018. ISSN 0001-8708. 10.1016/​j.aim.2017.11.001. URL https:/​/​​10.1016/​j.aim.2017.11.001.

[57] M. Sion. On general minimax theorems. Pacific Journal of Mathematics, 8 (1): 171–176, Mar. 1958. ISSN 0030-8730, 0030-8730. 10.2140/​pjm.1958.8.171. URL http:/​/​​pjm/​1958/​8-1/​p14.xhtml.

[58] D. A. Spielman and S.-H. Teng. Spectral sparsification of graphs. SIAM J. Comput., 40 (4): 981–1025, 2011. ISSN 0097-5397. 10.1137/​08074489X. URL https:/​/​​10.1137/​08074489X.

[59] M. Talagrand. The Diluted SK Model and the K-Sat Problem. In Mean Field Models for Spin Glasses, pages 325–395. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011. ISBN 978-3-642-15201-6 978-3-642-15202-3. 10.1007/​978-3-642-15202-3_6. URL http:/​/​​10.1007/​978-3-642-15202-3_6.

[60] K. Temme, T. J. Osborne, K. G. Vollbrecht, D. Poulin, and F. Verstraete. Quantum metropolis sampling. Nature, 471 (7336): 87–90, mar 2011. 10.1038/​nature09770.

[61] J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher. Practical sketching algorithms for low-rank matrix approximation. SIAM J. Matrix Anal. Appl., 38 (4): 1454–1485, 2017. ISSN 0895-4798. 10.1137/​17M1111590. URL https:/​/​​10.1137/​17M1111590.

[62] K. Tsuda, G. Rätsch, and M. K. Warmuth. Matrix exponentiated gradient updates for on-line learning and bregman projection. J. Mach. Learn. Res., 6: 995–1018, dec 2005. ISSN 1532-4435.

[63] J. van Apeldoorn and A. Gilyén. Improvements in Quantum SDP-Solving with Applications. In C. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 99:1–99:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-109-2. 10.4230/​LIPIcs.ICALP.2019.99. URL http:/​/​​opus/​volltexte/​2019/​10675.

[64] J. van Apeldoorn, A. Gilyén, S. Gribling, and R. de Wolf. Quantum SDP-solvers: better upper and lower bounds. In 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017, pages 403–414. IEEE Computer Soc., Los Alamitos, CA, 2017. 10.1109/​focs.2017.44.

[65] M.-H. Yung and A. Aspuru-Guzik. A quantum–quantum metropolis algorithm. Proceedings of the National Academy of Sciences, 109 (3): 754–759, 2012. ISSN 0027-8424. 10.1073/​pnas.1111758109. URL http:/​/​​content/​109/​3/​754.

Cited by

[1] Daniel Stilck França and Raul García-Patrón, "Limitations of optimization algorithms on noisy quantum devices", Nature Physics 17 11, 1221 (2021).

[2] Arbel Haim, Richard Kueng, and Gil Refael, "Variational-Correlations Approach to Quantum Many-body Problems", arXiv:2001.06510.

[3] Daniel J. Egger, Claudio Gambella, Jakub Marecek, Scott McFaddin, Martin Mevissen, Rudy Raymond, Andrea Simonetto, Stefan Woerner, and Elena Yndurain, "Quantum Computing for Finance: State of the Art and Future Prospects", arXiv:2006.14510.

[4] Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, and Mehdi Soleimanifar, "Sample-efficient learning of interacting quantum systems", Nature Physics 17 8, 931 (2021).

[5] Fernando G. S. L. Brandão, Richard Kueng, and Daniel Stilck França, "Fast and robust quantum state tomography from few basis measurements", arXiv:2009.08216.

[6] Claudio Gambella and Andrea Simonetto, "Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers", arXiv:2001.02069.

[7] Simon Apers and Ronald de Wolf, "Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving", arXiv:1911.07306.

[8] Iordanis Kerenidis, Anupam Prakash, and Dániel Szilágyi, "Quantum algorithms for Second-Order Cone Programming and Support Vector Machines", arXiv:1908.06720.

[9] Brandon Augustino, Giacomo Nannicini, Tamás Terlaky, and Luis F. Zuluaga, "Quantum Interior Point Methods for Semidefinite Optimization", arXiv:2112.06025.

The above citations are from SAO/NASA ADS (last updated successfully 2022-05-29 05:45:21). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2022-05-29 05:45:19).