Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints

Taylor L. Patti1,2, Jean Kossaifi2, Anima Anandkumar3,2, and Susanne F. Yelin1

1Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA
2NVIDIA, Santa Clara, California 95051, USA
3Department of Computing + Mathematical Sciences (CMS), California Institute of Technology (Caltech), Pasadena, CA 91125 USA

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


Semidefinite programs are optimization methods with a wide array of applications, such as approximating difficult combinatorial problems. One such semidefinite program is the Goemans-Williamson algorithm, a popular integer relaxation technique. We introduce a variational quantum algorithm for the Goemans-Williamson algorithm that uses only $n{+}1$ qubits, a constant number of circuit preparations, and $\text{poly}(n)$ expectation values in order to approximately solve semidefinite programs with up to $N=2^n$ variables and $M \sim O(N)$ constraints. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit, a technique known as the Hadamard Test. The Hadamard Test enables us to optimize the objective function by estimating only a single expectation value of the ancilla qubit, rather than separately estimating exponentially many expectation values. Similarly, we illustrate that the semidefinite programming constraints can be effectively enforced by implementing a second Hadamard Test, as well as imposing a polynomial number of Pauli string amplitude constraints. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems, including MaxCut. Our method exceeds the performance of analogous classical methods on a diverse subset of well-studied MaxCut problems from the GSet library.

Semidefinite programs allow us to approximate a wide array of hard problems, including NP-hard problems. One such semidefinite program is the Goemans-Williamson algorithm, which can solve hard problems, such as MaxCut. We introduce a variational quantum algorithm for the Goemans-Williamson algorithm that uses only $n{+}1$ qubits, a constant number of circuit preparations, and a polynomial number of expectation values in order to approximately solve semidefinite programs with an exponential number of variables and constraints. We encode the problem into a quantum circuit (or unitary) and read it out on a single auxilary qubit, a technique known as the Hadamard Test. Similarly, we illustrate that the problem constraints can be enforced by 1) a second Hadamard Test and 2) a polynomial number of Pauli string constraints. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems, including MaxCut. Our method exceeds the performance of analogous classical methods on a diverse subset of well-studied MaxCut problems.

► BibTeX data

► References

[1] Stephen P. Boyd and Lieven Vandenberghe. ``Convex optimization''. Cambridge Press. (2004).

[2] Michel X. Goemans. ``Semidefinite programming in combinatorial optimization''. Mathematical Programming 79, 143–161 (1997).

[3] Lieven Vandenberghe and Stephen Boyd. ``Applications of semidefinite programming''. Applied Numerical Mathematics 29, 283–299 (1999).

[4] Wenjun Li, Yang Ding, Yongjie Yang, R. Simon Sherratt, Jong Hyuk Park, and Jin Wang. ``Parameterized algorithms of fundamental np-hard problems: a survey''. Human-centric Computing and Information Sciences 10, 29 (2020).

[5] Christoph Helmberg. ``Semidefinite programming for combinatorial optimization''. Konrad-Zuse-Zentrum fur Informationstechnik Berlin. (2000).

[6] Michel X. Goemans and David P. Williamson. ``Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming''. J. ACM 42, 1115–1145 (1995).

[7] Florian A. Potra and Stephen J. Wright. ``Interior-point methods''. Journal of Computational and Applied Mathematics 124, 281–302 (2000).

[8] Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. ``A faster interior point method for semidefinite programming''. In 2020 IEEE 61st annual symposium on foundations of computer science (FOCS). Pages 910–918. IEEE (2020).

[9] Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, and Ruizhe Zhang. ``Solving sdp faster: A robust ipm framework and efficient implementation''. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). Pages 233–244. IEEE (2022).

[10] David P. Williamson and David B. Shmoys. ``The design of approximation algorithms''. Cambridge University Press. (2011).

[11] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn, et al. ``Quantum optimization using variational algorithms on near-term quantum devices''. Quantum Science and Technology 3, 030503 (2018).

[12] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. ``Quantum computation by adiabatic evolution'' (2000). arXiv:quant-ph/​0001106.

[13] Tameem Albash and Daniel A. Lidar. ``Adiabatic quantum computation''. Rev. Mod. Phys. 90, 015002 (2018).

[14] Sepehr Ebadi, Alexander Keesling, Madelyn Cain, Tout T Wang, Harry Levine, Dolev Bluvstein, Giulia Semeghini, Ahmed Omran, J-G Liu, Rhine Samajdar, et al. ``Quantum optimization of maximum independent set using rydberg atom arrays''. Science 376, 1209–1215 (2022).

