Improving Variational Quantum Optimization using CVaR

Panagiotis Kl. Barkoutsos; Giacomo Nannicini; Anton Robert; Ivano Tavernelli; Stefan Woerner

doi:10.22331/q-2020-04-20-256

Improving Variational Quantum Optimization using CVaR

Panagiotis Kl. Barkoutsos¹, Giacomo Nannicini², Anton Robert^1,3, Ivano Tavernelli¹, and Stefan Woerner¹

¹IBM Research – Zurich
²IBM T.J. Watson Research Center
³École Normale Supérieure, PSL University, Paris

Published:	2020-04-20, volume 4, page 256
Eprint:	arXiv:1907.04769v3
Doi:	https://doi.org/10.22331/q-2020-04-20-256
Citation:	Quantum 4, 256 (2020).

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

Abstract

Hybrid quantum/classical variational algorithms can be implemented on noisy intermediate-scale quantum computers and can be used to find solutions for combinatorial optimization problems. Approaches discussed in the literature minimize the expectation of the problem Hamiltonian for a parameterized trial quantum state. The expectation is estimated as the sample mean of a set of measurement outcomes, while the parameters of the trial state are optimized classically. This procedure is fully justified for quantum mechanical observables such as molecular energies. In the case of classical optimization problems, which yield diagonal Hamiltonians, we argue that aggregating the samples in a different way than the expected value is more natural. In this paper we propose the Conditional Value-at-Risk as an aggregation function. We empirically show -- using classical simulation as well as quantum hardware -- that this leads to faster convergence to better solutions for all combinatorial optimization problems tested in our study. We also provide analytical results to explain the observed difference in performance between different variational algorithms.

► BibTeX data

