Căutare adaptativă Grover pentru optimizarea binară polinomială constrânsă

Marca temporală: 8 aprilie 2021 10:04
Nodul sursă: 806213

Austin Gilliam1, Stefan Woerner2, și Constantin Gonciulea1

1JPMorgan Chase
2IBM Quantum, IBM Research – Zurich

Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.

Abstract

În această lucrare discutăm problemele Grover Adaptive Search (GAS) pentru problemele de optimizare binară polinomială constrânsă (CPBO) și, în special, problemele de optimizare binară neconstrânsă quadratică (QUBO), ca un caz special. GAS poate oferi o accelerare pătratică pentru problemele de optimizare combinatorie în comparație cu căutarea cu forță brută. Totuși, acest lucru necesită dezvoltarea unor oracole eficiente care să reprezinte probleme și state de pavilion care îndeplinesc anumite criterii de căutare. În general, acest lucru poate fi realizat utilizând aritmetica cuantică, cu toate acestea, acest lucru este costisitor în ceea ce privește porțile Toffoli, precum și qubiții auxiliari necesari, care pot fi prohibitivi în termen scurt. În cadrul acestei lucrări, dezvoltăm o modalitate de a construi oracole eficiente pentru a rezolva problemele CPBO folosind algoritmi GAS. Demonstrăm această abordare și potențiala accelerare a problemei de optimizare a portofoliului, adică un QUBO, folosind rezultate de simulare și experimentale obținute pe hardware cuantic real. Cu toate acestea, abordarea noastră se aplică funcțiilor obiective polinomiale de grad superior, precum și problemelor de optimizare constrânsă.

Imagine prezentată: Probabilitățile de ieșire ale GAS pentru două iterații rulează pe hardware cuantic real, cu aplicațiile respective $y$ și $r$ ale operatorului Grover. Rezultatele de măsurare valide sunt afișate cu albastru, în timp ce rezultatele de măsurare nevalide sunt afișate cu gri.

Rezumat popular

În această lucrare discutăm problemele Grover Adaptive Search (GAS) pentru problemele de optimizare binară polinomială constrânsă (CPBO) și, în special, problemele de optimizare binară neconstrânsă quadratică (QUBO), ca un caz special. GAS poate oferi o accelerare pătratică pentru problemele de optimizare combinatorie în comparație cu căutarea cu forță brută. Totuși, acest lucru necesită dezvoltarea unor oracole eficiente care să reprezinte probleme și state de pavilion care îndeplinesc anumite criterii de căutare. În general, acest lucru poate fi realizat utilizând aritmetica cuantică, cu toate acestea, acest lucru este costisitor în ceea ce privește porțile Toffoli, precum și qubiții auxiliari necesari, care pot fi prohibitivi în termen scurt. În cadrul acestei lucrări, dezvoltăm o modalitate de a construi oracole eficiente pentru a rezolva problemele CPBO folosind algoritmi GAS. Demonstrăm această abordare și potențiala accelerare a problemei de optimizare a portofoliului, adică un QUBO, folosind rezultate de simulare și experimentale obținute pe hardware cuantic real. Cu toate acestea, abordarea noastră se aplică funcțiilor obiective polinomiale de grad superior, precum și problemelor de optimizare constrânsă.

► Date BibTeX

► Referințe

[1] Lov K. Grover. Un algoritm mecanic cuantic rapid pentru căutarea în baze de date. În Proceedings of the Twenty-96th Annual ACM Symposium on Theory of Computing, STOC '212, paginile 219–1996, New York, NY, SUA, 0. ACM. ISBN 89791-785-5-10.1145. 237814.237866/​XNUMX.
https: / / doi.org/ 10.1145 / 237814.237866

[2] Peter W. Shor. Algoritmi în timp polinomial pentru factorizarea prime și logaritmi discreti pe un computer cuantic. SIAM Journal on Computing, 26 (5): 1484–1509, oct 1997. ISSN 1095-7111. 10.1137/​s0097539795293172.
https: / / doi.org/ 10.1137 / s0097539795293172

[3] BP Lanyon, JD Whitfield, GG Gillett, ME Goggin, MP Almeida, I. Kassal, JD Biamonte, M. Mohseni, BJ Powell, M. Barbieri și colab. Către chimia cuantică pe un computer cuantic. Nature Chemistry, 2 (2): 106–111, ianuarie 2010. ISSN 1755-4349. 10.1038/​nchem.483.
https://​/​doi.org/​10.1038/​nchem.483

[4] Aram W. Harrow, Avinatan Hassidim și Seth Lloyd. Algoritm cuantic pentru sisteme liniare de ecuații. Physical Review Letters, 103 (15), oct 2009. ISSN 1079-7114. 10.1103/​physrevlett.103.150502.
https: / / doi.org/ 10.1103 / physrevlett.103.150502