[15] Tadashi Kadowaki and Hidetoshi Nishimori. ``Quantum annealing in the transverse ising model''. Phys. Rev. E 58, 5355–5363 (1998).

[16] Elizabeth Gibney. ``D-wave upgrade: How scientists are using the world's most controversial quantum computer''. Nature 541 (2017).

[17] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm''. arXiv (2014). arXiv:1411.4028.

[18] Juan M Arrazola, Ville Bergholm, Kamil Brádler, Thomas R Bromley, Matt J Collins, Ish Dhand, Alberto Fumagalli, Thomas Gerrits, Andrey Goussev, Lukas G Helt, et al. ``Quantum circuits with many photons on a programmable nanophotonic chip''. Nature 591, 54–60 (2021).

[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''. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) 132, 27:1–27:14 (2019).

[20] Joran Van Apeldoorn and András Gilyén. ``Improvements in quantum sdp-solving with applications''. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (2019).

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

[22] Fernando G.S.L. Brandão and Krysta M. Svore. ``Quantum speed-ups for solving semidefinite programs''. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). Pages 415–426. (2017).

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

[24] Dhrumil Patel, Patrick J. Coles, and Mark M. Wilde. ``Variational quantum algorithms for semidefinite programming'' (2021). arXiv:2112.08859.

[25] Anirban N. Chowdhury, Guang Hao Low, and Nathan Wiebe. ``A variational quantum algorithm for preparing quantum gibbs states'' (2020). arXiv:2002.00055.

[26] Taylor L Patti, Omar Shehab, Khadijeh Najafi, and Susanne F Yelin. ``Markov chain monte carlo enhanced variational quantum algorithms''. Quantum Science and Technology 8, 015019 (2022).

[27] Youle Wang, Guangxi Li, and Xin Wang. ``Variational quantum gibbs state preparation with a truncated taylor series''. Physical Review Applied 16, 054035 (2021).

[28] Sanjeev Arora, Elad Hazan, and Satyen Kale. ``The multiplicative weights update method: A meta-algorithm and applications''. Theory of Computing 8, 121–164 (2012).

[29] Iordanis Kerenidis and Anupam Prakash. ``A quantum interior point method for lps and sdps''. ACM Transactions on Quantum Computing 1 (2020).

[30] Brandon Augustino, Giacomo Nannicini, Tamás Terlaky, and Luis F. Zuluaga. ``Quantum interior point methods for semidefinite optimization'' (2022). arXiv:2112.06025.

[31] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles. ``Variational quantum algorithms''. Nature Reviews Physics 3, 625–644 (2021).

[32] Kishor Bharti, Tobias Haug, Vlatko Vedral, and Leong-Chuan Kwek. ``Noisy intermediate-scale quantum algorithm for semidefinite programming''. Phys. Rev. A 105, 052445 (2022).

[33] Lennart Bittel and Martin Kliesch. ``Training variational quantum algorithms is np-hard''. Phys. Rev. Lett. 127, 120502 (2021).

[34] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. ``Barren plateaus in quantum neural network training landscapes''. Nature Communications 9, 4812 (2018).

[35] Carlos Ortiz Marrero, Mária Kieferová, and Nathan Wiebe. ``Entanglement-induced barren plateaus''. PRX Quantum 2, 040316 (2021).

[36] Taylor L. Patti, Khadijeh Najafi, Xun Gao, and Susanne F. Yelin. ``Entanglement devised barren plateau mitigation''. Phys. Rev. Res. 3, 033090 (2021).

[37] Arthur Pesah, M. Cerezo, Samson Wang, Tyler Volkoff, Andrew T. Sornborger, and Patrick J. Coles. ``Absence of barren plateaus in quantum convolutional neural networks''. Phys. Rev. X 11, 041011 (2021).

[38] Dorit Aharonov, Vaughan Jones, and Zeph Landau. ``A polynomial quantum algorithm for approximating the jones polynomial''. Algorithmica 55, 395–421 (2009).

[39] Clayton W. Commander. ``Maximum cut problem, max-cutmaximum cut problem, max-cut''. Pages 1991–1999. Springer US. Boston, MA (2009).

