1IBM Research - Zurych
2Centrum badawcze IBM TJ Watson
3École Normale Supérieure, PSL University, Paryż
Czy ten artykuł jest interesujący czy chcesz dyskutować? Napisz lub zostaw komentarz do SciRate.
Abstrakcyjny
Hybrydowe kwantowe / klasyczne algorytmy wariacyjne można zaimplementować na hałaśliwych komputerach kwantowych o średniej skali i można je wykorzystać do znalezienia rozwiązań problemów optymalizacji kombinatorycznej. Podejścia omówione w literaturze minimalizują oczekiwanie problemu hamiltonianu dla sparametryzowanego próbnego stanu kwantowego. Oczekiwanie szacuje się jako średnią z próby zbioru wyników pomiarów, podczas gdy parametry stanu próbnego są optymalizowane klasycznie. Ta procedura jest w pełni uzasadniona w przypadku obserwacji mechaniki kwantowej, takich jak energie molekularne. W przypadku klasycznych problemów optymalizacyjnych, które dają hamiltoniany diagonalne, argumentujemy, że agregowanie próbek w inny sposób niż oczekiwana wartość jest bardziej naturalne. W tym artykule proponujemy warunkową wartość zagrożoną jako funkcję agregacji. Empirycznie pokazujemy - używając klasycznej symulacji, a także sprzętu kwantowego - że prowadzi to do szybszej konwergencji do lepszych rozwiązań dla wszystkich problemów optymalizacji kombinatorycznej testowanych w naszym badaniu. Przedstawiamy również wyniki analityczne, aby wyjaśnić zaobserwowaną różnicę w wydajności między różnymi algorytmami wariacyjnymi.
► Dane BibTeX
► Referencje
[1] Karen Aardal, Robert E Bixby, Cor AJ Hurkens, Arjen K Lenstra i Job W Smeltink. Podział rynku i redukcja podstaw: w kierunku rozwiązania przypadków cornuéjols-dawande. 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. Biskup, 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, Chrześcijański Mikołaj, Chrześcijański Mikołaj, Abigail J. Krzyż, Andrew W. Krzyż, 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 Eastebman, Piech , 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 Itenoko, Toshinari 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 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 , 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, Anna Phan, 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, Diego M. Rodríguez, RohithKarur, Max Rossmannek, Mingi Ryu, Tharrmashastha SAPV, SamFerracin, Martin Sandberg, Hayk Sarkisyan, 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. Śpiewane, 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 Varchena, Almudis Varchena Carrera Vazquez, Desiree Vogt-Lee, Christophe Vuillot, James Weaver, Rafal Wieczorek, Jonathan A. Wildstroma, Roberta Wille’a, Ericka Winstona, Jacka 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, matsuo, azulehner, bamoramorrison, brandhsn, chlorophyll zz, dan1pal, dime10ocampead. , enavarro51, faisaldebouni, fanizzamarco, gadial, gruu, kanejess, klinvill, kurarrr, lerongil, ma5x, merav aharoni, michelle4654, ordmoj, sethmerkel, strickroman, sumitpuri, tigerjack, toural, vvilanghang.it i yotamvakninibm. Qiskit: środowisko open source do obliczeń kwantowych, 2019.
https: / / qiskit.org
[3] Carlo Acerbi i Dirk Tasche. Spójność spodziewanego niedoboru. 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. O złożoności obliczeniowej modeli spin-szkło. 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 i Umesh Vazirani. Teoria złożoności kwantowej. SIAM Journal on Computing, 26 (5): 1411–1473, 1997. 10.1137 / S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921
[6] Gavin E. Crooks. Wydajność kwantowego algorytmu optymalizacji przybliżonej problemu maksymalnego cięcia. prefiks arXiv arXiv: 1811.08419, 2018. URL https: / / arxiv.org/ abs / 1811.08419.
arXiv: 1811.08419
[7] Edward Farhi, Jeffrey Goldstone i Sam Gutmann. Algorytm optymalizacji przybliżonej kwantowej. nadruk arXiv arXiv: 1411.4028, strony 1–16, 2014a. Adres URL http: / / arxiv.org/ abs / 1411.4028.
arXiv: 1411.4028
[8] Edward Farhi, Jeffrey Goldstone i Sam Gutmann. Algorytm optymalizacji przybliżonej kwantowej zastosowany do problemu ograniczenia związanego z występowaniem. nadruk arXiv arXiv: 1412.6062, 2014b. Adres URL http: / / arxiv.org/ abs / 1412.6062.
arXiv: 1412.6062
[9] Edward Farhi, Jeffrey Goldstone, Sam Gutmann i Hartmut Neven. Algorytmy kwantowe dla stałych architektur kubitowych. prefiks arXiv arXiv: 1703.06199, 2017. URL https: / / arxiv.org/ abs / 1703.06199.
arXiv: 1703.06199
[10] E. Schuyler Fried, Nicolas PD Sawaya, Yudong Cao, Ian D. Kivlichan, Jhonathan Romero i Alán Aspuru-Guzik. q Torch: Kwantowy program do obsługi skurczów. 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. Mechanika kwantowa pomaga w poszukiwaniu igły w stogu siana. Listy z przeglądu fizycznego, 79 (2): 325, 1997. 10.1103 / PhysRevLett.79.325.
https: / / doi.org/ 10.1103 / PhysRevLett.79.325
[12] Matthew B Hastings. Klasyczne i kwantowe algorytmy aproksymacji głębokości. nadruk arXiv arXiv: 1905.07047, 2019. URL https: / / arxiv.org/ abs / 1905.07047.
arXiv: 1905.07047
[13] Jeff L. Hong. Szacowanie Monte Carlo wartości zagrożonej, warunkowej wartości zagrożonej i ich wrażliwości. W materiałach konferencji Winter Simulation Conference 2011, strony 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 i Jay M. Gambetta. Wydajny sprzętowo wariacyjny eigensolver kwantowy dla małych cząsteczek i magnesów kwantowych. Nature, 549 (7671): 242, 2017. 10.1038 / nature23879.
https: / / doi.org/ 10.1038 / nature23879
[15] Andrew Lucas. Formułowanie wielu problemów np. 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 i Kristan Temme. Optymalizacja kwantowa z wykorzystaniem algorytmów wariacyjnych na krótkoterminowych urządzeniach kwantowych. Quantum Science and Technology, 3 (3): 030503, 2018. 10.1088 / 2058-9565 / aab822.
https: / / doi.org/ 10.1088 / 2058-9565 / aab822
[17] Giacomo Nannicini. Wydajność hybrydowej kwantowo-klasycznej heurystyki wariacyjnej do optymalizacji kombinatorycznej. Physical Review E, 99: 013304, Jan 2019. 10.1103 / PhysRevE.99.013304.
https: / / doi.org/ 10.1103 / PhysRevE.99.013304
[18] GL Nemhauser i LA Wolsey. Optymalizacja liczb całkowitych i kombinatorycznych. Wiley, New York, 1988. 10.1002 / 9781118627372.
https: / / doi.org/ 10.1002 / 9781118627372
[19] Murphy Yuezhen Niu, Sirui Lu i Isaac L. Chuang. Optymalizacja qaoa: prawdopodobieństwo sukcesu i zależność czasu wykonywania od głębokości obwodu. prefiks arXiv 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 i Jeremy L. O'Brien. Wariacyjny solwer wartości własnej na fotonicznym procesorze kwantowym. Nature Communications, 5, 2014. 10.1038 / ncomms5213.
https: / / doi.org/ 10.1038 / ncomms5213
Cytowany przez
[1] Li Li, Minjie Fan, Marc Coram, Patrick Riley i Stefan Leichenauer, „Optymalizacja kwantowa z nowatorską funkcją celu Gibbsa i wyszukiwaniem architektury ansatz”, Badania fizyczne Review 2 2, 023074 (2020).
[2] Nicholas H. Stair, Renke Huang i Francesco A. Evangelista, „Multireference Quantum Krylov Algorithm for Strongly Correlated Electrons”, arXiv: 1911.05163.
[3] Anton Robert, Panagiotis Kl. Barkoutsos, Stefan Woerner i Ivano Tavernelli, „Resource-Efficient Quantum Algorithm for Protein Folding”, arXiv: 1908.02163.
[4] Lee Braine, Daniel J. Egger, Jennifer Glick i Stefan Woerner, „Quantum Algorithms for Mixed Binary Optimization Applied to Transaction Settlement”, arXiv: 1910.05788.
[5] Sami Khairy, Ruslan Shaydulin, Łukasz Cincio, Yuri Alexeev i Prasanna Balaprakash, „Reinforcement-Learning-Based Variational Quantum Circuits Optimization for Combinatorial Problems”, arXiv: 1911.04574.
[6] Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev i Prasanna Balaprakash, „Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems”, arXiv: 1911.11071.
[7] Ruslan Shaydulin i 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 i Sophia E. Economou, „Preserving Symmetries for Variational Quantum Eigensolvers in the Presence of Noise”, arXiv: 2003.00171.
[9] Austin Gilliam, Stefan Woerner i Constantin Gonciulea, „Grover Adaptive Search for Constrained Polynomial Binary Optimization”, arXiv: 1912.04088.
[10] Claudio Gambella i Andrea Simonetto, „Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers”, arXiv: 2001.02069.
[11] Xavier Vasques, „Centrum danych jutra składa się z heterogenicznych akceleratorów”, arXiv: 2003.10950.
[12] David Headley, Thorge Müller, Ana Martin, Enrique Solano, Mikel Sanz i Frank K. Wilhelm, „Approximating the Quantum Approximate Optimization Algorithm”, arXiv: 2002.12215.
[13] Loïc Henriet, „Odporność na spontaniczną emisję wariacyjnego algorytmu kwantowego”, Przegląd fizyczny A 101 1, 012335 (2020).
[14] Hiroshi Yano, Yudai Suzuki, Rudy Raymond i Naoki Yamamoto, „Efficient Discrete Feature Encoding for Variational Quantum Classifier”, arXiv: 2005.14382.
[15] Charles Moussa, Henri Calandra i Vedran Dunjko, „To quantum or not to quantum: w kierunku wyboru algorytmu w krótkoterminowej optymalizacji kwantowej”, arXiv: 2001.08271.
[16] Linghua Zhu, Ho Lun Tang, George S. Barron, Nicholas J. Mayhall, Edwin Barnes i Sophia E. Economou, „Adaptacyjny kwantowy algorytm przybliżonej optymalizacji do rozwiązywania problemów kombinatorycznych na komputerze kwantowym”, arXiv: 2005.10258.
Powyższe cytaty pochodzą z Serwis cytowany przez Crossref (ostatnia aktualizacja pomyślnie 2020-06-03 20:00:53) i Reklamy SAO / NASA (ostatnia aktualizacja pomyślnie 2020-06-03 20:00:54). Lista może być niekompletna, ponieważ nie wszyscy wydawcy podają odpowiednie i pełne dane cytowania.
Niniejszy artykuł opublikowano w Quantum pod Creative Commons Uznanie autorstwa 4.0 Międzynarodowe (CC BY 4.0) licencja. Prawa autorskie należą do pierwotnych właścicieli praw autorskich, takich jak autorzy lub ich instytucje.
Źródło: https://quantum-journal.org/papers/q-2020-04-20-256/