[5] Carlos Bravo-Prieto, Ryan LaRose, M. Cerezo, Yigit Subasi, Lukasz Cicio și Patrick J. Coles. Rezolvator liniar cuantic variațional, 2020. URL https://​/​arxiv.org/​abs/​1909.05820.
arXiv: 1909.05820

[6] Patrick Rebentrost, Brajesh Gupt și Thomas R. Bromley. Finanțare computațională cuantică: prețul Monte Carlo a instrumentelor financiare derivate. Fiz. Rev. A, 98: 022321, august 2018. 10.1103/​PhysRevA.98.022321.
https: / / doi.org/ 10.1103 / PhysRevA.98.022321

[7] Stefan Woerner și Daniel J. Egger. Analiza riscului cuantic. npj Quantum Information, 5: 15, 2019. 10.1038/​s41534-019-0130-6.
https:/​/​doi.org/​10.1038/​s41534-019-0130-6

[8] DJ Egger, R. Garcia Gutierrez, J. Cahue Mestre și S. Woerner. Analiza riscului de credit folosind calculatoare cuantice. Tranzacții IEEE pe computere, paginile 1–1, 2020. 10.1109/​TC.2020.3038063.
https: / / doi.org/ 10.1109 / TC.2020.3038063

[9] Nikitas Stamatopoulos, Daniel J. Egger, Yue Sun, Christa Zoufal, Raban Iten, Ning Shen și Stefan Woerner. Tarifarea opțiunilor folosind calculatoare cuantice. Quantum, 4: 291, iulie 2020. ISSN 2521-327X. 10.22331/​q-2020-07-06-291.
https:/​/​doi.org/​10.22331/​q-2020-07-06-291

[10] Edward Farhi, Jeffrey Goldstone și Sam Gutmann. A Quantum Approximate Optimization Algorithm, 2014. URL https:/​/​arxiv.org/​abs/​1411.4028.
arXiv: 1411.4028

[11] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man Hong Yung, Xiao Qi Zhou, Peter J. Love, Alán Aspuru-Guzik și Jeremy L. O'Brien. Un rezolvator de valori proprii variaționale pe un procesor cuantic fotonic. Nature Communications, 5: 4213, 2014. ISSN 20411723. 10.1038/​ncomms5213.
https: / / doi.org/ 10.1038 / ncomms5213

[12] Giacomo Nannicini. Performanța euristicii variaționale hibride cuantice-clasice pentru optimizarea combinatorie. Physical Review E, 99: 013304, ianuarie 2019. 10.1103/​PhysRevE.99.013304.
https: / / doi.org/ 10.1103 / PhysRevE.99.013304

[13] Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli și Stefan Woerner. Îmbunătățirea optimizării cuantice variaționale folosind cvar. Quantum, 4: 256, apr 2020. ISSN 2521-327X. 10.22331/​q-2020-04-20-256.
https:/​/​doi.org/​10.22331/​q-2020-04-20-256

[14] L. Braine, DJ Egger, J. Glick și S. Woerner. Algoritmi cuantici pentru optimizarea binară mixtă aplicați decontării tranzacțiilor. IEEE Transactions on Quantum Engineering, 2: 1–8, 2021. 10.1109/​TQE.2021.3063635.
https: / / doi.org/ 10.1109 / TQE.2021.3063635

[15] Andrew M Childs, Edward Farhi și John Preskill. Robustețea calculului cuantic adiabatic. Physical Review A, 65 (1): 012322, 2001. 10.1103/​PhysRevA.65.012322.
https: / / doi.org/ 10.1103 / PhysRevA.65.012322

[16] Mark W Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, Richard Harris, Andrew J Berkley, Jan Johansson, Paul Bunyk și colab. Recoacere cuantică cu spinuri fabricate. Nature, 473 (7346): 194–198, 2011. 10.1038/​nature10012.
https: / / doi.org/ 10.1038 / nature10012

[17] Christoph Dürr și Peter Høyer. Un algoritm cuantic pentru găsirea minimului, 1996. URL https://​/​arxiv.org/​abs/​quant-ph/​9607014.
arXiv: Quant-ph / 9607014

[18] D. Bulger, WP Baritompa și GR Wood. Implementarea căutării pur adaptive cu algoritmul cuantic Grover. Journal of Optimization Theory and Applications, 116 (3): 517–529, martie 2003. ISSN 1573-2878. 10.1023/​A:1023061218864.
https: / / doi.org/ 10.1023 / A: 1023061218864

[19] WP Baritompa, DW Bulger și GR Wood. Algoritmul cuantic al lui Grover aplicat optimizării globale. SIAM J. on Optimization, 15 (4): 1170–1184, aprilie 2005. ISSN 1052-6234. 10.1137/​040605072.
https: / / doi.org/ 10.1137 / 040605072

