quantum-computing

Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives

Quantum Science and Technology (arXiv overlay)

18 min read

0 likes

⚡ Quantum Brief

Researchers from Caltech, Stanford, and USC introduced Product-State Lifting (PSL), a quantum encoding method that extends variational quantum semidefinite programs (vQSDPs) to handle high-degree polynomial optimization problems without exponential resource costs. PSL transforms quadratic-focused vQSDPs into algorithms capable of solving k-degree polynomial objectives using only linear additional resources, avoiding the constraint explosion seen in classical semidefinite relaxations. The team demonstrated PSL by integrating it with a 2023 vQSDP framework using Hadamard tests, achieving competitive results for Max-kSAT—a benchmark NP-hard problem—while maintaining hardware-friendly circuit structures. Unlike classical approaches that inflate problem size when converting polynomials to quadratic forms, PSL preserves approximation quality by encoding higher-order terms via parallel product registers, keeping constraints constant regardless of polynomial degree. This work provides a near-term path to practical quantum advantage for real-world optimization tasks like logistics and scheduling, where higher-order variable interactions are critical but traditionally intractable for quantum devices.

Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives

Summarize this article with:

AbstractMany practically important NP-hard optimization problems are inherently higher-order polynomial optimizations, which are typically addressed using approximation algorithms. Classical relaxations express polynomial objectives over a polynomial basis and solve the resulting quadratic objective as a semidefinite program, which can significantly inflate problem size and degrade approximation behavior. Variational quantum analogues to classical semidefinite programs (vQSDPs) are near-term formulations geared towards quadratic objectives. We introduce Product-State Lifting (PSL), a simple product-register encoding that upgrades any vQSDP with basis-state encoding to tackle $k$-degree polynomial optimization. This upgrade requires only a linear increase in resources with constraints constant in $k$. As a worked example, we pair PSL with the recently-proposed vQSDP with the Hadamard test and approximate amplitude constraints [Quantum 7, 1057 (2023)], and outline an application to Max-$k$SAT. PSL maintains the device-friendly structure of vQSDPs while making polynomial degree a linear resource parameter, offering a general path from quadratic to polynomial optimization without the constraint growth typical of classical relaxations.Popular summaryMany important optimization problems, such as routing to scheduling, ask us to find the best choice among an enormous number of possibilities. Finding optimal solutions can be exponentially difficult, so both classical and quantum methods rely on approximation. A major challenge is that real-world problems often involve higher-order interactions between several variables at once. Standard approaches typically simplify these problems into quadratic ones, which makes the problem much larger and weakens the approximation. This paper proposes a method for elevating some existing quantum approximation algorithms for quadratic problems to target those higher-order problems more directly. The method, called Product-State Lifting (PSL), represents higher-degree interactions using several identical quantum registers together, allowing algorithms to maintain the same structure and constraints as in the simpler quadratic case. Importantly, required quantum resources grow only linearly with the degree of the problem. As a proof of concept, PSL was applied to the approximation algorithm [Quantum 7, 1057 (2023)], with simulations yielding results competitive with classical solutions.► BibTeX data@article{Wang2026elevating, doi = {10.22331/q-2026-04-21-2076}, url = {https://doi.org/10.22331/q-2026-04-21-2076}, title = {Elevating {V}ariational {Q}uantum {S}emidefinite {P}rograms for {P}olynomial {O}bjectives}, author = {Wang, Iria W. and Brown, Robin and Patti, Taylor L. and Anandkumar, Anima and Pavone, Marco and Yelin, Susanne F.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2076}, month = apr, year = {2026} }► References [1] 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). https://doi.org/10.22331/q-2023-07-12-1057 [2] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. ``Quantum machine learning''. Nature 549, 195–202 (2017). https://doi.org/10.1038/nature23474 [3] Yudong Cao, Jonathan Romero, Jonathan P. Olson, Matthias Degroote, Peter D. Johnson, Mária Kieferová, Ian D. Kivlichan, Tim Menke, Borja Peropadre, Nicolas P. D. Sawaya, Sukin Sim, Libor Veis, and Alán Aspuru-Guzik. ``Quantum chemistry in the age of quantum computing''. Chemical Reviews 119, 10856–10915 (2019). https://doi.org/10.1021/acs.chemrev.8b00803 [4] Ashley Montanaro. ``Quantum algorithms: an overview''. npj Quantum Information 2, 1–8 (2016). https://doi.org/10.1038/npjqi.2015.23 [5] John Preskill. ``Quantum computing in the nisq era and beyond''. Quantum 2, 79 (2018). https://doi.org/10.22331/q-2018-08-06-79 [6] Bernhard Korte and Jens Vygen. ``Introduction''. Page 1–13. Springer. Berlin, Heidelberg (2018). https://doi.org/10.1007/978-3-662-56039-6_1 [7] Jeremias Berg, Antti Hyttinen, and Matti Järvisalo. ``Applications of maxsat in data analysis''. In EPiC Series in Computing. Volume 59, page 50–64. EasyChair (2019). https://doi.org/10.29007/3qkh [8] Lieven Vandenberghe and Stephen Boyd. ``Semidefinite programming''. SIAM Review 38, 49–95 (1996). https://doi.org/10.1137/1038003 [9] Vijay V. Vazirani. ``Approximation algorithms''. Springer Link. (2001). url: https://link.springer.com/book/10.1007/978-3-662-04565-7. https://link.springer.com/book/10.1007/978-3-662-04565-7 [10] Shaowei Cai and Xindi Zhang. ``Pure maxsat and its applications to combinatorial optimization via linear local search''.

In Helmut Simonis, editor, Principles and Practice of Constraint Programming. Page 90–106. Cham (2020).

Springer International Publishing. https://doi.org/10.1007/978-3-030-58475-7_6 [11] Organizers of the 19th International Conference on Theory and Applications of Satisfiability Testing. ``The homepage of eleventh max-sat evaluation''. http://www.maxsat.udl.cat/16/index.html (2016). http://www.maxsat.udl.cat/16/index.html [12] Pablo A. Parrilo. ``Semidefinite programming relaxations for semialgebraic problems''. Mathematical Programming 96, 293–320 (2003). https://doi.org/10.1007/s10107-003-0387-5 [13] Michel X. Goemans and David P. Williamson. ``Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming''. Journal of the ACM 42, 1115–1145 (1995). https://doi.org/10.1145/227683.227684 [14] Randy Hickey and Fahiem Bacchus. ``Large neighbourhood search for anytime maxsat solving''. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022. Pages 1818–1824. ijcai.org (2022). https://doi.org/10.24963/IJCAI.2022/253 [15] Amir Ali Ahmadi. ``Sum of squares (sos) techniques: An introduction''. https://www.princeton.edu/ aaa/Public/Teaching/ORF523/S16/ORF523_S16_Lec15.pdf. https://www.princeton.edu/~aaa/Public/Teaching/ORF523/S16/ORF523_S16_Lec15.pdf [16] Stephen Prajna, Antonis Papachristodoulou, and Pablo A. Parrilo. ``Introducing sostools: a general purpose sum of squares programming solver''. In Proceedings of the 41st IEEE Conference on Decision and Control, 2002. Volume 1, page 741–746 vol.1. (2002). https://doi.org/10.1109/CDC.2002.1184594 [17] Bastian Harrach. ``Solving an inverse elliptic coefficient problem by convex non-linear semidefinite programming''. Optimization Letters 16, 1599–1609 (2022). https://doi.org/10.1007/s11590-021-01802-4 [18] Adrian Gepp, Geoff Harris, and Bruce Vanstone. ``Financial applications of semidefinite programming: a review and call for interdisciplinary research''. Accounting and Finance 60, 3527–3555 (2020). https://doi.org/10.1111/acfi.12543 [19] Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. ``Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning''.

In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano 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 für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2019.99 [21] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. ``Quantum sdp-solvers: Better upper and lower bounds''. Quantum 4, 230 (2020). https://doi.org/10.22331/q-2020-02-14-230 [22] Fernando G.S.L. Brandao and Krysta M. Svore. ``Quantum speed-ups for solving semidefinite programs''. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). Page 415–426. (2017). https://doi.org/10.1109/FOCS.2017.45 [23] Fernando G. S. L. Brandão, Richard Kueng, and Daniel Stilck França. ``Faster quantum and classical sdp approximations for quadratic binary optimization''. Quantum 6, 625 (2022). https://doi.org/10.22331/q-2022-01-20-625 [24] S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, X.-Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S.-T. Wang, M. Greiner, V. Vuletić, and M. D. Lukin. ``Quantum optimization of maximum independent set using rydberg atom arrays''. Science 376, 1209–1215 (2022). https://doi.org/10.1126/science.abo6587 [25] Tameem Albash and Daniel A. Lidar. ``Adiabatic quantum computation''. Reviews of Modern Physics 90, 015002 (2018). https://doi.org/10.1103/RevModPhys.90.015002 [26] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. ``Quantum computation by adiabatic evolution'' (2000). arXiv:quant-ph/0001106. arXiv:quant-ph/0001106 [27] Elizabeth Gibney. ``D-wave upgrade: How scientists are using the world’s most controversial quantum computer''. Nature 541, 447–448 (2017). https://doi.org/10.1038/541447b [28] Tadashi Kadowaki and Hidetoshi Nishimori. ``Quantum annealing in the transverse ising model''. Physical Review E 58, 5355–5363 (1998). https://doi.org/10.1103/PhysRevE.58.5355 [29] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm'' (2014). arXiv:1411.4028. arXiv:1411.4028 [30] J. M. Arrazola, V. Bergholm, K. Brádler, T. R. Bromley, M. J. Collins, I. Dhand, A. Fumagalli, T. Gerrits, A. Goussev, L. G. Helt, J. Hundal, T. Isacsson, R. B. Israel, J. Izaac, S. Jahangiri, R. Janik, N. Killoran, S. P. Kumar, J. Lavoie, A. E. Lita, D. H. Mahler, M. Menotti, B. Morrison, S. W. Nam, L. Neuhaus, H. Y. Qi, N. Quesada, A. Repingon, K. K. Sabapathy, M. Schuld, D. Su, J. Swinarton, A. Száva, K. Tan, P. Tan, V. D. Vaidya, Z. Vernon, Z. Zabaneh, and Y. Zhang. ``Quantum circuits with many photons on a programmable nanophotonic chip''. Nature 591, 54–60 (2021). https://doi.org/10.1038/s41586-021-03202-1 [31] Michael Lubasch, Jaewoo Joo, Pierre Moinier, Martin Kiffner, and Dieter Jaksch. ``Variational quantum algorithms for nonlinear problems''. Phys. Rev. A 101, 010301 (2020). https://doi.org/10.1103/PhysRevA.101.010301 [32] Albert J. Pool, Alejandro D. Somoza, Conor Mc Keever, Michael Lubasch, and Birger Horstmann. ``Nonlinear dynamics as a ground-state solution on quantum computers''. Phys. Rev. Res. 6, 033257 (2024). https://doi.org/10.1103/PhysRevResearch.6.033257 [33] Jingxuan Chen, Hanna Westerheim, Zoë Holmes, Ivy Luo, Theshani Nuradha, Dhrumil Patel, Soorya Rethinasamy, Kathie Wang, and Mark M. Wilde. ``Slack-variable approach for variational quantum semidefinite programming''. Physical Review A 112, 022607 (2025). https://doi.org/10.1103/lwxq-4myj [34] Dhrumil Patel, Patrick J. Coles, and Mark M. Wilde. ``Variational quantum algorithms for semidefinite programming''. Quantum 8, 1374 (2024). https://doi.org/10.22331/q-2024-06-17-1374 [35] Alex Lemon, Anthony Man-Cho So, and Yinyu Ye. ``Low-rank semidefinite programming: Theory and applications''. Foundations and Trends in Optimization 2, 1–156 (2016). https://doi.org/10.1561/2400000009 [36] H. van Maaren, L. van Norden, and M. J. H. Heule. ``Sums of squares based approximation algorithms for max-sat''.

Discrete Applied Mathematics 156, 1754–1779 (2008). https://doi.org/10.1016/j.dam.2007.08.036 [37] Colin Howson. ``Logic with trees: An introduction to symbolic logic''. Routledge. New York (1997). https://doi.org/10.4324/9780203976739 [38] Taylor L. Patti, Khadijeh Najafi, Xun Gao, and Susanne F. Yelin. ``Entanglement devised barren plateau mitigation''.

Physical Review Research 3, 033090 (2021). https://doi.org/10.1103/PhysRevResearch.3.033090 [39] Huan-Yu Liu, Tai-Ping Sun, Yu-Chun Wu, Yong-Jian Han, and Guo-Ping Guo. ``Mitigating barren plateaus with transfer-learning-inspired parameter initializations''. New Journal of Physics 25, 013039 (2023). https://doi.org/10.1088/1367-2630/acb58e [40] Shahin Hakemi, Mahboobeh Houshmand, Esmaeil KheirKhah, and Seyyed Abed Hosseini. ``A review of recent advances in quantum-inspired metaheuristics''. Evolutionary Intelligence 17, 627–642 (2024). https://doi.org/10.1007/s12065-022-00783-2 [41] Organizers of the Annual International Conference on Theory and Applications of Satisfiability Testing. ``Maxsat evaluations''. https://maxsat-evaluations.github.io/. https://maxsat-evaluations.github.io/ [42] Matthew B. Hastings. ``Perturbation theory and the sum of squares'' (2024). arXiv:2205.12325. arXiv:2205.12325 [43] Andrew C. Doherty, Pablo A. Parrilo, and Federico M. Spedalieri. ``Complete family of separability criteria''. Physical Review A 69, 022308 (2004). https://doi.org/10.1103/PhysRevA.69.022308 [44] Taylor L. Patti, Jean Kossaifi, Susanne F. Yelin, and Anima Anandkumar. ``Tensorly-quantum: Quantum machine learning with tensor methods'' (2021). arXiv:2112.10239. arXiv:2112.10239Cited byCould not fetch Crossref cited-by data during last attempt 2026-04-21 09:42:35: Could not fetch cited-by data for 10.22331/q-2026-04-21-2076 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-04-21 09:42:36: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractMany practically important NP-hard optimization problems are inherently higher-order polynomial optimizations, which are typically addressed using approximation algorithms. Classical relaxations express polynomial objectives over a polynomial basis and solve the resulting quadratic objective as a semidefinite program, which can significantly inflate problem size and degrade approximation behavior. Variational quantum analogues to classical semidefinite programs (vQSDPs) are near-term formulations geared towards quadratic objectives. We introduce Product-State Lifting (PSL), a simple product-register encoding that upgrades any vQSDP with basis-state encoding to tackle $k$-degree polynomial optimization. This upgrade requires only a linear increase in resources with constraints constant in $k$. As a worked example, we pair PSL with the recently-proposed vQSDP with the Hadamard test and approximate amplitude constraints [Quantum 7, 1057 (2023)], and outline an application to Max-$k$SAT. PSL maintains the device-friendly structure of vQSDPs while making polynomial degree a linear resource parameter, offering a general path from quadratic to polynomial optimization without the constraint growth typical of classical relaxations.Popular summaryMany important optimization problems, such as routing to scheduling, ask us to find the best choice among an enormous number of possibilities. Finding optimal solutions can be exponentially difficult, so both classical and quantum methods rely on approximation. A major challenge is that real-world problems often involve higher-order interactions between several variables at once. Standard approaches typically simplify these problems into quadratic ones, which makes the problem much larger and weakens the approximation. This paper proposes a method for elevating some existing quantum approximation algorithms for quadratic problems to target those higher-order problems more directly. The method, called Product-State Lifting (PSL), represents higher-degree interactions using several identical quantum registers together, allowing algorithms to maintain the same structure and constraints as in the simpler quadratic case. Importantly, required quantum resources grow only linearly with the degree of the problem. As a proof of concept, PSL was applied to the approximation algorithm [Quantum 7, 1057 (2023)], with simulations yielding results competitive with classical solutions.► BibTeX data@article{Wang2026elevating, doi = {10.22331/q-2026-04-21-2076}, url = {https://doi.org/10.22331/q-2026-04-21-2076}, title = {Elevating {V}ariational {Q}uantum {S}emidefinite {P}rograms for {P}olynomial {O}bjectives}, author = {Wang, Iria W. and Brown, Robin and Patti, Taylor L. and Anandkumar, Anima and Pavone, Marco and Yelin, Susanne F.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2076}, month = apr, year = {2026} }► References [1] 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). https://doi.org/10.22331/q-2023-07-12-1057 [2] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. ``Quantum machine learning''. Nature 549, 195–202 (2017). https://doi.org/10.1038/nature23474 [3] Yudong Cao, Jonathan Romero, Jonathan P. Olson, Matthias Degroote, Peter D. Johnson, Mária Kieferová, Ian D. Kivlichan, Tim Menke, Borja Peropadre, Nicolas P. D. Sawaya, Sukin Sim, Libor Veis, and Alán Aspuru-Guzik. ``Quantum chemistry in the age of quantum computing''. Chemical Reviews 119, 10856–10915 (2019). https://doi.org/10.1021/acs.chemrev.8b00803 [4] Ashley Montanaro. ``Quantum algorithms: an overview''. npj Quantum Information 2, 1–8 (2016). https://doi.org/10.1038/npjqi.2015.23 [5] John Preskill. ``Quantum computing in the nisq era and beyond''. Quantum 2, 79 (2018). https://doi.org/10.22331/q-2018-08-06-79 [6] Bernhard Korte and Jens Vygen. ``Introduction''. Page 1–13. Springer. Berlin, Heidelberg (2018). https://doi.org/10.1007/978-3-662-56039-6_1 [7] Jeremias Berg, Antti Hyttinen, and Matti Järvisalo. ``Applications of maxsat in data analysis''. In EPiC Series in Computing. Volume 59, page 50–64. EasyChair (2019). https://doi.org/10.29007/3qkh [8] Lieven Vandenberghe and Stephen Boyd. ``Semidefinite programming''. SIAM Review 38, 49–95 (1996). https://doi.org/10.1137/1038003 [9] Vijay V. Vazirani. ``Approximation algorithms''. Springer Link. (2001). url: https://link.springer.com/book/10.1007/978-3-662-04565-7. https://link.springer.com/book/10.1007/978-3-662-04565-7 [10] Shaowei Cai and Xindi Zhang. ``Pure maxsat and its applications to combinatorial optimization via linear local search''.

In Helmut Simonis, editor, Principles and Practice of Constraint Programming. Page 90–106. Cham (2020).

Read Original

Source Information

Source: Quantum Science and Technology (arXiv overlay)

Website: https://quantum-journal.org/feed

Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives

Tags

Source Information