[40] Steven J. Benson, Yinyu Yeb, and Xiong Zhang. ``Mixed linear and semidefinite programming for combinatorial and quadratic optimization''. Optimization Methods and Software 11, 515–544 (1999).

[41] Changhui Choi and Yinyu Ye. ``Solving sparse semidefinite programs using the dual scaling algorithm with an iterative solver''. Manuscript, Department of Management Sciences, University of Iowa, Iowa City, IA 52242 (2000). url: web.stanford.edu/​ yyye/​yyye/​cgsdp1.pdf.

[42] Angelika Wiegele. ``Biq mac library – a collection of max-cut and quadratic 0-1 programming instances of medium size''. Alpen-Adria-Universität Klagenfurt (2007). url: biqmac.aau.at/​biqmaclib.pdf.

[43] Stefan H. Schmieta. ``The dimacs library of mixed semidefinite-quadratic-linear programs''. 7th DIMACS Implementation Challenge (2007). url: http:/​/​archive.dimacs.rutgers.edu.

[44] Yoshiki Matsuda. ``Benchmarking the max-cut problem on the simulated bifurcation machine''. Medium (2019). url: medium.com/​toshiba-sbm/​benchmarking-the-max-cut-problem-on-the-simulated-bifurcation-machine-e26e1127c0b0.

[45] R. M. Karp. ``Reducibility among combinatorial problems''. Springer US. Boston, MA (1972).

[46] Dimitri P Bertsekas. ``Constrained optimization and lagrange multiplier methods''. Academic press. (1982).

[47] G Mauro D'Ariano, Matteo GA Paris, and Massimiliano F Sacchi. ``Quantum tomography''. Advances in imaging and electron physics 128, 206–309 (2003).

[48] Alessandro Bisio, Giulio Chiribella, Giacomo Mauro D'Ariano, Stefano Facchini, and Paolo Perinotti. ``Optimal quantum tomography''. IEEE Journal of Selected Topics in Quantum Electronics 15, 1646–1660 (2009).

[49] Max S. Kaznady and Daniel F. V. James. ``Numerical strategies for quantum tomography: Alternatives to full optimization''. Phys. Rev. A 79, 022109 (2009).

[50] Javier Peña. ``Convergence of first-order methods via the convex conjugate''. Operations Research Letters 45, 561–564 (2017).

[51] Alan Frieze and Mark Jerrum. ``Improved approximation algorithms for maxk-cut and max bisection''. Algorithmica 18, 67–81 (1997).

[52] Clark David Thompson. ``A complexity theory for vlsi''. PhD thesis. Carnegie Mellon University. (1980). url: dl.acm.org/​doi/​10.5555/​909758.

[53] Chu Min Li and Felip Manya. ``Maxsat, hard and soft constraints''. In Handbook of satisfiability. Pages 903–927. IOS Press (2021).

[54] Nicholas J Higham. ``Computing the nearest correlation matrix—a problem from finance''. IMA journal of Numerical Analysis 22, 329–343 (2002).

[55] Tadayoshi Fushiki. ``Estimation of positive semidefinite correlation matrices by using convex quadratic semidefinite programming''. Neural Computation 21, 2028–2048 (2009).

[56] Todd MJ. ``A study of search directions in primal-dual interior-point methods for semidefinite programming''. Optimization methods and software 11, 1–46 (1999).

[57] Roger Fletcher. ``Penalty functions''. Mathematical Programming The State of the Art: Bonn 1982Pages 87–114 (1983).

[58] Robert M Freund. ``Penalty and barrier methods for constrained optimization''. Lecture Notes, Massachusetts Institute of Technology (2004). url: ocw.mit.edu/​courses/​15-084j-nonlinear-programming-spring-2004.

[59] Eric Ricardo Anschuetz. ``Critical points in quantum generative models''. In International Conference on Learning Representations. (2022). url: openreview.net/​forum?id=2f1z55GVQN.

[60] Amir Beck. ``First-order methods in optimization''. SIAM. (2017).

[61] Sanjeev Arora and Satyen Kale. ``A combinatorial, primal-dual approach to semidefinite programs''. J. ACM 63 (2016).

[62] Taylor L. Patti, Jean Kossaifi, Susanne F. Yelin, and Anima Anandkumar. ``Tensorly-quantum: Quantum machine learning with tensor methods'' (2021). arXiv:2112.10239.