[20] Austin Gilliam, Charlene Venci, Sreraman Muralidharan, Vitaliy Dorum, Eric May, Rajesh Narasimhan și Constantin Gonciulea. Modele fundamentale pentru calcularea cuantică eficientă, 2019. URL https://​/​arxiv.org/​abs/​1907.11513.
arXiv: 1907.11513

[21] Thomas G. Draper. Adăugare pe un computer cuantic, 2000. URL https:/​/​arxiv.org/​abs/​quant-ph/​0008033.
arXiv: Quant-ph / 0008033

[22] Román Orús, Samuel Mugel și Enrique Lizaso. Calcularea cuantică pentru finanțe: prezentare generală și perspective. Reviews in Physics, 4: 100028, noiembrie 2019. ISSN 2405-4283. 10.1016/​j.revip.2019.100028.
https: / / doi.org/ 10.1016 / j.revip.2019.100028

[23] Daniel J. Egger, Claudio Gambella, Jakub Marecek, Scott McFaddin, Martin Mevissen, Rudy Raymond, Andrea Simonetto, Stefan Woerner și Elena Yndurain. Calcularea cuantică pentru finanțe: stadiul tehnicii și perspective de viitor. IEEE Transactions on Quantum Engineering, 1: 1–24, 2020a. ISSN 2689-1808. 10.1109/​tqe.2020.3030314.
https://​/​doi.org/​10.1109/​tqe.2020.3030314

[24] Patrick Rebentrost și Seth Lloyd. Finanțare computațională cuantică: algoritm cuantic pentru optimizarea portofoliului, 2018. URL https://​/​arxiv.org/​abs/​1811.03975.
arXiv: 1811.03975

[25] Davide Venturelli și Alexei Kondratyev. Abordarea de recoacere cuantică inversă a problemelor de optimizare a portofoliului. Quantum Machine Intelligence, 1, 2019. 10.1007/​s42484-019-00001-w.
https: / / doi.org/ 10.1007 / s42484-019-00001-w

[26] Daniel J. Egger, Jakub Marecek și Stefan Woerner. Optimizare cuantică cu pornire caldă, 2020b. URL https://​/​arxiv.org/​abs/​2009.10095.
arXiv: 2009.10095

[27] Héctor Abraham et. al. Qiskit: Un cadru open-source pentru calculul cuantic. 2019. 10.5281/​zenodo.2562110.
https: / / doi.org/ 10.5281 / zenodo.2562110

[28] Michele Mosca. Căutare cuantică, numărare și amplificare a amplitudinii prin analiza vectorului propriu. În Proceedings of Randomized Algorithms, Workshop of Mathematical Foundations of Computer Science, paginile 90–100, 1998. URL https:/​/​eccc.weizmann.ac.il/​/​resources/​pdf/​moscafi.pdf.
https:/​/​eccc.weizmann.ac.il/​/​resources/​pdf/​moscafi.pdf

[29] Gilles Brassard, Peter Hoyer, Michele Mosca și Alain Tapp. Amplificarea și estimarea amplitudinii cuantice. Matematică Contemporană, 305, 2002. 10.1090/​conm/​305.
https: / / doi.org/ 10.1090 / conm / 305

[30] Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tomoki Tanaka, Tamiya Onodera și Naoki Yamamoto. Estimarea amplitudinii fără estimarea fazei. Quantum Information Processing, 19 (2), ianuarie 2020. ISSN 1573-1332. 10.1007/​s11128-019-2565-2.
https:/​/​doi.org/​10.1007/​s11128-019-2565-2

[31] Scott Aaronson și Patrick Rall. Numărarea aproximativă cuantică, simplificată. Simpozion privind simplitatea în algoritmi, paginile 24–32, ianuarie 2020. 10.1137/​1.9781611976014.5.
https: / / doi.org/ 10.1137 / 1.9781611976014.5

[32] Michel Boyer, Gilles Brassard, Peter Høyer și Alain Tapp. Limite strânse în căutarea cuantică. Fortschritte der Physik, 46 (4-5): 493–505, iunie 1998. ISSN 1521-3978. 10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P.
[33] Benjamín Barán și Marcos Villagra. Optimizare multiobiectivă Grover Adaptive Search, paginile 191–211. Springer International Publishing, Cham, 2019. ISBN 978-3-319-99648-6. 10.1007/​978-3-319-99648-6_11.
https:/​/​doi.org/​10.1007/​978-3-319-99648-6_11

[34] Yunseong Nam, Yuan Su și Dmitri Maslov. Transformată Fourier cuantică aproximativă cu o(n log(n)) t porți. npj Quantum Information, 6 (1), martie 2020. ISSN 2056-6387. 10.1038/​s41534-020-0257-5.
https:/​/​doi.org/​10.1038/​s41534-020-0257-5

