1IBM Research – Zurich
2IBM T.J. Watson Research Center
3École Normale Supérieure, PSL University, Paris
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
► 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] Li Li, Minjie Fan, Marc Coram, Patrick Riley, and Stefan Leichenauer, “Quantum optimization with a novel Gibbs objective function and ansatz architecture search”, Physical Review Research 2 2, 023074 (2020).
[2] Nicholas H. Stair, Renke Huang, and Francesco A. Evangelista, “A Multireference Quantum Krylov Algorithm for Strongly Correlated Electrons”, arXiv:1911.05163.
[3] Anton Robert, Panagiotis Kl. Barkoutsos, Stefan Woerner, and Ivano Tavernelli, “Resource-Efficient Quantum Algorithm for Protein Folding”, arXiv:1908.02163.
[4] Lee Braine, Daniel J. Egger, Jennifer Glick, and Stefan Woerner, “Quantum Algorithms for Mixed Binary Optimization applied to Transaction Settlement”, arXiv:1910.05788.
[5] Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev, and Prasanna Balaprakash, “Reinforcement-Learning-Based Variational Quantum Circuits Optimization for Combinatorial Problems”, arXiv:1911.04574.
[6] Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev, and Prasanna Balaprakash, “Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems”, arXiv:1911.11071.
[7] Ruslan Shaydulin and Yuri Alexeev, “Evaluating Quantum Approximate Optimization Algorithm: A Case Study”, arXiv:1910.04881.
[8] 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”, arXiv:2003.00171.
[9] Austin Gilliam, Stefan Woerner, and Constantin Gonciulea, “Grover Adaptive Search for Constrained Polynomial Binary Optimization”, arXiv:1912.04088.
[10] Claudio Gambella and Andrea Simonetto, “Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers”, arXiv:2001.02069.
[11] Xavier Vasques, “The data center of tomorrow is made up of heterogeneous accelerators”, arXiv:2003.10950.
[12] David Headley, Thorge Müller, Ana Martin, Enrique Solano, Mikel Sanz, and Frank K. Wilhelm, “Approximating the Quantum Approximate Optimisation Algorithm”, arXiv:2002.12215.
[13] Loïc Henriet, “Robustness to spontaneous emission of a variational quantum algorithm”, Physical Review A 101 1, 012335 (2020).
[14] Hiroshi Yano, Yudai Suzuki, Rudy Raymond, and Naoki Yamamoto, “Efficient Discrete Feature Encoding for Variational Quantum Classifier”, arXiv:2005.14382.
[15] Charles Moussa, Henri Calandra, and Vedran Dunjko, “To quantum or not to quantum: towards algorithm selection in near-term quantum optimization”, arXiv:2001.08271.
[16] 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”, arXiv:2005.10258.
The above citations are from Crossref’s cited-by service (last updated successfully 2020-06-03 20:00:53) and SAO/NASA ADS (last updated successfully 2020-06-03 20:00:54). The list may be incomplete as not all publishers provide suitable and complete citation data.
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.
Source: https://quantum-journal.org/papers/q-2020-04-20-256/
