Warm-starting quantum optimization

Daniel J. Egger; Jakub Mareček; Stefan Woerner

doi:10.22331/q-2021-06-17-479

Warm-starting quantum optimization

Daniel J. Egger¹, Jakub Mareček², and Stefan Woerner¹

¹IBM Quantum, IBM Research – Zurich, Säumerstrasse 4, 8803 Rüschlikon, Switzerland
²Czech Technical University, Karlovo nam. 13, Prague 2, the Czech Republic

Published:	2021-06-17, volume 5, page 479
Eprint:	arXiv:2009.10095v4
Doi:	https://doi.org/10.22331/q-2021-06-17-479
Citation:	Quantum 5, 479 (2021).

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

Abstract

There is an increasing interest in quantum algorithms for problems of integer programming and combinatorial optimization. Classical solvers for such problems employ relaxations, which replace binary variables with continuous ones, for instance in the form of higher-dimensional matrix-valued problems (semidefinite programming). Under the Unique Games Conjecture, these relaxations often provide the best performance ratios available classically in polynomial time. Here, we discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem and how to analyze properties of the associated quantum algorithms. In particular, this allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. We illustrate this in the context of portfolio optimization, where our results indicate that warm-starting the Quantum Approximate Optimization Algorithm (QAOA) is particularly beneficial at low depth. Likewise, Recursive QAOA for MAXCUT problems shows a systematic increase in the size of the obtained cut for fully connected graphs with random weights, when Goemans-Williamson randomized rounding is utilized in a warm start. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.

Featured image: The quantum circuit of warm-start QAOA.

Popular summary

Many optimization problems in binary decision variables are hard to solve. In this work, we demonstrate how to leverage decades of research in classical optimization algorithms to warm-start quantum optimization algorithms. This allows the quantum algorithm to inherit the performance guarantees from the classical algorithm used in the warm-start.

► BibTeX data