@article{Barkoutsos2020improving,
  doi = {10.22331/q-2020-04-20-256},
  url = {https://doi.org/10.22331/q-2020-04-20-256},
  title = {Improving {V}ariational {Q}uantum {O}ptimization using {CV}a{R}},
  author = {Barkoutsos, Panagiotis Kl. and Nannicini, Giacomo and Robert, Anton and Tavernelli, Ivano and Woerner, Stefan},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {256},
  month = apr,
  year = {2020}
}

► References

[1] Karen Aardal, Robert E Bixby, Cor AJ Hurkens, Arjen K Lenstra, and Job W Smeltink. Market split and basis reduction: Towards a solution of the cornuéjols-dawande instances. INFORMS Journal on Computing, 12 (3): 192–202, 2000. ISSN 1091-9856. 10.1287/ijoc.12.3.192.12635.
https://doi.org/10.1287/ijoc.12.3.192.12635

[2] Héctor Abraham, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, Thomas Alexander, Gadi Alexandrowics, Eli Arbel, Abraham Asfaw, Carlos Azaustre, AzizNgoueya, Panagiotis Barkoutsos, George Barron, Luciano Bello, Yael Ben-Haim, Daniel Bevenius, Lev S. Bishop, Sorin Bolos, Samuel Bosch, Sergey Bravyi, David Bucher, Fran Cabrera, Padraic Calpin, Lauren Capelluto, Jorge Carballo, Ginés Carrascal, Adrian Chen, Chun-Fu Chen, Richard Chen, Jerry M. Chow, Christian Claus, Christian Clauss, Abigail J. Cross, Andrew W. Cross, Simon Cross, Juan Cruz-Benito, Chris Culver, Antonio D. Córcoles-Gonzales, Sean Dague, Tareq El Dandachi, Matthieu Dartiailh, DavideFrr, Abdón Rodríguez Davila, Delton Ding, Jun Doi, Eric Drechsler, Drew, Eugene Dumitrescu, Karel Dumon, Ivan Duran, Kareem EL-Safty, Eric Eastman, Pieter Eendebak, Daniel Egger, Mark Everitt, Paco Martín Fernández, Axel Hernández Ferrera, Albert Frisch, Andreas Fuhrer, MELVIN GEORGE, Julien Gacon, Gadi, Borja Godoy Gago, Jay M. Gambetta, Adhisha Gammanpila, Luis Garcia, Shelly Garion, Juan Gomez-Mosquera, Salvador de la Puente González, Jesse Gorzinski, Ian Gould, Donny Greenberg, Dmitry Grinko, Wen Guan, John A. Gunnels, Mikael Haglund, Isabel Haide, Ikko Hamamura, Vojtech Havlicek, Joe Hellmers, Łukasz Herok, Stefan Hillmich, Hiroshi Horii, Connor Howington, Shaohan Hu, Wei Hu, Haruki Imai, Takashi Imamichi, Kazuaki Ishizaki, Raban Iten, Toshinari Itoko, Ali Javadi, Ali Javadi-Abhari, Jessica, Kiran Johns, Tal Kachmann, Naoki Kanazawa, Kang-Bae, Anton Karazeev, Paul Kassebaum, Spencer King, Knabberjoe, Arseny Kovyrshin, Rajiv Krishnakumar, Vivek Krishnan, Kevin Krsulich, Gawel Kus, Ryan LaRose, Raphaël Lambert, Joe Latone, Scott Lawrence, Dennis Liu, Peng Liu, Yunho Maeng, Aleksei Malyshev, Jakub Marecek, Manoel Marques, Dolph Mathews, Atsushi Matsuo, Douglas T. McClure, Cameron McGarry, David McKay, Dan McPherson, Srujan Meesala, Martin Mevissen, Antonio Mezzacapo, Rohit Midha, Zlatko Minev, Abby Mitchell, Nikolaj Moll, Michael Duane Mooring, Renier Morales, Niall Moran, Prakash Murali, Jan Müggenburg, David Nadlinger, Ken Nakanishi, Giacomo Nannicini, Paul Nation, Yehuda Naveh, Patrick Neuweiler, Pradeep Niroula, Hassi Norlen, Lee James O'Riordan, Oluwatobi Ogunbayo, Pauline Ollitrault, Steven Oud, Dan Padilha, Hanhee Paik, Simone Perriello, Anna Phan, Francesco Piro, Marco Pistoia, Alejandro Pozas-iKerstjens, Viktor Prutyanov, Daniel Puzzuoli, Jesús Pérez, Quintiii, Rudy Raymond, Rafael Martín-Cuevas Redondo, Max Reuter, Julia Rice, Diego M. Rodríguez, RohithKarur, Max Rossmannek, Mingi Ryu, Tharrmashastha SAPV, SamFerracin, Martin Sandberg, Hayk Sargsyan, Ninad Sathaye, Bruno Schmitt, Chris Schnabel, Zachary Schoenfeld, Travis L. Scholten, Eddie Schoute, Joachim Schwarm, Ismael Faro Sertage, Kanav Setia, Nathan Shammah, Yunong Shi, Adenilton Silva, Andrea Simonetto, Nick Singstock, Yukio Siraichi, Iskandar Sitdikov, Seyon Sivarajah, Magnus Berg Sletfjerding, John A. Smolin, Mathias Soeken, Igor Olegovich Sokolov, SooluThomas, Dominik Steenken, Matt Stypulkoski, Jack Suen, Kevin J. Sung, Hitomi Takahashi, Ivano Tavernelli, Charles Taylor, Pete Taylour, Soolu Thomas, Mathieu Tillet, Maddy Tod, Enrique de la Torre, Kenso Trabing, Matthew Treinish, TrishaPe, Wes Turner, Yotam Vaknin, Carmen Recio Valcarce, Francois Varchon, Almudena Carrera Vazquez, Desiree Vogt-Lee, Christophe Vuillot, James Weaver, Rafal Wieczorek, Jonathan A. Wildstrom, Robert Wille, Erick Winston, Jack J. Woehr, Stefan Woerner, Ryan Woo, Christopher J. Wood, Ryan Wood, Steve Wood, James Wootton, Daniyar Yeralin, Richard Young, Jessie Yu, Christopher Zachow, Laura Zdanski, Christa Zoufal, Zoufalc, a matsuo, azulehner, bcamorrison, brandhsn, chlorophyll zz, dan1pal, dime10, drholmie, elfrocampeador, enavarro51, faisaldebouni, fanizzamarco, gadial, gruu, kanejess, klinvill, kurarrr, lerongil, ma5x, merav aharoni, michelle4654, ordmoj, sethmerkel, strickroman, sumitpuri, tigerjack, toural, vvilpas, welien, willhbang, yang.luh, yelojakit, and yotamvakninibm. Qiskit: An open-source framework for quantum computing, 2019. URL https://qiskit.org.
https://qiskit.org

[3] Carlo Acerbi and Dirk Tasche. On the coherence of expected shortfall. Journal of Banking & Finance, 26 (7): 1487–1503, 2002. 10.1016/S0378-4266(02)00283-2.
https://doi.org/10.1016/S0378-4266(02)00283-2

[4] Francisco Barahona. On the computational complexity of ising spin glass models. Journal of Physics A: Mathematical and General, 15 (10): 3241, 1982. 10.1088/0305-4470/15/10/028.
https://doi.org/10.1088/0305-4470/15/10/028

[5] Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26 (5): 1411–1473, 1997. 10.1137/S0097539796300921.
https://doi.org/10.1137/S0097539796300921

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

[7] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm. arXiv preprint arXiv:1411.4028, pages 1–16, 2014a. URL http://arxiv.org/abs/1411.4028.
arXiv:1411.4028

[8] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem. arXiv preprint arXiv:1412.6062, 2014b. URL http://arxiv.org/abs/1412.6062.
arXiv:1412.6062

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

[10] E. Schuyler Fried, Nicolas P. D. Sawaya, Yudong Cao, Ian D. Kivlichan, Jhonathan Romero, and Alán Aspuru-Guzik. qTorch: The quantum tensor contraction handler. PLOS ONE, 13 (12): 1–20, 12 2018. 10.1371/journal.pone.0208510.
https://doi.org/10.1371/journal.pone.0208510

[11] Lov K Grover. Quantum mechanics helps in searching for a needle in a haystack. Physical review letters, 79 (2): 325, 1997. 10.1103/PhysRevLett.79.325.
https://doi.org/10.1103/PhysRevLett.79.325

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

[13] Jeff L. Hong. Monte carlo estimation of value-at-risk, conditional value-at-risk and their sensitivities. In Proceedings of the 2011 Winter Simulation Conference, pages 95–107. IEEE, 2011. 10.1109/WSC.2011.6147743.
https://doi.org/10.1109/WSC.2011.6147743

[14] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 549 (7671): 242, 2017. 10.1038/nature23879.
https://doi.org/10.1038/nature23879

[15] Andrew Lucas. Ising formulations of many np problems. Frontiers in Physics, 2: 5, 2014. ISSN 2296-424X. 10.3389/fphy.2014.00005.
https://doi.org/10.3389/fphy.2014.00005

[16] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn, Abhinav Kandala, Antonio Mezzacapo, Peter Müller, Walter Riess, Gian Salis, John Smolin, Ivano Tavernelli, and Kristan Temme. Quantum optimization using variational algorithms on near-term quantum devices. Quantum Science and Technology, 3 (3): 030503, 2018. 10.1088/2058-9565/aab822.
https://doi.org/10.1088/2058-9565/aab822

[17] Giacomo Nannicini. Performance of hybrid quantum-classical variational heuristics for combinatorial optimization. Physical Review E, 99: 013304, Jan 2019. 10.1103/PhysRevE.99.013304.
https://doi.org/10.1103/PhysRevE.99.013304

[18] G.L. Nemhauser and L.A. Wolsey. Integer and Combinatorial Optimization. Wiley, New York, 1988. 10.1002/9781118627372.
https://doi.org/10.1002/9781118627372

[19] Murphy Yuezhen Niu, Sirui Lu, and Isaac L Chuang. Optimizing qaoa: Success probability and runtime dependence on circuit depth. arXiv preprint arXiv:1905.12134, 2019. URL https://arxiv.org/abs/1905.12134.
arXiv:1905.12134

[20] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man Hong Yung, Xiao Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O'Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5, 2014. 10.1038/ncomms5213.
https://doi.org/10.1038/ncomms5213

Cited by

[1] Linghua Zhu, Ho Lun Tang, George S. Barron, F. A. Calderon-Vargas, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou, "An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer", arXiv:2005.10258, (2020).

[2] Anton Robert, Panagiotis Kl. Barkoutsos, Stefan Woerner, and Ivano Tavernelli, "Resource-efficient quantum algorithm for protein folding", npj Quantum Information 7, 38 (2021).

[3] James Sud, Stuart Hadfield, Eleanor Rieffel, Norm Tubman, and Tad Hogg, "A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz", arXiv:2211.09270, (2022).

[4] Daniel J. Egger, Jakub Mareček, and Stefan Woerner, "Warm-starting quantum optimization", Quantum 5, 479 (2021).

[5] Pablo Díez-Valle, Jorge Luis-Hita, Senaida Hernández-Santana, Fernando Martínez-García, Álvaro Díaz-Fernández, Eva Andrés, Juan José García-Ripoll, Escolástico Sánchez-Martínez, and Diego Porras, "Multiobjective variational quantum optimization for constrained problems: an application to cash handling", Quantum Science and Technology 8 4, 045009 (2023).

[6] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg, and Ilya Safro, "Classical symmetries and the Quantum Approximate Optimization Algorithm", Quantum Information Processing 20 11, 359 (2021).

[7] Jason Larkin, Matías Jonsson, Daniel Justice, and Gian Giacomo Guerreschi, "Evaluation of QAOA based on the approximation ratio of individual samples", Quantum Science and Technology 7 4, 045014 (2022).

[8] Antoine Michel, Sebastian Grijalva, Loïc Henriet, Christophe Domain, and Antoine Browaeys, "Blueprint for a digital-analog variational quantum eigensolver using Rydberg atom arrays", Physical Review A 107 4, 042602 (2023).

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

[10] George S. Barron, Bryan T. Gard, Orien J. Altman, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou, "Preserving Symmetries for Variational Quantum Eigensolvers in the Presence of Noise", Physical Review Applied 16 3, 034003 (2021).

[11] Alexandre Choquette, Agustin Di Paolo, Panagiotis Kl. Barkoutsos, David Sénéchal, Ivano Tavernelli, and Alexandre Blais, "Quantum-optimal-control-inspired ansatz for variational quantum algorithms", Physical Review Research 3 2, 023092 (2021).

[12] Linghua Zhu, Ho Lun Tang, George S. Barron, F. A. Calderon-Vargas, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou, "Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer", Physical Review Research 4 3, 033029 (2022).

[13] Jarrod R. McClean, Matthew P. Harrigan, Masoud Mohseni, Nicholas C. Rubin, Zhang Jiang, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven, "Low-Depth Mechanisms for Quantum Optimization", PRX Quantum 2 3, 030312 (2021).

[14] Charles Moussa, Henri Calandra, and Vedran Dunjko, "To quantum or not to quantum: towards algorithm selection in near-term quantum optimization", Quantum Science and Technology 5 4, 044009 (2020).

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

[16] Zeqiao Zhou, Yuxuan Du, Xinmei Tian, and Dacheng Tao, "QAOA-in-QAOA: Solving Large-Scale MaxCut Problems on Small Quantum Machines", Physical Review Applied 19 2, 024027 (2023).

[17] John Golden, Andreas Bärtschi, Stephan Eidenbenz, and Daniel O'Malley, "Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization", arXiv:2202.00648, (2022).

[18] Lucas Slattery, Benjamin Villalonga, and Bryan K. Clark, "Unitary block optimization for variational quantum algorithms", Physical Review Research 4 2, 023072 (2022).

[19] Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev, and Prasanna Balaprakash, "Reinforcement-Learning-Based Variational Quantum Circuits Optimization for Combinatorial Problems", arXiv:1911.04574, (2019).

[20] Xin Wang, Zhixin Song, and Youle Wang, "Variational Quantum Singular Value Decomposition", Quantum 5, 483 (2021).

[21] Giuseppe Scriva, Nikita Astrakhantsev, Sebastiano Pilati, and Guglielmo Mazzola, "Challenges of variational quantum optimization with measurement shot noise", arXiv:2308.00044, (2023).

[22] Marvin Bechtold, Johanna Barzen, Frank Leymann, Alexander Mandl, Julian Obst, Felix Truger, and Benjamin Weder, "Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices", Quantum Science and Technology 8 4, 045022 (2023).

[23] Anita Weidinger, Glen Bigan Mbeng, and Wolfgang Lechner, "Error mitigation for quantum approximate optimization", Physical Review A 108 3, 032408 (2023).

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

[25] Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev, and Prasanna Balaprakash, "Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems", arXiv:1911.11071, (2019).

[26] Ramin Ayanzadeh, Narges Alavisamani, Poulami Das, and Moinuddin Qureshi, "FrozenQubits: Boosting Fidelity of QAOA by Skipping Hotspot Nodes", arXiv:2210.17037, (2022).

[27] David Fitzek, Toheed Ghandriz, Leo Laine, Mats Granath, and Anton Frisk Kockum, "Applying quantum approximate optimization to the heterogeneous vehicle routing problem", arXiv:2110.06799, (2021).

[28] Lee Braine, Daniel J. Egger, Jennifer Glick, and Stefan Woerner, "Quantum Algorithms for Mixed Binary Optimization applied to Transaction Settlement", arXiv:1910.05788, (2019).

[29] Loïc Henriet, "Robustness to spontaneous emission of a variational quantum algorithm", Physical Review A 101 1, 012335 (2020).

[30] Daisuke Tsukayama, Jun-ichi Shirakashi, and Hiroshi Imai, "CoolMomentum mitigating local minima in variational quantum eigensolvers", Japanese Journal of Applied Physics 62 8, 088003 (2023).

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

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

[33] Martin R. Albrecht, Miloš Prokop, Yixin Shen, and Petros Wallden, "Variational quantum solutions to the Shortest Vector Problem", Quantum 7, 933 (2023).

[34] Andrew Patterson, Hongxiang Chen, Leonard Wossnig, Simone Severini, Dan Browne, and Ivan Rungger, "Quantum state discrimination using noisy quantum neural networks", Physical Review Research 3 1, 013063 (2021).

[35] Nicholas H. Stair, Renke Huang, and Francesco A. Evangelista, "A Multireference Quantum Krylov Algorithm for Strongly Correlated Electrons", arXiv:1911.05163, (2019).

[36] Lihui Lv, Bao Yan, Hong Wang, Zhi Ma, Yangyang Fei, Xiangdong Meng, and Qianheng Duan, "Using Variational Quantum Algorithm to Solve the LWE Problem", Entropy 24 10, 1428 (2022).

[37] Yunlong Yu, Chenfeng Cao, Xiang-Bin Wang, Nic Shannon, and Robert Joynt, "Solution of SAT problems with the adaptive-bias quantum approximate optimization algorithm", Physical Review Research 5 2, 023147 (2023).

[38] Elias X. Huber, Benjamin Y. L. Tan, Paul R. Griffin, and Dimitris G. Angelakis, "Exponential Qubit Reduction in Optimization for Financial Transaction Settlement", arXiv:2307.07193, (2023).

[39] D. V. Babukhin and W. V. Pogosov, "The effect of quantum noise on algorithmic perfect quantum state transfer on NISQ processors", Quantum Information Processing 21 1, 7 (2022).

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

[41] Ruslan Shaydulin and Yuri Alexeev, "Evaluating Quantum Approximate Optimization Algorithm: A Case Study", arXiv:1910.04881, (2019).

[42] Xavier Vasques, "A new step for computing", arXiv:2108.03997, (2021).

[43] Zhaolong Huang, Qiting Li, Junling Zhao, and Meimei Song, "Variational Quantum Algorithm Applied to Collision Avoidance of Unmanned Aerial Vehicles", Entropy 24 11, 1685 (2022).

[44] Xavier Vasques, "The data center of tomorrow is made up of heterogeneous accelerators", arXiv:2003.10950, (2020).

The above citations are from SAO/NASA ADS (last updated successfully 2023-10-01 03:20:32). 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-10-01 03:20:27: Encountered the unhandled forward link type postedcontent_cite while looking for citations to DOI 10.22331/q-2020-04-20-256.

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.