[35] Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin și David Petrie Moulton. Un nou circuit de adiție cu ondulație cuantică, 2004. URL https://​/​arxiv.org/​abs/​quant-ph/​0410184.
arXiv: Quant-ph / 0410184

[36] Thomas G. Draper, Samuel A. Kutin, Eric M. Rains și Krysta M. Svore. Un sumător cuantic cuantic cu profunzime logaritmică. Informații cuantice. Comput., 6 (4): 351–369, iulie 2006. ISSN 1533-7146. 10.26421/​QIC6.4-5-4.
https: / / doi.org/ 10.26421 / QIC6.4-5-4

[37] Craig Gidney. Reducerea la jumătate a costului adăugării cuantice. Quantum, 2: 74, iunie 2018. ISSN 2521-327X. 10.22331/​q-2018-06-18-74.
https:/​/​doi.org/​10.22331/​q-2018-06-18-74

[38] Andrew W. Cross, Lev S. Bishop, Sarah Sheldon, Paul D. Nation și Jay M. Gambetta. Validarea calculatoarelor cuantice folosind circuite model randomizate. Physical Review A, 100 (3), septembrie 2019. ISSN 2469-9934. 10.1103/​physreva.100.032328.
https: / / doi.org/ 10.1103 / physreva.100.032328

[39] A. Dewes, FR Ong, V. Schmitt, R. Lauro, N. Boulant, P. Bertet, D. Vion și D. Esteve. Caracterizarea unui procesor cu două transmisii cu citire individuală a qubitului single-shot. Fiz. Rev. Lett., 108: 057002, februarie 2012. 10.1103/​PhysRevLett.108.057002.
https: / / doi.org/ 10.1103 / PhysRevLett.108.057002

[40] Svante Janson. Momente de tip gamma și zona de proces brownian supremum. Probabil. Surveys, 7: 1–52, 2010. 10.1214/​10-PS160.
https://​/​doi.org/​10.1214/​10-PS160

[41] Michael A. Nielsen și Isaac L. Chuang. Calcul cuantic și informații cuantice: ediția a 10-a aniversare. Cambridge University Press, New York, NY, SUA, ediția a 10-a, 2011. ISBN 1107002176, 9781107002173. 10.1017/​CBO9780511976667.
https: / / doi.org/ 10.1017 / CBO9780511976667

Citat de

[1] Daniel J. Egger, Claudio Gambella, Jakub Marecek, Scott McFaddin, Martin Mevissen, Rudy Raymond, Andrea Simonetto, Stefan Woerner și Elena Yndurain, „Quantum Computing for Finance: State of the Art and Future Prospects”, arXiv: 2006.14510.

[2] Claudio Gambella și Andrea Simonetto, „Multi-block ADMM Euristics for Mixed-Binary Optimization on Classical and Quantum Computers”, arXiv: 2001.02069.

[3] Austin Gilliam, Marco Pistoia și Constantin Gonciulea, „Optimizing Quantum Search Using a Generalized Version of Grover's Algorithm”, arXiv: 2005.06468.

[4] Austin Gilliam, Marco Pistoia și Constantin Gonciulea, „Construcția canonică a oracolelor cuantice”, arXiv: 2006.10656.

[5] Austin Gilliam, Marco Pistoia și Constantin Gonciulea, „Optimizing Quantum Search with a Binomial Version of Grover's Algorithm”, arXiv: 2007.10894.

[6] Julien Gacon, Christa Zoufal, Giuseppe Carleo și Stefan Woerner, „Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information”, arXiv: 2103.09232.

[7] Sayantan Pramanik, M Girish Chandra, Shampa Sarkar și Manoj Nambiar, „Aproximate Phase Search and Eigen Estimation using Modified Grover's Algorithm”, arXiv: 2012.11497.

[8] Su Yeon Chang, Steven Herbert, Sofia Vallecorsa, Elías F. Combarro și Ross Duncan, „Dual-Parameterized Quantum Circuit GAN Model in High Energy Physics”, arXiv: 2103.15470.

[9] Marika Svensson, Martin Andersson, Mattias Grönkvist, Pontus Vikstål, Devdatt Dubhashi, Giulia Ferrini și Göran Johansson, „A Euristic Method to solve large-scale Integer Linear Programs by combining Branch-and-Price with a Quantum Algorithm”, arXiv: 2103.15433.

[10] Yidong Liao, Min-Hsiu Hsieh și Chris Ferrie, „Optimizarea cuantică pentru formarea rețelelor neuronale cuantice”, arXiv: 2103.17047.

Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2021-04-10 02:42:05). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.

On Serviciul citat de Crossref nu s-au găsit date despre citarea lucrărilor (ultima încercare 2021-04-10 02:42:03).

Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.

Sursa: https://quantum-journal.org/papers/q-2021-04-08-428/

Timestamp-ul:

Mai mult de la Jurnalul cuantic