@article{Egger2021warmstartingquantum,
  doi = {10.22331/q-2021-06-17-479},
  url = {https://doi.org/10.22331/q-2021-06-17-479},
  title = {Warm-starting quantum optimization},
  author = {Egger, Daniel J. and Mare{\v{c}}ek, Jakub and Woerner, Stefan},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {479},
  month = jun,
  year = {2021}
}

► References

[1] Nikolaj Moll, Panagiotis Barkoutsos, Lev S. Bishop, Jerry M. Chow, Andrew Cross, Daniel J. Egger, Stefan Filipp, Andreas Fuhrer, Jay M. Gambetta, Marc Ganzhorn, and et al. Quantum optimization using variational algorithms on near-term quantum devices. Quantum Sci. Technol., 3 (3): 030503, 2018. 10.1088/2058-9565/aab822.
https://doi.org/10.1088/2058-9565/aab822

[2] Abhinav Kandala, Kristan Temme, Antonio D. Corcoles, Antonio Mezzacapo, Jerry M. Chow, and Jay M. Gambetta. Error mitigation extends the computational reach of a noisy quantum processor. Nature, 567: 491–495, 2018. 10.1038/s41586-019-1040-7.
https://doi.org/10.1038/s41586-019-1040-7

[3] Marc Ganzhorn, Daniel J. Egger, Panagiotis Kl. Barkoutsos, Pauline Ollitrault, Gian Salis, Nikolaj Moll, Andreas Fuhrer, Peter Mueller, Stefan Woerner, Ivano Tavernelli, and Stefan Filipp. Gate-efficient simulation of molecular eigenstates on a quantum computer. Phys. Rev. Applied, 11: 044092, Apr 2019. 10.1103/PhysRevApplied.11.044092.
https://doi.org/10.1103/PhysRevApplied.11.044092

[4] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549 (7671): 195–202, 2017. 10.1038/nature23474.
https://doi.org/10.1038/nature23474

[5] Vojtech Havlicek, Antonio D. Corcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta. Supervised learning with quantum-enhanced feature spaces. Nature, 567: 209 – 212, 2019. 10.1038/s41586-019-0980-2.
https://doi.org/10.1038/s41586-019-0980-2

[6] Daniel J. Egger, Claudio Gambella, Jakub Mareček, Scott McFaddin, Martin Mevissen, Rudy Raymond, Aandrea Simonetto, Sefan Woerner, and Elena Yndurain. Quantum computing for finance: State-of-the-art and future prospects. IEEE Trans. on Quantum Eng., 1: 1–24, 2020. 10.1109/TQE.2020.3030314.
https://doi.org/10.1109/TQE.2020.3030314

[7] Stefan Woerner and Daniel J. Egger. Quantum risk analysis. npj Quantum Inf., 5: 15, 2019. 10.1038/s41534-019-0130-6.
https://doi.org/10.1038/s41534-019-0130-6

[8] Patrick Rebentrost, Brajesh Gupt, and Thomas R. Bromley. Quantum computational finance: Monte Carlo pricing of financial derivatives. Phys. Rev. A, 98: 022321, Aug 2018. 10.1103/PhysRevA.98.022321.
https://doi.org/10.1103/PhysRevA.98.022321

[9] Nikitas Stamatopoulos, Daniel J. Egger, Yue Sun, Christa Zoufal, Raban Iten, Ning Shen, and Stefan Woerner. Option pricing using quantum computers. Quantum, 4: 291, 2020. 10.22331/q-2020-07-06-291.
https://doi.org/10.22331/q-2020-07-06-291

[10] Ana Martin, Bruno Candelas, Ángel Rodríguez-Rozas, José D. Martín-Guerrero, Xi Chen, Lucas Lamata, Román Orús, Enrique Solano, and Mikel Sanz. Toward pricing financial derivatives with an ibm quantum computer. Phys. Rev. Research, 3: 013167, Feb 2021. 10.1103/PhysRevResearch.3.013167.
https://doi.org/10.1103/PhysRevResearch.3.013167

[11] Roman Orus, Samuel Mugel, and Enrique Lizaso. Quantum computing for finance: Overview and prospects. Rev. Phys., 4: 100028, 2019. 10.1016/j.revip.2019.100028.
https://doi.org/10.1016/j.revip.2019.100028

[12] Daniel J. Egger, Ricardo G. Gutierrez, Jordi Cahue Mestre, and Stefan Woerner. Credit risk analysis using quantum computers. IEEE Trans. Comput., 1: 1–1, Nov 2020. 10.1109/TC.2020.3038063.
https://doi.org/10.1109/TC.2020.3038063

[13] Almudena Carrera Vazquez and Stefan Woerner. Efficient state preparation for quantum amplitude estimation. Phys. Rev. Applied, 15: 034027, Mar 2021. 10.1103/PhysRevApplied.15.034027.
https://doi.org/10.1103/PhysRevApplied.15.034027

[14] Lee Braine, Daniel J. Egger, Jennifer Glick, and Stefan Woerner. Quantum algorithms for mixed binary optimization applied to transaction settlement. IEEE Trans. on Quantum Eng., 2: 1–8, 2021. 10.1109/TQE.2021.3063635.
https://doi.org/10.1109/TQE.2021.3063635

[15] Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli, and Stefan Woerner. Improving variational quantum optimization using cvar. Quantum, 4: 256, Apr 2020. 10.22331/q-2020-04-20-256.
https://doi.org/10.22331/q-2020-04-20-256

[16] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm, 2014a. URL https://arxiv.org/abs/1411.4028.
arXiv:1411.4028

[17] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem, 2014b. URL https://arxiv.org/abs/1412.6062.
arXiv:1412.6062

[18] Zhi-Cheng Yang, Armin Rahmani, Alireza Shabani, Hartmut Neven, and Claudio Chamon. Optimizing variational quantum algorithms using pontryagin's minimum principle. Phys. Rev. X, 7: 021027, May 2017. 10.1103/PhysRevX.7.021027.
https://doi.org/10.1103/PhysRevX.7.021027

[19] Mark W. Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, Richard Harris, Andrew J. Berkley, Jan Johansson, Paul Bunyk, and et al. Quantum annealing with manufactured spins. Nature, 473 (7346): 194–198, May 2011. 10.1038/nature10012.
https://doi.org/10.1038/nature10012

[20] Glen Bigan Mbeng, Rosario Fazio, and Giuseppe Santoro. Quantum annealing: a journey through digitalization, control, and hybrid quantum variational schemes, 2019. URL https://arxiv.org/abs/1906.08948.
arXiv:1906.08948

[21] Michael Juenger, Elisabeth Lobe, Petra Mutzel, Gerhard Reinelt, Franz Rendl, Giovanni Rinaldi, and Tobias Stollenwerk. Performance of a quantum annealer for Ising ground state computations on chimera graphs, 2019. URL https://arxiv.org/abs/1904.11965.
arXiv:1904.11965

[22] Rami Barends, Alireza Shabani, Lucas Lamata, Julian Kelly, Antonio Mezzacapo, Urtzi Las Heras, Ryan Babbush, Austin G. Fowler, Brooks Campbell, Yu Chen, and et al. Digitized adiabatic quantum computing with a superconducting circuit. Nature, 534 (7606): 222–226, Jun 2016. 10.1038/nature17658.
https://doi.org/10.1038/nature17658

[23] Madita Willsch, Dennis Willsch, Fengping Jin, Hans De Raedt, and Kristel Michielsen. Benchmarking the quantum approximate optimization algorithm. Quantum Inf. Process., 19 (7): 197, Jun 2020. 10.1007/s11128-020-02692-8.
https://doi.org/10.1007/s11128-020-02692-8

[24] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to variational quantum optimization from symmetry protection. Phys. Rev. Lett., 125: 260505, Dec 2020a. 10.1103/PhysRevLett.125.260505.
https://doi.org/10.1103/PhysRevLett.125.260505

[25] Gavin E. Crooks. Performance of the quantum approximate optimization algorithm on the maximum cut problem, 2018. URL https://arxiv.org/abs/1811.08419.
arXiv:1811.08419

[26] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Hartmut Neven. Quantum algorithms for fixed qubit architectures, 2017. URL https://arxiv.org/abs/1703.06199.
arXiv:1703.06199

[27] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor Rieffel, Davide Venturelli, and Rupak Biswas. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms, 12 (2): 34, Feb 2019. 10.3390/a12020034.
https://doi.org/10.3390/a12020034

[28] Linghua Zhu, Ho Lun Tang, George S. Barron, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou. An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer, 2020. URL https://arxiv.org/abs/2005.10258.
arXiv:2005.10258

[29] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy, and Eleanor G. Rieffel. XY mixers: Analytical and numerical results for the quantum alternating operator ansatz. Phys. Rev. A, 101: 012320, Jan 2020. 10.1103/PhysRevA.101.012320.
https://doi.org/10.1103/PhysRevA.101.012320

[30] Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev, and Prasanna Balaprakash. Learning to optimize variational quantum circuits to solve combinatorial problems. Proceedings of the AAAI Conference on Artificial Intelligence, 34 (03): 2367–2375, Apr 2020. 10.1609/aaai.v34i03.5616.
https://doi.org/10.1609/aaai.v34i03.5616

[31] Matteo M. Wauters, Emanuele Panizon, Glen B. Mbeng, and Giuseppe E. Santoro. Reinforcement-learning-assisted quantum optimization. Phys. Rev. Research, 2: 033446, Sep 2020. 10.1103/PhysRevResearch.2.033446.
https://doi.org/10.1103/PhysRevResearch.2.033446

[32] Ruslan Shaydulin, Ilya Safro, and Jeffrey Larson. Multistart methods for quantum approximate optimization. 2019 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–8, Sep 2019. 10.1109/HPEC.2019.8916288.
https://doi.org/10.1109/HPEC.2019.8916288

[33] Ruslan Shaydulin and Yuri Alexeev. Evaluating quantum approximate optimization algorithm: A case study. In 2019 Tenth International Green and Sustainable Computing Conference (IGSC), pages 1–6, 2019. 10.1109/IGSC48788.2019.8957201.
https://doi.org/10.1109/IGSC48788.2019.8957201

[34] Roeland Wiersema, Cunlu Zhou, Yvette de Sereville, Juan Felipe Carrasquilla, Yong Baek Kim, and Henry Yuen. Exploring entanglement and optimization within the hamiltonian variational ansatz. PRX Quantum, 1: 020319, Dec 2020. 10.1103/PRXQuantum.1.020319.
https://doi.org/10.1103/PRXQuantum.1.020319

[35] Fernando G. S. L. Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven. For fixed control parameters the quantum approximate optimization algorithm's objective function value concentrates for typical instances, 2018. URL https://arxiv.org/abs/1812.04170.
arXiv:1812.04170

[36] Matthew B. Hastings. Classical and quantum bounded depth approximation algorithms, 2019. URL https://arxiv.org/abs/1905.07047.
arXiv:1905.07047

[37] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Hybrid quantum-classical algorithms for approximate graph coloring, 2020b. URL https://arxiv.org/abs/2011.13420.
arXiv:2011.13420

[38] Mahabubul Alam, Abdullah Ash-Saki, and Swaroop Ghosh. Analysis of quantum approximate optimization algorithm under realistic noise in superconducting qubits, 2019. URL https://arxiv.org/abs/1907.09631.
arXiv:1907.09631

[39] Vishwanathan Akshay, Hariphan Philathong, Mauro E. S. Morales, and Jacob D. Biamonte. Reachability deficits in quantum approximate optimization. Phys. Rev. Lett., 124: 090504, Mar 2020a. 10.1103/PhysRevLett.124.090504.
https://doi.org/10.1103/PhysRevLett.124.090504

[40] Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, Sergio Boixo, and et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nat. Phys., 17 (3): 332–336, Mar 2021. 10.1038/s41567-020-01105-y.
https://doi.org/10.1038/s41567-020-01105-y

[41] Yulong Dong, Xiang Meng, Lin Lin, Robert Kosut, and K. Birgitta Whaley. Robust control optimization for quantum approximate optimization algorithms. IFAC-PapersOnLine, 53 (2): 242–249, 2020. 10.1016/j.ifacol.2020.12.130. 21th IFAC World Congress.
https://doi.org/10.1016/j.ifacol.2020.12.130

[42] Nathan Lacroix, Christoph Hellings, Christian Kraglund Andersen, Agustin Di Paolo, Ants Remm, Stefania Lazar, Sebastian Krinner, Graham J. Norris, Mihai Gabureac, Johannes Heinsoo, and et al. Improving the performance of deep quantum optimization algorithms with continuous gate sets. PRX Quantum, 1: 110304, Oct 2020. 10.1103/PRXQuantum.1.020304.
https://doi.org/10.1103/PRXQuantum.1.020304

[43] Nathan Earnest, Caroline Tornow, and Daniel J. Egger. Pulse-efficient circuit transpilation for quantum applications on cross-resonance-based hardware, 2021. URL https://arxiv.org/abs/2105.01063.
arXiv:2105.01063

[44] Pranav Gokhale, Ali Javadi-Abhari, Nathan Earnest, Yunong Shi, and Frederic T. Chong. Optimized quantum compilation for near-term algorithms with openpulse, 2020. URL https://www.microarch.org/micro53/papers/738300a186.pdf. 10.1109/MICRO50266.2020.00027.
https://doi.org/10.1109/MICRO50266.2020.00027
https://www.microarch.org/micro53/papers/738300a186.pdf

[45] David C. McKay, Thomas Alexander, Luciano Bello, Michael J. Biercuk, Lev Bishop, Jiayin Chen, Jerry M. Chow, Antonio D. Córcoles, Daniel J. Egger, Stefan Filipp, and et al. Qiskit backend specifications for OpenQASM and OpenPulse experiments, 2018. URL https://arxiv.org/abs/1809.03452.
arXiv:1809.03452

[46] Thomas Alexander, Naoki Kanazawa, Daniel J. Egger, Lauren Capelluto, Christopher J. Wood, Ali Javadi-Abhari, and David C. McKay. Qiskit pulse: programming quantum computers through the cloud with pulses. Quantum Sci. Technol., 5 (4): 044006, Aug 2020. 10.1088/2058-9565/aba404.
https://doi.org/10.1088/2058-9565/aba404

[47] Anirudha Majumdar, Georgina Hall, and Amir Ali Ahmadi. Recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics. Annu. Rev. Control Robot. Auton. Syst., 3: 331–360, 2020. 10.1146/annurev-control-091819-074326.
https://doi.org/10.1146/annurev-control-091819-074326

[48] Miguel F. Anjos and Jean B. Lasserre. Handbook on semidefinite, conic and polynomial optimization, volume 166. Springer Science & Business Media, 2011. 10.1007/978-1-4614-0769-0.
https://doi.org/10.1007/978-1-4614-0769-0

[49] Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. Complexity and real computation. Springer Science & Business Media, 2012. 10.1007/978-1-4612-0701-6.
https://doi.org/10.1007/978-1-4612-0701-6

[50] Lorant Porkolab and Leonid Khachiyan. On the complexity of semidefinite programs. J. Glob. Optim., 10 (4): 351–365, 1997. 10.1023/A:1008203903341.
https://doi.org/10.1023/A:1008203903341

[51] Alp Yurtsever, Joel A. Tropp, Olivier Fercoq, Madeleine Udell, and Volkan Cevher. Scalable semidefinite programming. SIAM J. Math. Data Sci., 3 (1): 171–200, 2021. 10.1137/19M1305045.
https://doi.org/10.1137/19M1305045

[52] Prabhakar Raghavan and Clark D. Tompson. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7 (4): 365–374, Dec 1987. 10.1007/BF02579324.
https://doi.org/10.1007/BF02579324

[53] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42 (6): 1115–1145, nov 1995. 10.1145/227683.227684.
https://doi.org/10.1145/227683.227684

[54] Howard Karloff. How good is the Goemans–Williamson MAX CUT algorithm? SIAM J. Comput., 29 (1): 336–350, 1999. 10.1137/S0097539797321481.
https://doi.org/10.1137/S0097539797321481

[55] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37 (1): 319–357, 2007. 10.1137/S0097539705447372.
https://doi.org/10.1137/S0097539705447372

[56] Subhas Khot. On the unique games conjecture (invited survey). In 2012 IEEE 27th Conference on Computational Complexity, pages 99–121, Los Alamitos, CA, USA, jun 2010. IEEE Computer Society. 10.1109/CCC.2010.19.
https://doi.org/10.1109/CCC.2010.19

[57] Subhash A. Khot and Nisheeth K. Vishnoi. The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into l1. J. ACM, 62 (1): 1–39, 2015. 10.1145/2629614.
https://doi.org/10.1145/2629614

[58] Kunal Marwaha. Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs. Quantum, 5: 437, April 2021. 10.22331/q-2021-04-20-437.
https://doi.org/10.22331/q-2021-04-20-437

[59] Peter L. Hammer and Sergiu Rudeanu. Boolean methods in operations research and related areas. Springer Science & Business Media, 1968. 10.1007/978-3-642-85823-9.
https://doi.org/10.1007/978-3-642-85823-9

[60] Jean B. Lasserre. A MAX-CUT formulation of 0/1 programs. Oper. Res. Lett., 44 (2): 158 – 164, 2016. 10.1016/j.orl.2015.12.014.
https://doi.org/10.1016/j.orl.2015.12.014

[61] Panos M. Pardalos and Georg Schnitger. Checking local optimality in constrained quadratic programming is np-hard. Oper. Res. Lett., 7 (1): 33–35, 1988. 10.1016/0167-6377(88)90049-1.
https://doi.org/10.1016/0167-6377(88)90049-1

[62] Kim Allemand, Komei Fukuda, Thomas M Liebling, and Erich Steiner. A polynomial case of unconstrained zero-one quadratic optimization. Math. Program., 91 (1): 49–52, 2001. 10.1007/s101070100233.
https://doi.org/10.1007/s101070100233

[63] Milan Hladík, Michal Černý, and Miroslav Rada. A new polynomially solvable class of quadratic optimization problems with box constraints. arXiv:1911.10877, 2019. URL https://arxiv.org/abs/1911.10877.
arXiv:1911.10877

[64] Jacek Gondzio and Andreas Grothey. Solving nonlinear financial planning problems with $10^9$ decision variables on massively parallel architectures. WIT Trans Modelling Simul., 43: 11, 2006. 10.2495/CF060101.
https://doi.org/10.2495/CF060101

[65] Svatopluk Poljak, Franz Rendl, and Henry Wolkowicz. A recipe for semidefinite relaxation for (0, 1)-quadratic programming. J. Glob. Optim., 7 (1): 51–73, 1995. 10.1007/BF01100205.
https://doi.org/10.1007/BF01100205

[66] 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. 10.22331/q-2020-02-14-230.
https://doi.org/10.22331/q-2020-02-14-230

[67] 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 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. ISBN 978-3-95977-109-2. 10.4230/LIPIcs.ICALP.2019.27.
https://doi.org/10.4230/LIPIcs.ICALP.2019.27

[68] Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang. Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1–23:15, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. ISBN 978-3-95977-159-7. 10.4230/LIPIcs.MFCS.2020.23.
https://doi.org/10.4230/LIPIcs.MFCS.2020.23

[69] Jacek Gondzio. Warm start of the primal-dual method applied in the cutting-plane scheme. Math. Program., 83 (1-3): 125–143, 1998. 10.1007/BF02680554.
https://doi.org/10.1007/BF02680554

[70] Andrew Lucas. Ising formulations of many NP problems. Front. Phys., 2: 5, 2014. 10.3389/fphy.2014.00005.
https://doi.org/10.3389/fphy.2014.00005

[71] Bas Lodewijks. Mapping np-hard and NP-complete optimisation problems to quadratic unconstrained binary optimisation problems. arXiv:1911.08043, 2019. URL https://arxiv.org/abs/1911.08043.
arXiv:1911.08043

[72] Jean B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM J. Optim., 11 (3): 796–817, 2001. 10.1137/S1052623400366802.
https://doi.org/10.1137/S1052623400366802

[73] Jean B. Lasserre. Convergent SDP-relaxations in polynomial optimization with sparsity. SIAM J. Optim., 17 (3): 822–843, 2006. 10.1137/05064504X.
https://doi.org/10.1137/05064504X

[74] Bissan Ghaddar, Juan C. Vera, and Miguel F. Anjos. Second-order cone relaxations for binary quadratic polynomial programs. SIAM J. Optim., 21 (1): 391–414, 2011. 10.1137/100802190.
https://doi.org/10.1137/100802190

[75] Moses Charikar and Anthony Wirth. Maximizing quadratic programs: Extending Grothendieck's inequality. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 54–60. IEEE, 2004. 10.1109/FOCS.2004.39.
https://doi.org/10.1109/FOCS.2004.39

[76] Mikhail Krechetov, Jakub Mareček, Yury Maximov, and Martin Takáč. Entropy-penalized semidefinite programming. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2019. 10.24963/ijcai.2019/157.
https://doi.org/10.24963/ijcai.2019/157

[77] Sartaj Sahni and Teofilo Gonzalez. P-complete approximation problems. J. ACM, 23 (3): 555–565, 1976. 10.1145/321958.321975. See Lemma A2.
https://doi.org/10.1145/321958.321975

[78] Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.

[79] Sepehr Abbasi-Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz, and Mohit Singh. Sticky brownian rounding and its applications to constraint satisfaction problems. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 854–873. SIAM, 2020. 10.1137/1.9781611975994.52.
https://doi.org/10.1137/1.9781611975994.52

[80] Ronen Eldan and Assaf Naor. Krivine diffusions attain the goemans–williamson approximation ratio. arXiv:1906.10615, 2019. URL https://arxiv.org/abs/1906.10615.
arXiv:1906.10615

[81] Jamie Morgenstern, Samira Samadi, Mohit Singh, Uthaipon Tantipongpipat, and Santosh Vempala. Fair dimensionality reduction and iterative rounding for SDPs. arXiv:1902.11281, 2019. URL https://arxiv.org/abs/1902.11281v1.
arXiv:1902.11281

[82] Samuel Karlin and Howard E. Taylor. A second course in stochastic processes. Elsevier, 1981. p. 257 and the following.

[83] Julia Kempe, Oded Regev, and Ben Toner. The unique games conjecture with entangled provers is false. In Algebraic Methods in Computational Complexity, 2007.

[84] Julia Kempe, Oded Regev, and Ben Toner. Unique games with entangled provers are easy. SIAM J. Comput., 39 (7): 3207–3229, 2010. 10.1137/090772885.
https://doi.org/10.1137/090772885

[85] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM J. Comput., 26 (5): 1510–1523, 1997. 10.1137/S0097539796300933.
https://doi.org/10.1137/S0097539796300933

[86] Harry Markowitz. Portfolio selection. J. Finance, 7 (1): 77–91, 1952. 10.2307/2975974.
https://doi.org/10.2307/2975974

[87] H. Abraham et al. Qiskit: An open-source framework for quantum computing, 2019. URL https://doi.org/10.5281/zenodo.2562111.
https://doi.org/10.5281/zenodo.2562111

[88] Johan Håstad. Some optimal inapproximability results. J. ACM, 48 (4): 798–859, 2001. 10.1145/502090.502098.
https://doi.org/10.1145/502090.502098

[89] Vishwanathan Akshay, Hariphan Philathong, Igor Zacharov, and Jacob D. Biamonte. Reachability deficits implicit in google's quantum approximate optimization of graph problems, 2020b. URL https://arxiv.org/abs/2007.09148.
arXiv:2007.09148

[90] Rebekah Herrman, James Ostrowski, Travis S. Humble, and George Siopsis. Lower bounds on circuit depth of the quantum approximate optimization algorithm. Quantum Inf. Process., 20 (2): 59, Feb 2021. 10.1007/s11128-021-03001-7.
https://doi.org/10.1007/s11128-021-03001-7

[91] Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel. Quantum approximate optimization algorithm for maxcut: A fermionic view. Phys. Rev. A, 97: 022304, Feb 2018. 10.1103/PhysRevA.97.022304.
https://doi.org/10.1103/PhysRevA.97.022304

[92] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Phys. Rev. X, 10: 021067, Jun 2020. 10.1103/PhysRevX.10.021067.
https://doi.org/10.1103/PhysRevX.10.021067

[93] Jason Larkin, Matías Jonsson, Daniel Justice, and Gian Giacomo Guerreschi. Evaluation of quantum approximate optimization algorithm based on the approximation ratio of single samples, 2020. URL https://arxiv.org/abs/2006.04831.
arXiv:2006.04831

[94] qiskit-optimization. https://github.com/Qiskit/qiskit-optimization. Accessed: 25. 04. 2021.
https://github.com/Qiskit/qiskit-optimization

[95] Andreas Bärtschi and Stephan Eidenbenz. Grover mixers for qaoa: Shifting complexity from mixer design to state preparation. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 72–82, 2020. 10.1109/QCE49297.2020.00020.
https://doi.org/10.1109/QCE49297.2020.00020

[96] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler, and Swati Gupta. Bridging classical and quantum with SDP initialized warm-starts for QAOA, 2020. URL https://arxiv.org/abs/2010.14021.
arXiv:2010.14021

[97] Iain Dunning, Swati Gupta, and John Silberholz. What works best when? a systematic evaluation of heuristics for Max-Cut and QUBO. INFORMS J. Comput., 30 (3): 608–624, 2018. 10.1287/ijoc.2017.0798.
https://doi.org/10.1287/ijoc.2017.0798

[98] Panagiotis Kl. Barkoutsos, Jerome F. Gonthier, Igor Sokolov, Nikolaj Moll, Gian Salis, Andreas Fuhrer, Marc Ganzhorn, Daniel J. Egger, Matthias Troyer, Antonio Mezzacapo, and et al. Quantum algorithms for electronic structure calculations: Particle-hole hamiltonian and optimized wave-function expansions. Phys. Rev. A, 98: 022322, Aug 2018. 10.1103/PhysRevA.98.022322.
https://doi.org/10.1103/PhysRevA.98.022322

[99] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of np. J. ACM, 45 (1): 70–122, 1998. 10.1145/273865.273901.
https://doi.org/10.1145/273865.273901

[100] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45 (3): 501–555, 1998. 10.1145/278298.278306.
https://doi.org/10.1145/278298.278306

[101] Irit Dinur. The PCP theorem by gap amplification. J. ACM, 54 (3): 12–es, jun 2007. 10.1145/1236457.1236459.
https://doi.org/10.1145/1236457.1236459

[102] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009.

[103] Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, STOC '02, pages 767–775, New York, NY, USA, 2002. Association for Computing Machinery. 10.1145/509907.510017.
https://doi.org/10.1145/509907.510017

[104] Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 245–254, 2008. 10.1145/1374376.1374414.
https://doi.org/10.1145/1374376.1374414

[105] Prasad Raghavendra and David Steurer. How to round any CSP. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 586–594, 2009. 10.1109/FOCS.2009.74.
https://doi.org/10.1109/FOCS.2009.74

[106] Subhash Khot, Dor Minzer, and Muli Safra. Pseudorandom sets in grassmann graph have near-perfect expansion. In Proceedings of the fifty-ninth Annual Symposium on Foundations of Computer Science (FOCS), pages 592–601, 2018. 10.1109/FOCS.2018.00062.
https://doi.org/10.1109/FOCS.2018.00062

[107] Boaz Barak, Prasad Raghavendra, and David Steurer. Rounding semidefinite programming hierarchies via global correlation. In Proceedings of the fiftysecond annual symposium on foundations of computer science, pages 472–481. IEEE, 2011. 10.1109/FOCS.2011.95.
https://doi.org/10.1109/FOCS.2011.95

[108] Samuel B. Hopkins, Tselil Schramm, and Luca Trevisan. Subexponential LPs approximate max-cut. In Proceedings of the sixtyfirst Annual Symposium on Foundations of Computer Science (FOCS), pages 943–953. IEEE, 2020. 10.1109/FOCS46700.2020.00092.
https://doi.org/10.1109/FOCS46700.2020.00092

[109] Albert Einstein, Boris Podolsky, and Nathan Rosen. Can quantum-mechanical description of physical reality be considered complete? Phys. Rev., 47 (10): 777, 1935. 10.1103/PhysRev.47.777.
https://doi.org/10.1103/PhysRev.47.777

[110] Boris S. Cirel'son. Quantum generalizations of Bell's inequality. Lett. Math. Phys., 4 (2): 93–100, 1980. 10.1007/BF00417500.
https://doi.org/10.1007/BF00417500

[111] A. Natarajan and T. Vidick. Low-degree testing for quantum states, and a quantum entangled games PCP for QMA. In Proceedings of the fiftyninth Annual Symposium on Foundations of Computer Science (FOCS), pages 731–742, 2018. 10.1109/FOCS.2018.00075.
https://doi.org/10.1109/FOCS.2018.00075

[112] Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani. The detectability lemma and quantum gap amplification. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, pages 417–426, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 9781605585062. 10.1145/1536414.1536472.
https://doi.org/10.1145/1536414.1536472

[113] Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Near-optimal algorithms for unique games. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 205–214, 2006. 10.1145/1132516.1132547.
https://doi.org/10.1145/1132516.1132547

[114] Dimitris Achlioptas, Assaf Naor, and Yuval Peres. Rigorous location of phase transitions in hard optimization problems. Nature, 435 (7043): 759–764, 2005. 10.1038/nature03602.
https://doi.org/10.1038/nature03602

[115] Don Coppersmith, David Gamarnik, Mohammad T. Hajiaghayi, and Gregory B. Sorkin. Random MAX SAT, random MAX CUT, and their phase transitions. Random Struct. Algorithms, 24 (4): 502–545, 2004. 10.1002/rsa.20015.
https://doi.org/10.1002/rsa.20015

Cited by

[1] Nima Nikmehr, Peng Zhang, and Mikhail A. Bragin, "Quantum Distributed Unit Commitment: An Application in Microgrids", IEEE Transactions on Power Systems 37 5, 3592 (2022).

[2] Nathan Earnest, Caroline Tornow, and Daniel J. Egger, "Pulse-efficient circuit transpilation for quantum applications on cross-resonance-based hardware", Physical Review Research 3 4, 043088 (2021).

[3] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik, "Noisy intermediate-scale quantum algorithms", Reviews of Modern Physics 94 1, 015004 (2022).

[4] He-Liang Huang, Xiao-Yue Xu, Chu Guo, Guojing Tian, Shi-Jie Wei, Xiaoming Sun, Wan-Su Bao, and Gui-Lu Long, "Near-term quantum computing techniques: Variational quantum algorithms, error mitigation, circuit compilation, benchmarking and classical simulation", Science China Physics, Mechanics, and Astronomy 66 5, 250302 (2023).

[5] Johannes Weidenfeller, Lucia C. Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Woerner, and Daniel J. Egger, "Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware", Quantum 6, 870 (2022).

[6] Takuya Yoshioka, Keita Sasada, Yuichiro Nakano, and Keisuke Fujii, "Fermionic quantum approximate optimization algorithm", Physical Review Research 5 2, 023071 (2023).

[7] James Dborin, Fergus Barratt, Vinul Wimalaweera, Lewis Wright, and Andrew G. Green, "Matrix product state pre-training for quantum machine learning", Quantum Science and Technology 7 3, 035014 (2022).

[8] Amir M Aghaei, Bela Bauer, Kirill Shtengel, and Ryan V. Mishmash, "Efficient matrix-product-state preparation of highly entangled trial states: Weak Mott insulators on the triangular lattice revisited", arXiv:2009.12435, (2020).

[9] G. Wendin, "Quantum information processing with superconducting circuits: a perspective", arXiv:2302.04558, (2023).

[10] Phillip C. Lotshaw, Thien Nguyen, Anthony Santana, Alexander McCaskey, Rebekah Herrman, James Ostrowski, George Siopsis, and Travis S. Humble, "Scaling quantum approximate optimization on near-term hardware", Scientific Reports 12, 12388 (2022).

[11] Stefan H. Sack and Maksym Serbyn, "Quantum annealing initialization of the quantum approximate optimization algorithm", Quantum 5, 491 (2021).

[12] Bryce Fuller, Charles Hadfield, Jennifer R. Glick, Takashi Imamichi, Toshinari Itoko, Richard J. Thompson, Yang Jiao, Marna M. Kagele, Adriana W. Blom-Schieber, Rudy Raymond, and Antonio Mezzacapo, "Approximate Solutions of Combinatorial Problems via Quantum Relaxations", arXiv:2111.03167, (2021).

[13] Samuel Duffield, Marcello Benedetti, and Matthias Rosenkranz, "Bayesian learning of parameterised quantum circuits", Machine Learning: Science and Technology 4 2, 025007 (2023).

[14] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler, and Swati Gupta, "Bridging Classical and Quantum with SDP initialized warm-starts for QAOA", arXiv:2010.14021, (2020).

[15] Laurin E. Fischer, Daniel Miller, Francesco Tacchino, Panagiotis Kl. Barkoutsos, Daniel J. Egger, and Ivano Tavernelli, "Ancilla-free implementation of generalized measurements for qubits embedded in a qudit space", Physical Review Research 4 3, 033027 (2022).

[16] Jonathan Wurtz and Peter J. Love, "Counterdiabaticity and the quantum approximate optimization algorithm", Quantum 6, 635 (2022).

[17] Noah L. Wach, Manuel S. Rudolph, Fred Jendrzejewski, and Sebastian Schmitt, "Data re-uploading with a single qudit", arXiv:2302.13932, (2023).

[18] Christa Zoufal, Ryan V. Mishmash, Nitin Sharma, Niraj Kumar, Aashish Sheshadri, Amol Deshmukh, Noelle Ibrahim, Julien Gacon, and Stefan Woerner, "Variational quantum algorithm for unconstrained black box binary optimization: Application to feature selection", Quantum 7, 909 (2023).

[19] M. Werninghaus, D. J. Egger, and S. Filipp, "High-Speed Calibration and Characterization of Superconducting Quantum Processors without Qubit Reset", PRX Quantum 2 2, 020324 (2021).

[20] Nishant Jain, Brian Coyle, Elham Kashefi, and Niraj Kumar, "Graph neural network initialisation of quantum approximate optimisation", Quantum 6, 861 (2022).

[21] Johanna Barzen, "From Digital Humanities to Quantum Humanities: Potentials and Applications", arXiv:2103.11825, (2021).

[22] Ioannis Kolotouros and Petros Wallden, "Evolving objective function for improved variational quantum optimization", Physical Review Research 4 2, 023225 (2022).

[23] Archismita Dalal and Amara Katabarwa, "Noise tailoring for robust amplitude estimation", New Journal of Physics 25 2, 023015 (2023).

[24] Teague Tomesh, Zain H. Saleem, and Martin Suchara, "Quantum Local Search with the Quantum Alternating Operator Ansatz", Quantum 6, 781 (2022).

[25] Austin Gilliam, Stefan Woerner, and Constantin Gonciulea, "Grover Adaptive Search for Constrained Polynomial Binary Optimization", arXiv:1912.04088, (2019).

[26] Elijah Pelofske, "Mapping state transition susceptibility in quantum annealing", Physical Review Research 5 1, 013224 (2023).

[27] Zain H. Saleem, Teague Tomesh, Bilal Tariq, and Martin Suchara, "Approaches to Constrained Quantum Approximate Optimization", arXiv:2010.06660, (2020).

[28] Austin Gilliam, Stefan Woerner, and Constantin Gonciulea, "Grover Adaptive Search for Constrained Polynomial Binary Optimization", Quantum 5, 428 (2021).

[29] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang, "Hybrid quantum-classical algorithms for approximate graph coloring", Quantum 6, 678 (2022).

[30] Constantin Dalyac, Loïc Henriet, Emmanuel Jeandel, Wolfgang Lechner, Simon Perdrix, Marc Porcheron, and Margarita Veshchezerova, "Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles", arXiv:2012.14859, (2020).

[31] Daniel Beaulieu and Anh Pham, "Max-cut Clustering Utilizing Warm-Start QAOA and IBM Runtime", arXiv:2108.13464, (2021).

[32] Wim van Dam, Karim Eldefrawy, Nicholas Genise, and Natalie Parham, "Quantum Optimization Heuristics with an Application to Knapsack Problems", arXiv:2108.08805, (2021).

[33] Nicolas PD Sawaya, Albert T Schmitz, and Stuart Hadfield, "Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems", arXiv:2203.14432, (2022).

[34] Franz G. Fuchs, Kjetil Olsen Lye, Halvor Møll Nilsen, Alexander J. Stasik, and Giorgio Sartor, "Constrained mixers for the quantum approximate optimization algorithm", arXiv:2203.06095, (2022).

[35] Jonathan Wurtz and Peter Love, "Classically optimal variational quantum algorithms", arXiv:2103.17065, (2021).

[36] Vicente P. Soloviev, Concha Bielza, and Pedro Larrañaga, "Quantum approximate optimization algorithm for Bayesian network structure learning", Quantum Information Processing 22 1, 19 (2023).

[37] Stuart M. Harwood, Dimitar Trenev, Spencer T. Stober, Panagiotis Barkoutsos, Tanvi P. Gujarati, Sarah Mostame, and Donny Greenberg, "Improving the variational quantum eigensolver using variational adiabatic quantum computing", arXiv:2102.02875, (2021).

[38] Alicia B. Magann, Kenneth M. Rudinger, Matthew D. Grace, and Mohan Sarovar, "Lyapunov-control-inspired strategies for quantum combinatorial optimization", Physical Review A 106 6, 062414 (2022).

[39] Sami Boulebnane, "Improving the Quantum Approximate Optimization Algorithm with postselection", arXiv:2011.05425, (2020).

[40] Daniel Beaulieu and Anh Pham, "Evaluating performance of hybrid quantum optimization algorithms for MAXCUT Clustering using IBM runtime environment", arXiv:2112.03199, (2021).

[41] Elijah Pelofske, Georg Hahn, and Hristo Djidjev, "Initial state encoding via reverse quantum annealing and h-gain features", arXiv:2303.13748, (2023).

[42] Lilly Palackal, Benedikt Poggel, Matthias Wulff, Hans Ehm, Jeanette Miriam Lorenz, and Christian B. Mendl, "Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem", arXiv:2304.09629, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-05-31 15:27:30) and SAO/NASA ADS (last updated successfully 2023-06-05 13:42:11). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2023-06-05 13:42:08: Encountered the unhandled forward link type postedcontent_cite while looking for citations to DOI 10.22331/q-2021-06-17-479.

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.