[63] Jean Kossaifi, Yannis Panagakis, Anima Anandkumar, and Maja Pantic. ``Tensorly: Tensor learning in python''. Journal of Machine Learning Research 20, 1–6 (2019). url: http:/​/​jmlr.org/​papers/​v20/​18-277.html.

[64] cuQuantum Team. ``Nvidia/​cuquantum: cuquantum v22.11'' (2022).

[65] Diederik P. Kingma and Jimmy Ba. ``Adam: A method for stochastic optimization'' (2017). arXiv:1412.6980.

[66] Brahim Chaourar. ``A linear time algorithm for a variant of the max cut problem in series parallel graphs''. Advances in Operations Research (2017).

[67] Yury Makarychev. ``A short proof of kuratowski's graph planarity criterion''. Journal of Graph Theory 25, 129–131 (1997).

[68] Béla Bollobás. ``The evolution of random graphs—the giant component''. Page 130–159. Cambridge Studies in Advanced Mathematics. Cambridge University Press. (2001). 2 edition.

[69] Sanjeev Arora, David Karger, and Marek Karpinski. ``Polynomial time approximation schemes for dense instances of np-hard problems''. Journal of computer and system sciences 58, 193–210 (1999).

[70] Rick Durrett. ``Erdös–rényi random graphs''. Page 27–69. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press. (2006).

[71] Gary Chartrand and Ping Zhang. ``Chromatic graph theory''. Taylor and Francis. (2008).

[72] John van de Wetering. ``Zx-calculus for the working quantum computer scientist'' (2020). arXiv:2012.13966.

[73] Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons, and Seyon Sivarajah. ``Phase gadget synthesis for shallow circuits''. Electronic Proceedings in Theoretical Computer Science 318, 213–228 (2020).

[74] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu. ``Theory of trotter error with commutator scaling''. Phys. Rev. X 11, 011020 (2021).

[75] Joseph W Britton, Brian C Sawyer, Adam C Keith, C-C Joseph Wang, James K Freericks, Hermann Uys, Michael J Biercuk, and John J Bollinger. ``Engineered two-dimensional ising interactions in a trapped-ion quantum simulator with hundreds of spins''. Nature 484, 489–492 (2012).

[76] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, Harry Levine, Ahmed Omran, Hannes Pichler, Soonwon Choi, Alexander S Zibrov, Manuel Endres, Markus Greiner, et al. ``Probing many-body dynamics on a 51-atom quantum simulator''. Nature 551, 579–584 (2017).

[77] Gheorghe-Sorin Paraoanu. ``Recent progress in quantum simulation using superconducting circuits''. Journal of Low Temperature Physics 175, 633–654 (2014).

[78] Katsuki Fujisawa, Hitoshi Sato, Satoshi Matsuoka, Toshio Endo, Makoto Yamashita, and Maho Nakata. ``High-performance general solver for extremely large-scale semidefinite programming problems''. In SC '12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. Pages 1–11. (2012).

[79] Adrian S. Lewis and Michael L. Overton. ``Eigenvalue optimization''. Acta Numerica 5, 149–190 (1996).

[80] Xiaosi Xu, Jinzhao Sun, Suguru Endo, Ying Li, Simon C. Benjamin, and Xiao Yuan. ``Variational algorithms for linear algebra''. Science Bulletin 66, 2181–2188 (2021).

Cited by

[1] Kaito Wada, Rudy Raymond, Yuki Sato, and Hiroshi C Watanabe, "Sequential optimal selections of single-qubit gates in parameterized quantum circuits", Quantum Science and Technology 9 3, 035030 (2024).

[2] Ruyu Yang, Wencheng Zhao, and Tingting Chen, "Scalable algorithms for calculating power functions of random quantum states in the noisy intermediate-scale quantum era", Physical Review A 109 6, 062421 (2024).

[3] Yilun Yang, Arthur Christianen, Mari Carmen Bañuls, Dominik S. Wild, and J. Ignacio Cirac, "Phase-Sensitive Quantum Measurement without Controlled Operations", Physical Review Letters 132 22, 220601 (2024).

[4] Oscar Watts, Yuta Kikuchi, and Luuk Coopmans, "Quantum Semidefinite Programming with Thermal Pure Quantum States", arXiv:2310.07774, (2023).

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

The above citations are from Crossref's cited-by service (last updated successfully 2024-06-22 03:45:46) and SAO/NASA ADS (last updated successfully 2024-06-22 03:45:47). The list may be incomplete as not all publishers provide suitable and complete citation data.