Faster quantum and classical SDP approximations for quadratic binary optimization

Fernando G.S L. Brandão; Richard Kueng; Daniel Stilck França

doi:10.22331/q-2022-01-20-625

Faster quantum and classical SDP approximations for quadratic binary optimization

Fernando G.S L. Brandão^1,2,3, Richard Kueng^1,2,4, and Daniel Stilck França^5,6

¹Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA, USA
²Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA, USA
³AWS Center for Quantum Computing, Pasadena, CA, USA
⁴Institute for Integrated Circuits, Johannes Kepler University Linz, Austria
⁵QMATH, Department of Mathematical Sciences, University of Copenhagen, Denmark
⁶Department of Mathematics, Technische Universität München, Germany

Published:	2022-01-20, volume 6, page 625
Eprint:	arXiv:1909.04613v3
Doi:	https://doi.org/10.22331/q-2022-01-20-625
Citation:	Quantum 6, 625 (2022).

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

Abstract

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.

Featured image: Caricature of one iteration of the algorithm.

Popular summary

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

@article{GSLBrandao2022fasterquantum,
  doi = {10.22331/q-2022-01-20-625},
  url = {https://doi.org/10.22331/q-2022-01-20-625},
  title = {Faster quantum and classical {SDP} approximations for quadratic binary optimization},
  author = {G.S L. Brand{\~{a}}o, Fernando and Kueng, Richard and Stilck Fran{\c{c}}a, Daniel},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {625},
  month = jan,
  year = {2022}
}

► 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://doi.org/10.1088.
https://doi.org/10.1088/1742-5468/ab3988

[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://doi.org/10.1137/S0097539704441629.
https://doi.org/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://doi.org/10.1016/S0022-0000(03)00008-4.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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://doi.org/10.1145/2837020.
https://doi.org/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.
https://doi.org/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://doi.org/10.1088.
https://doi.org/10.1088/1367-2630/15/12/125020

[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://doi.org/10.1007/s00220-006-0150-x.
https://doi.org/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://doi.org/10.1007/978-1-4612-0653-8.
https://doi.org/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://dl.acm.org/doi/abs/10.5555/3157382.3157407.
https://dl.acm.org/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://doi.org/10.1017/CBO9780511804441.
https://doi.org/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.
https://doi.org/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://drops.dagstuhl.de/opus/volltexte/2019/10603.
https://doi.org/10.4230/LIPIcs.ICALP.2019.27
http://drops.dagstuhl.de/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://www.nowpublishers.com/article/Details/MAL-050.
https://doi.org/10.1561/2200000050
http://www.nowpublishers.com/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://doi.org/10.1007/s10107-004-0564-1.
https://doi.org/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://ieeexplore.ieee.org/document/1366224/.
https://doi.org/10.1109/FOCS.2004.39
http://ieeexplore.ieee.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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://doi.org/10.1088.
https://doi.org/10.1088/1367-2630/14/9/095022

[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://doi.org/10.4230/LIPIcs.TQC.2021.7.
https://doi.org/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.
https://doi.org/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://doi.org/10.1007/s004930050052.
https://doi.org/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://doi.org/10.1103/PhysRevLett.100.160501.
https://doi.org/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://gateway.proquest.com/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.
https://doi.org/10.7907/3K1S-R458
http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqm&rft_dat=xri:pqdiss:3609482

[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://doi.org/10.1145/227683.227684.
https://doi.org/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://iopscience.iop.org/article/10.1088/1751-8121/ab8111.
https://doi.org/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.
https://doi.org/10.1109/tit.2017.2719044

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

[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://doi.org/10.1073.
https://doi.org/10.1073/pnas.1523097113

[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://doi.org/10.1007/s00220-016-2641-8.
https://doi.org/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://dl.acm.org/doi/10.1145/3406306.
https://doi.org/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://doi.org/10.1007/s00220-003-0955-9.
https://doi.org/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://doi.org/10.1002.
https://doi.org/10.1002/cpa.21450

[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.
arXiv:1907.13602

[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://doi.org/10.1137/19M1278612.
https://doi.org/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://doi.org/10.1016/j.acha.2015.07.007.
https://doi.org/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://link.springer.com/10.1007/s10107-020-01558-2.
https://doi.org/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.
https://doi.org/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://doi.org/10.1090/S0002-9939-04-07800-1.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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://dl.acm.org/citation.cfm?doid=3313276.3316386.
https://doi.org/10.1145/3313276.3316386
http://dl.acm.org/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://proceedings.mlr.press/v65/mei17a.html.
https://proceedings.mlr.press/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.
https://doi.org/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://dl.acm.org/doi/10.1145/2897518.2897548.
https://doi.org/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.
arXiv:0912.0336

[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://doi.acm.org/10.1145/2897518.2897544.
https://doi.org/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.
https://doi.org/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://doi.org/10.1007/978-1-4614-6289-7.
https://doi.org/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://doi.org/10.1103/PhysRevLett.103.220502.
https://doi.org/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://doi.org/10.1016/j.aim.2017.11.001.
https://doi.org/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://msp.org/pjm/1958/8-1/p14.xhtml.
https://doi.org/10.2140/pjm.1958.8.171
http://msp.org/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://doi.org/10.1137/08074489X.
https://doi.org/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://link.springer.com/10.1007/978-3-642-15202-3_6.
https://doi.org/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.
https://doi.org/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://doi.org/10.1137/17M1111590.
https://doi.org/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://drops.dagstuhl.de/opus/volltexte/2019/10675.
https://doi.org/10.4230/LIPIcs.ICALP.2019.99
http://drops.dagstuhl.de/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.
https://doi.org/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://www.pnas.org/content/109/3/754.
https://doi.org/10.1073/pnas.1111758109
http://www.pnas.org/content/109/3/754

Cited by

[1] Jeremy Côté, Frédéric Sauvage, Martín Larocca, Matías Jonsson, Lukasz Cincio, and Tameem Albash, "Diabatic quantum annealing for the frustrated ring model", Quantum Science and Technology 8 4, 045033 (2023).

[2] Álvaro M. Alhambra, "Quantum Many-Body Systems in Thermal Equilibrium", PRX Quantum 4 4, 040201 (2023).

[3] Alexander M. Dalzell, B. David Clader, Grant Salton, Mario Berta, Cedric Yen-Yu Lin, David A. Bader, Nikitas Stamatopoulos, Martin J. A. Schuetz, Fernando G. S. L. Brandão, Helmut G. Katzgraber, and William J. Zeng, "End-To-End Resource Analysis for Quantum Interior-Point Methods and Portfolio Optimization", PRX Quantum 4 4, 040325 (2023).

[4] Xiumei Zhao, Yongmei Li, Jing Li, Shasha Wang, Song Wang, Sujuan Qin, and Fei Gao, "Near-term quantum algorithm for solving the MaxCut problem with fewer quantum resources", Physica A: Statistical Mechanics and its Applications 648, 129951 (2024).

[5] Hongyi Zhou, Sirui Peng, Qian Li, and Xiaoming Sun, "A hybrid algorithm for quadratically constrained quadratic optimization problems", Physica Scripta 99 6, 065052 (2024).

[6] Iria W. Wang, Robin Brown, Taylor L. Patti, Anima Anandkumar, Marco Pavone, and Susanne F. Yelin, "Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives", Quantum 10, 2076 (2026).

[7] Viet T. Tran and Richard Kueng, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 1599 (2025) ISBN:979-8-3315-5736-2.

[8] Rodolfo A. Quintero and Luis F. Zuluaga, Encyclopedia of Optimization 1 (2023) ISBN:978-3-030-54621-2.

[9] Adriano Baldeschi and Giuseppe Bruno, "Quantum Computing Winks at Statistics. Is It a Good Match?", SSRN Electronic Journal (2024).

[10] Thomas Beck, Alessandro Baroni, Ryan Bennink, Gilles Buchs, Eduardo Antonio Coello Pérez, Markus Eisenbach, Rafael Ferreira da Silva, Muralikrishnan Gopalakrishnan Meena, Kalyan Gottiparthi, Peter Groszkowski, Travis S. Humble, Ryan Landfield, Ketan Maheshwari, Sarp Oral, Michael A. Sandoval, Amir Shehata, In-Saeng Suh, and Christopher Zimmer, "Integrating quantum computing resources into scientific HPC ecosystems", Future Generation Computer Systems 161, 11 (2024).

[11] Haomu Yuan, Christopher K Long, Hugo V Lepage, and Crispin H W Barnes, "Quantifying the advantages of applying quantum approximate algorithms to portfolio optimisation", Quantum Science and Technology 11 2, 025034 (2026).

[12] Tom Peham, Nina Brandl, Richard Kueng, Robert Wille, and Lukas Burgholzer, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 802 (2023) ISBN:979-8-3503-4323-6.

[13] Jonathan Wei Zhong Lau, Kian Hwee Lim, Kishor Bharti, Leong-Chuan Kwek, and Sai Vinjanampathy, "Convex Optimization for Nonequilibrium Steady States on a Hybrid Quantum Processor", Physical Review Letters 130 24, 240601 (2023).

[14] Ruho Kondo, Yuki Sato, Rudy Raymond, and Naoki Yamamoto, "Recursive Quantum Relaxation for Combinatorial Optimization Problems", Quantum 9, 1594 (2025).

[15] Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, Sander Gribling, Swati Gupta, Stuart Hadfield, Raoul Heese, Gerhard Kircher, Thomas Kleinert, Thorsten Koch, Georgios Korpas, Steve Lenk, Jakub Marecek, Vanio Markov, Guglielmo Mazzola, Stefano Mensa, Naeimeh Mohseni, Giacomo Nannicini, Corey O’Meara, Elena Peña Tapia, Sebastian Pokutta, Manuel Proissl, Patrick Rebentrost, Emre Sahin, Benjamin C. B. Symons, Sabine Tornow, Víctor Valls, Stefan Woerner, Mira L. Wolf-Bauwens, Jon Yard, Sheir Yarkoni, Dirk Zechiel, Sergiy Zhuk, and Christa Zoufal, "Challenges and opportunities in quantum optimization", Nature Reviews Physics 6 12, 718 (2024).

[16] Taylor L. Patti, Jean Kossaifi, Anima Anandkumar, and Susanne F. Yelin, "Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints", Quantum 7, 1057 (2023).

[17] Brandon Augustino, Giacomo Nannicini, Tamás Terlaky, and Luis F. Zuluaga, "Quantum Interior Point Methods for Semidefinite Optimization", Quantum 7, 1110 (2023).

[18] Paul K. Faehrmann, Jens Eisert, Mária Kieferová, and Richard Kueng, "Short-time simulation of quantum dynamics by Pauli measurements", Physical Review A 112 1, 012602 (2025).

[19] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

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

[21] Tom Peham, Nina Brandl, Richard Kueng, Robert Wille, and Lukas Burgholzer, "Depth-Optimal Synthesis of Clifford Circuits with SAT Solvers", arXiv:2305.01674, (2023).

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

[23] 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", IEEE Transactions on Quantum Engineering 1, TQE.2020.3030314 (2020).

[24] 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, (2020).

[25] Claudio Gambella and Andrea Simonetto, "Multiblock ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers", IEEE Transactions on Quantum Engineering 1, TQE.2020.3033139 (2020).

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

[27] Stuart Harwood, Claudio Gambella, Dimitar Trenev, Andrea Simonetto, David Bernal Neira, and Donny Greenberg, "FormulatingandSolvingRoutingProblems on Quantum Computers", IEEE Transactions on Quantum Engineering 2, TQE.2021 (2021).

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

[29] Iordanis Kerenidis, Anupam Prakash, and Dániel Szilágyi, "Quantum algorithms for Second-Order Cone Programming and Support Vector Machines", Quantum 5, 427 (2021).

[30] Thomas Beck, Alessandro Baroni, Ryan Bennink, Gilles Buchs, Eduardo Antonio Coello Perez, Markus Eisenbach, Rafael Ferreira da Silva, Muralikrishnan Gopalakrishnan Meena, Kalyan Gottiparthi, Peter Groszkowski, Travis S. Humble, Ryan Landfield, Ketan Maheshwari, Sarp Oral, Michael A. Sandoval, Amir Shehata, In-Saeng Suh, and Christopher Zimmer, "Integrating Quantum Computing Resources into Scientific HPC Ecosystems", arXiv:2408.16159, (2024).

[31] Ruho Kondo, Yuki Sato, Rudy Raymond, and Naoki Yamamoto, "Recursive Quantum Relaxation for Combinatorial Optimization Problems", arXiv:2403.02045, (2024).

[32] Fabian Henze, Viet Tran, Birte Ostermann, Richard Kueng, Timo de Wolff, and David Gross, "Solving quadratic binary optimization problems using quantum SDP methods: Non-asymptotic running time analysis", arXiv:2502.15426, (2025).

[33] Lennart Binkowski, "Practical lower bounds for hybrid quantum interior point methods in linear programming", arXiv:2604.24362, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-07 05:33:49) and SAO/NASA ADS (last updated successfully 2026-08-06 16:31:14). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-08-07 05:33:49: Cannot retrieve data from ADS due to rate limitations.

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.