{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T22:04:31Z","timestamp":1776809071760,"version":"3.51.2"},"reference-count":80,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T00:00:00Z","timestamp":1689120000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"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<\/mml:mi>+<\/mml:mo><\/mml:mrow>1<\/mml:mn><\/mml:math> qubits, a constant number of circuit preparations, and poly<\/mml:mtext>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:math> expectation values in order to approximately solve semidefinite programs with up to N<\/mml:mi>=<\/mml:mo>2<\/mml:mn>n<\/mml:mi><\/mml:msup><\/mml:math> variables and M<\/mml:mi>&#x223C;<\/mml:mo>O<\/mml:mi>(<\/mml:mo>N<\/mml:mi>)<\/mml:mo><\/mml:math> 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.<\/jats:p>","DOI":"10.22331\/q-2023-07-12-1057","type":"journal-article","created":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T14:13:40Z","timestamp":1689171220000},"page":"1057","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":10,"title":["Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints"],"prefix":"10.22331","volume":"7","author":[{"given":"Taylor L.","family":"Patti","sequence":"first","affiliation":[{"name":"Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA"},{"name":"NVIDIA, Santa Clara, California 95051, USA"}]},{"given":"Jean","family":"Kossaifi","sequence":"additional","affiliation":[{"name":"NVIDIA, Santa Clara, California 95051, USA"}]},{"given":"Anima","family":"Anandkumar","sequence":"additional","affiliation":[{"name":"Department of Computing + Mathematical Sciences (CMS), California Institute of Technology (Caltech), Pasadena, CA 91125 USA"},{"name":"NVIDIA, Santa Clara, California 95051, USA"}]},{"given":"Susanne F.","family":"Yelin","sequence":"additional","affiliation":[{"name":"Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA"}]}],"member":"9598","published-online":{"date-parts":[[2023,7,12]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Stephen P. Boyd and Lieven Vandenberghe. ``Convex optimization''. Cambridge Press. (2004).","DOI":"10.1017\/CBO9780511804441"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Michel X. Goemans. ``Semidefinite programming in combinatorial optimization''. Mathematical Programming 79, 143\u2013161 (1997).","DOI":"10.1007\/BF02614315"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Lieven Vandenberghe and Stephen Boyd. ``Applications of semidefinite programming''. Applied Numerical Mathematics 29, 283\u2013299 (1999).","DOI":"10.1016\/S0168-9274(98)00098-1"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1186\/s13673-020-00226-w"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Christoph Helmberg. ``Semidefinite programming for combinatorial optimization''. Konrad-Zuse-Zentrum fur Informationstechnik Berlin. (2000).","DOI":"10.1007\/BF02614315"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Michel X. Goemans and David P. Williamson. ``Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming''. J. ACM 42, 1115\u20131145 (1995).","DOI":"10.1145\/227683.227684"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Florian A. Potra and Stephen J. Wright. ``Interior-point methods''. Journal of Computational and Applied Mathematics 124, 281\u2013302 (2000).","DOI":"10.1016\/S0377-0427(00)00433-7"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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\u2013918. IEEE (2020).","DOI":"10.1109\/FOCS46700.2020.00089"},{"key":"8","doi-asserted-by":"publisher","unstructured":"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\u2013244. IEEE (2022).","DOI":"10.1109\/FOCS54457.2022.00029"},{"key":"9","doi-asserted-by":"publisher","unstructured":"David P. Williamson and David B. Shmoys. ``The design of approximation algorithms''. Cambridge University Press. (2011).","DOI":"10.1017\/CBO9780511921735"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1088\/2058-9565\/aab822"},{"key":"11","unstructured":"Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. ``Quantum computation by adiabatic evolution'' (2000). arXiv:quant-ph\/0001106."},{"key":"12","doi-asserted-by":"publisher","unstructured":"Tameem Albash and Daniel A. Lidar. ``Adiabatic quantum computation''. Rev. Mod. Phys. 90, 015002 (2018).","DOI":"10.1103\/RevModPhys.90.015002"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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\u20131215 (2022).","DOI":"10.1126\/science.abo6587"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Tadashi Kadowaki and Hidetoshi Nishimori. ``Quantum annealing in the transverse ising model''. Phys. Rev. E 58, 5355\u20135363 (1998).","DOI":"10.1103\/PhysRevE.58.5355"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Elizabeth Gibney. ``D-wave upgrade: How scientists are using the world's most controversial quantum computer''. Nature 541 (2017).","DOI":"10.1038\/541447b"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm''. arXiv (2014). arXiv:1411.4028.","DOI":"10.48550\/arXiv.1411.4028"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Juan M Arrazola, Ville Bergholm, Kamil Br\u00e1dler, 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\u201360 (2021).","DOI":"10.1038\/s41586-021-03202-1"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Fernando G. S. L. Brand\u00e3o, 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\u201327:14 (2019).","DOI":"10.4230\/LIPIcs.ICALP.2019.27"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Joran Van Apeldoorn and Andr\u00e1s Gily\u00e9n. ``Improvements in quantum sdp-solving with applications''. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (2019).","DOI":"10.4230\/LIPICS.ICALP.2019.99"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Joran van Apeldoorn, Andr\u00e0s Gily\u00e8n, Sander Gribling, and Ronald de Wolf. ``Quantum sdp-solvers: Better upper and lower bounds''. Quantum 4, 230 (2020).","DOI":"10.22331\/q-2020-02-14-230"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Fernando G.S.L. Brand\u00e3o 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\u2013426. (2017).","DOI":"10.1109\/FOCS.2017.45"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Fernando G.S L. Brand\u00e3o, Richard Kueng, and Daniel Stilck Fran\u00e7a. ``Faster quantum and classical SDP approximations for quadratic binary optimization''. Quantum 6, 625 (2022).","DOI":"10.22331\/q-2022-01-20-625"},{"key":"23","unstructured":"Dhrumil Patel, Patrick J. Coles, and Mark M. Wilde. ``Variational quantum algorithms for semidefinite programming'' (2021). arXiv:2112.08859."},{"key":"24","unstructured":"Anirban N. Chowdhury, Guang Hao Low, and Nathan Wiebe. ``A variational quantum algorithm for preparing quantum gibbs states'' (2020). arXiv:2002.00055."},{"key":"25","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1088\/2058-9565\/aca821"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Youle Wang, Guangxi Li, and Xin Wang. ``Variational quantum gibbs state preparation with a truncated taylor series''. Physical Review Applied 16, 054035 (2021).","DOI":"10.1103\/PhysRevApplied.16.054035"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Sanjeev Arora, Elad Hazan, and Satyen Kale. ``The multiplicative weights update method: A meta-algorithm and applications''. Theory of Computing 8, 121\u2013164 (2012).","DOI":"10.4086\/toc.2012.v008a006"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis and Anupam Prakash. ``A quantum interior point method for lps and sdps''. ACM Transactions on Quantum Computing 1 (2020).","DOI":"10.1145\/3406306"},{"key":"29","unstructured":"Brandon Augustino, Giacomo Nannicini, Tam\u00e1s Terlaky, and Luis F. Zuluaga. ``Quantum interior point methods for semidefinite optimization'' (2022). arXiv:2112.06025."},{"key":"30","doi-asserted-by":"publisher","unstructured":"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\u2013644 (2021).","DOI":"10.1038\/s42254-021-00348-9"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Kishor Bharti, Tobias Haug, Vlatko Vedral, and Leong-Chuan Kwek. ``Noisy intermediate-scale quantum algorithm for semidefinite programming''. Phys. Rev. A 105, 052445 (2022).","DOI":"10.1103\/PhysRevA.105.052445"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Lennart Bittel and Martin Kliesch. ``Training variational quantum algorithms is np-hard''. Phys. Rev. Lett. 127, 120502 (2021).","DOI":"10.1103\/PhysRevLett.127.120502"},{"key":"33","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1038\/s41467-018-07090-4"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Carlos Ortiz Marrero, M\u00e1ria Kieferov\u00e1, and Nathan Wiebe. ``Entanglement-induced barren plateaus''. PRX Quantum 2, 040316 (2021).","DOI":"10.1103\/PRXQuantum.2.040316"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Taylor L. Patti, Khadijeh Najafi, Xun Gao, and Susanne F. Yelin. ``Entanglement devised barren plateau mitigation''. Phys. Rev. Res. 3, 033090 (2021).","DOI":"10.1103\/PhysRevResearch.3.033090"},{"key":"36","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevX.11.041011"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Dorit Aharonov, Vaughan Jones, and Zeph Landau. ``A polynomial quantum algorithm for approximating the jones polynomial''. Algorithmica 55, 395\u2013421 (2009).","DOI":"10.1007\/s00453-008-9168-0"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Clayton W. Commander. ``Maximum cut problem, max-cutmaximum cut problem, max-cut''. Pages 1991\u20131999. Springer US. Boston, MA (2009).","DOI":"10.1007\/978-0-387-74759-0_358"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Steven J. Benson, Yinyu Yeb, and Xiong Zhang. ``Mixed linear and semidefinite programming for combinatorial and quadratic optimization''. Optimization Methods and Software 11, 515\u2013544 (1999).","DOI":"10.1080\/10556789908805761"},{"key":"40","unstructured":"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."},{"key":"41","unstructured":"Angelika Wiegele. ``Biq mac library \u2013 a collection of max-cut and quadratic 0-1 programming instances of medium size''. Alpen-Adria-Universit\u00e4t Klagenfurt (2007). url: biqmac.aau.at\/biqmaclib.pdf."},{"key":"42","unstructured":"Stefan H. Schmieta. ``The dimacs library of mixed semidefinite-quadratic-linear programs''. 7th DIMACS Implementation Challenge (2007). url: http:\/\/archive.dimacs.rutgers.edu."},{"key":"43","unstructured":"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."},{"key":"44","doi-asserted-by":"crossref","unstructured":"R. M. Karp. ``Reducibility among combinatorial problems''. Springer US. Boston, MA (1972).","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Dimitri P Bertsekas. ``Constrained optimization and lagrange multiplier methods''. Academic press. (1982).","DOI":"10.1016\/C2013-0-10366-2"},{"key":"46","doi-asserted-by":"publisher","unstructured":"G Mauro D'Ariano, Matteo GA Paris, and Massimiliano F Sacchi. ``Quantum tomography''. Advances in imaging and electron physics 128, 206\u2013309 (2003).","DOI":"10.48550\/arXiv.quant-ph\/0302028"},{"key":"47","doi-asserted-by":"publisher","unstructured":"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\u20131660 (2009).","DOI":"10.1109\/JSTQE.2009.2029243"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Max S. Kaznady and Daniel F. V. James. ``Numerical strategies for quantum tomography: Alternatives to full optimization''. Phys. Rev. A 79, 022109 (2009).","DOI":"10.1103\/PhysRevA.79.022109"},{"key":"49","doi-asserted-by":"publisher","unstructured":"Javier Pe\u00f1a. ``Convergence of first-order methods via the convex conjugate''. Operations Research Letters 45, 561\u2013564 (2017).","DOI":"10.1016\/j.orl.2017.08.013"},{"key":"50","doi-asserted-by":"publisher","unstructured":"Alan Frieze and Mark Jerrum. ``Improved approximation algorithms for maxk-cut and max bisection''. Algorithmica 18, 67\u201381 (1997).","DOI":"10.1007\/BF02523688"},{"key":"51","unstructured":"Clark David Thompson. ``A complexity theory for vlsi''. PhD thesis. Carnegie Mellon University. (1980). url: dl.acm.org\/doi\/10.5555\/909758."},{"key":"52","doi-asserted-by":"publisher","unstructured":"Chu Min Li and Felip Manya. ``Maxsat, hard and soft constraints''. In Handbook of satisfiability. Pages 903\u2013927. IOS Press (2021).","DOI":"10.3233\/978-1-58603-929-5-613"},{"key":"53","doi-asserted-by":"publisher","unstructured":"Nicholas J Higham. ``Computing the nearest correlation matrix\u2014a problem from finance''. IMA journal of Numerical Analysis 22, 329\u2013343 (2002).","DOI":"10.1093\/imanum\/22.3.329"},{"key":"54","doi-asserted-by":"publisher","unstructured":"Tadayoshi Fushiki. ``Estimation of positive semidefinite correlation matrices by using convex quadratic semidefinite programming''. Neural Computation 21, 2028\u20132048 (2009).","DOI":"10.1162\/neco.2009.04-08-765"},{"key":"55","doi-asserted-by":"publisher","unstructured":"Todd MJ. ``A study of search directions in primal-dual interior-point methods for semidefinite programming''. Optimization methods and software 11, 1\u201346 (1999).","DOI":"10.1080\/10556789908805745"},{"key":"56","doi-asserted-by":"publisher","unstructured":"Roger Fletcher. ``Penalty functions''. Mathematical Programming The State of the Art: Bonn 1982Pages 87\u2013114 (1983).","DOI":"10.1007\/978-3-642-68874-4_5"},{"key":"57","unstructured":"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."},{"key":"58","unstructured":"Eric Ricardo Anschuetz. ``Critical points in quantum generative models''. In International Conference on Learning Representations. (2022). url: openreview.net\/forum?id=2f1z55GVQN."},{"key":"59","doi-asserted-by":"publisher","unstructured":"Amir Beck. ``First-order methods in optimization''. SIAM. (2017).","DOI":"10.1137\/1.9781611974997"},{"key":"60","doi-asserted-by":"publisher","unstructured":"Sanjeev Arora and Satyen Kale. ``A combinatorial, primal-dual approach to semidefinite programs''. J. ACM 63 (2016).","DOI":"10.1145\/2837020"},{"key":"61","unstructured":"Taylor L. Patti, Jean Kossaifi, Susanne F. Yelin, and Anima Anandkumar. ``Tensorly-quantum: Quantum machine learning with tensor methods'' (2021). arXiv:2112.10239."},{"key":"62","unstructured":"Jean Kossaifi, Yannis Panagakis, Anima Anandkumar, and Maja Pantic. ``Tensorly: Tensor learning in python''. Journal of Machine Learning Research 20, 1\u20136 (2019). url: http:\/\/jmlr.org\/papers\/v20\/18-277.html."},{"key":"63","unstructured":"cuQuantum Team. ``Nvidia\/cuquantum: cuquantum v22.11'' (2022)."},{"key":"64","unstructured":"Diederik P. Kingma and Jimmy Ba. ``Adam: A method for stochastic optimization'' (2017). arXiv:1412.6980."},{"key":"65","doi-asserted-by":"publisher","unstructured":"Brahim Chaourar. ``A linear time algorithm for a variant of the max cut problem in series parallel graphs''. Advances in Operations Research (2017).","DOI":"10.1155\/2017\/1267108"},{"key":"66","doi-asserted-by":"publisher","unstructured":"Yury Makarychev. ``A short proof of kuratowski's graph planarity criterion''. Journal of Graph Theory 25, 129\u2013131 (1997).","DOI":"10.1002\/(SICI)1097-0118(199706)25:2<129::AID-JGT4>3.0.CO;2-O"},{"key":"67","doi-asserted-by":"publisher","unstructured":"B\u00e9la Bollob\u00e1s. ``The evolution of random graphs\u2014the giant component''. Page 130\u2013159. Cambridge Studies in Advanced Mathematics. Cambridge University Press. (2001). 2 edition.","DOI":"10.1017\/CBO9780511814068.008"},{"key":"68","doi-asserted-by":"publisher","unstructured":"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\u2013210 (1999).","DOI":"10.1006\/jcss.1998.1605"},{"key":"69","doi-asserted-by":"publisher","unstructured":"Rick Durrett. ``Erd\u00f6s\u2013r\u00e9nyi random graphs''. Page 27\u201369. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press. (2006).","DOI":"10.1017\/CBO9780511546594.003"},{"key":"70","doi-asserted-by":"publisher","unstructured":"Gary Chartrand and Ping Zhang. ``Chromatic graph theory''. Taylor and Francis. (2008).","DOI":"10.1201\/9781584888017"},{"key":"71","unstructured":"John van de Wetering. ``Zx-calculus for the working quantum computer scientist'' (2020). arXiv:2012.13966."},{"key":"72","doi-asserted-by":"publisher","unstructured":"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\u2013228 (2020).","DOI":"10.4204\/eptcs.318.13"},{"key":"73","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevX.11.011020"},{"key":"74","doi-asserted-by":"publisher","unstructured":"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\u2013492 (2012).","DOI":"10.1038\/nature10981"},{"key":"75","doi-asserted-by":"publisher","unstructured":"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\u2013584 (2017).","DOI":"10.1038\/nature24622"},{"key":"76","doi-asserted-by":"publisher","unstructured":"Gheorghe-Sorin Paraoanu. ``Recent progress in quantum simulation using superconducting circuits''. Journal of Low Temperature Physics 175, 633\u2013654 (2014).","DOI":"10.1007\/s10909-014-1175-8"},{"key":"77","doi-asserted-by":"publisher","unstructured":"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\u201311. (2012).","DOI":"10.1109\/SC.2012.67"},{"key":"78","doi-asserted-by":"publisher","unstructured":"Adrian S. Lewis and Michael L. Overton. ``Eigenvalue optimization''. Acta Numerica 5, 149\u2013190 (1996).","DOI":"10.1017\/S0962492900002646"},{"key":"79","doi-asserted-by":"publisher","unstructured":"Xiaosi Xu, Jinzhao Sun, Suguru Endo, Ying Li, Simon C. Benjamin, and Xiao Yuan. ``Variational algorithms for linear algebra''. Science Bulletin 66, 2181\u20132188 (2021).","DOI":"10.1016\/j.scib.2021.06.023"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-07-12-1057\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T14:13:55Z","timestamp":1689171235000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-07-12-1057\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,12]]},"references-count":80,"URL":"https:\/\/doi.org\/10.22331\/q-2023-07-12-1057","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,12]]},"article-number":"1057"}}