Ricerca adattiva di Grover per l'ottimizzazione binaria polinomiale vincolata

Timestamp: 8 aprile 2021 10:04
Nodo di origine: 806213

Austin Gilliam1, Stefan Wörner2e Costantino Gonciulea1

1JPMorgan Chase
2IBM Quantum, IBM Research - Zurigo

Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.

Astratto

In questo articolo discutiamo Grover Adaptive Search (GAS) per problemi di ottimizzazione binaria polinomiale vincolata (CPBO) e, in particolare, problemi di ottimizzazione binaria non vincolata quadratica (QUBO), come un caso speciale. GAS può fornire un'accelerazione quadratica per problemi di ottimizzazione combinatoria rispetto alla ricerca di forza bruta. Tuttavia, ciò richiede lo sviluppo di oracoli efficienti per rappresentare problemi e stati di bandiera che soddisfano determinati criteri di ricerca. In generale, ciò può essere ottenuto utilizzando l'aritmetica quantistica, tuttavia, questo è costoso in termini di porte di Toffoli e qubit ancilla richiesti, che possono essere proibitivi a breve termine. All'interno di questo lavoro, sviluppiamo un modo per costruire oracoli efficienti per risolvere problemi CPBO utilizzando algoritmi GAS. Dimostriamo questo approccio e la potenziale accelerazione per il problema di ottimizzazione del portafoglio, cioè un QUBO, utilizzando simulazioni e risultati sperimentali ottenuti su hardware quantistico reale. Tuttavia, il nostro approccio si applica alle funzioni obiettivo polinomiale di grado più elevato e ai problemi di ottimizzazione vincolata.

Immagine in primo piano: le probabilità di output di GAS per due iterazioni vengono eseguite su hardware quantistico reale, con le rispettive soglie $ y $ e $ r $ applicazioni dell'operatore di Grover. I risultati delle misurazioni valide sono mostrati in blu, mentre i risultati delle misurazioni non valide sono mostrati in grigio.

Riepilogo popolare

In questo articolo discutiamo Grover Adaptive Search (GAS) per problemi di ottimizzazione binaria polinomiale vincolata (CPBO) e, in particolare, problemi di ottimizzazione binaria non vincolata quadratica (QUBO), come un caso speciale. GAS può fornire un'accelerazione quadratica per problemi di ottimizzazione combinatoria rispetto alla ricerca di forza bruta. Tuttavia, ciò richiede lo sviluppo di oracoli efficienti per rappresentare problemi e stati di bandiera che soddisfano determinati criteri di ricerca. In generale, ciò può essere ottenuto utilizzando l'aritmetica quantistica, tuttavia, questo è costoso in termini di porte di Toffoli e qubit ancilla richiesti, che possono essere proibitivi a breve termine. All'interno di questo lavoro, sviluppiamo un modo per costruire oracoli efficienti per risolvere problemi CPBO utilizzando algoritmi GAS. Dimostriamo questo approccio e la potenziale accelerazione per il problema di ottimizzazione del portafoglio, cioè un QUBO, utilizzando simulazioni e risultati sperimentali ottenuti su hardware quantistico reale. Tuttavia, il nostro approccio si applica alle funzioni obiettivo polinomiale di grado più elevato e ai problemi di ottimizzazione vincolata.

► dati BibTeX

► Riferimenti

, Lov K. Grover. Un algoritmo di meccanica quantistica veloce per la ricerca nel database. In Atti del ventottesimo Simposio annuale ACM sulla teoria dell'informatica, STOC '96, pagine 212–219, New York, NY, USA, 1996. ACM. ISBN 0-89791-785-5. 10.1145 / 237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866 mila

, Peter W. Shor. Algoritmi tempo-polinomiali per fattorizzazione in fattori primi e logaritmi discreti su computer quantistico. SIAM Journal on Computing, 26 (5): 1484–1509, ottobre 1997. ISSN 1095-7111. 10.1137 / s0097539795293172.
https: / / doi.org/ 10.1137 / s0097539795293172

, BP Lanyon, JD Whitfield, GG Gillett, ME Goggin, MP Almeida, I. Kassal, JD Biamonte, M. Mohseni, BJ Powell, M. Barbieri ed et al. Verso la chimica quantistica su un computer quantistico. Nature Chemistry, 2 (2): 106–111, gennaio 2010. ISSN 1755-4349. 10.1038 / nchem.483.
https: / / doi.org/ 10.1038 / nchem.483

, Aram W. Harrow, Avinatan Hassidim e Seth Lloyd. Algoritmo quantistico per sistemi lineari di equazioni. Physical Review Letters, 103 (15), ottobre 2009. ISSN 1079-7114. 10.1103 / physrevlett.103.150502.
https: / / doi.org/ 10.1103 / physrevlett.103.150502

, Carlos Bravo-Prieto, Ryan LaRose, M. Cerezo, Yigit Subasi, Lukasz Cincio e Patrick J. Coles. Risolutore lineare quantistico variazionale, 2020. URL https: / / arxiv.org/ abs / 1909.05820.
arXiv: 1909.05820

, Patrick Rebentrost, Brajesh Gupt e Thomas R. Bromley. Finanza computazionale quantistica: Monte carlo pricing dei derivati ​​finanziari. Phys. Rev. A, 98: 022321, agosto 2018. 10.1103 / PhysRevA.98.022321.
https: / / doi.org/ 10.1103 / PhysRevA.98.022321

, Stefan Woerner e Daniel J. Egger. Analisi quantistica del rischio. npj Quantum Information, 5:15, 2019. 10.1038 / s41534-019-0130-6.
https:/​/​doi.org/​10.1038/​s41534-019-0130-6

, DJ Egger, R. Garcia Gutierrez, J. Cahue Mestre e S. Woerner. Analisi del rischio di credito utilizzando computer quantistici. Transazioni IEEE sui computer, pagine 1–1, 2020. 10.1109 / TC.2020.3038063.
https: / / doi.org/ 10.1109 / TC.2020.3038063

, Nikitas Stamatopoulos, Daniel J. Egger, Yue Sun, Christa Zoufal, Raban Iten, Ning Shen e Stefan Woerner. Prezzi delle opzioni utilizzando computer quantistici. Quantum, 4: 291, luglio 2020. ISSN 2521-327X. 10.22331 / q-2020-07-06-291.
https:/​/​doi.org/​10.22331/​q-2020-07-06-291

, Edward Farhi, Jeffrey Goldstone e Sam Gutmann. A Quantum Approximate Optimization Algorithm, 2014. URL https: / / arxiv.org/ abs / 1411.4028.
arXiv: 1411.4028

, Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man Hong Yung, Xiao Qi Zhou, Peter J. Love, Alán Aspuru-Guzik e Jeremy L. O'Brien. Un solutore di autovalori variazionale su un processore quantistico fotonico. Nature Communications, 5: 4213, 2014. ISSN 20411723. 10.1038 / ncomms5213.
https: / / doi.org/ 10.1038 / ncomms5213

, Giacomo Nannicini. Prestazioni dell'euristica variazionale quantistica-classica ibrida per l'ottimizzazione combinatoria. Revisione fisica E, 99: 013304, gennaio 2019. 10.1103 / PhysRevE.99.013304.
https: / / doi.org/ 10.1103 / PhysRevE.99.013304

, Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli e Stefan Woerner. Migliorare l'ottimizzazione quantistica variazionale utilizzando cvar. Quantum, 4: 256, aprile 2020. ISSN 2521-327X. 10.22331 / q-2020-04-20-256.
https:/​/​doi.org/​10.22331/​q-2020-04-20-256

, L. Braine, DJ Egger, J. Glick e S. Woerner. Algoritmi quantistici per l'ottimizzazione binaria mista applicati al regolamento delle transazioni. Transazioni IEEE sull'ingegneria quantistica, 2: 1–8, 2021. 10.1109 / TQE.2021.3063635.
https: / / doi.org/ 10.1109 / TQE.2021.3063635

, Andrew M. Childs, Edward Farhi e John Preskill. Robustezza del calcolo quantistico adiabatico. Physical Review A, 65 (1): 012322, 2001. 10.1103 / PhysRevA.65.012322.
https: / / doi.org/ 10.1103 / PhysRevA.65.012322

, Mark W Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, Richard Harris, Andrew J Berkley, Jan Johansson, Paul Bunyk, et al. Ricottura quantistica con giri prodotti. Nature, 473 (7346): 194–198, 2011. 10.1038 / nature10012.
https: / / doi.org/ 10.1038 / nature10012

, Christoph Dürr e Peter Høyer. Un algoritmo quantistico per trovare il minimo, 1996. URL https: / / arxiv.org/ abs / quant-ph / 9607014.
arXiv: Quant-ph / 9607014

, D. Bulger, WP Baritompa e GR Wood. Implementazione della ricerca adattiva pura con l'algoritmo quantistico di Grover. Journal of Optimization Theory and Applications, 116 (3): 517–529, marzo 2003. ISSN 1573-2878. 10.1023 / A: 1023061218864.
https: / / doi.org/ 10.1023 / A: 1023061218864 millions

, WP Baritompa, DW Bulger e GR Wood. Algoritmo quantistico di Grover applicato all'ottimizzazione globale. SIAM J. on Optimization, 15 (4): 1170–1184, aprile 2005. ISSN 1052-6234. 10.1137 / 040605072.
https: / / doi.org/ 10.1137 / 040605072 mila

, Austin Gilliam, Charlene Venci, Sreraman Muralidharan, Vitaliy Dorum, Eric May, Rajesh Narasimhan e Constantin Gonciulea. Modelli fondamentali per un calcolo quantistico efficiente, 2019. URL https: / / arxiv.org/ abs / 1907.11513.
arXiv: 1907.11513

, Thomas G. Draper. Aggiunta su un computer quantistico, 2000. URL https: / / arxiv.org/ abs / quant-ph / 0008033.
arXiv: Quant-ph / 0008033

, Román Orús, Samuel Mugel e Enrique Lizaso. Quantum computing per la finanza: panoramica e prospettive. Recensioni in fisica, 4: 100028, novembre 2019. ISSN 2405-4283. 10.1016 / j.revip.2019.100028.
https: / / doi.org/ 10.1016 / j.revip.2019.100028

, Daniel J. Egger, Claudio Gambella, Jakub Marecek, Scott McFaddin, Martin Mevissen, Rudy Raymond, Andrea Simonetto, Stefan Woerner ed Elena Yndurain. Quantum computing per la finanza: stato dell'arte e prospettive future. Transazioni IEEE sull'ingegneria quantistica, 1: 1–24, 2020a. ISSN 2689-1808. 10.1109 / tqe.2020.3030314.
https: / / doi.org/ 10.1109 / tqe.2020.3030314

, Patrick Rebentrost e Seth Lloyd. Finanza computazionale quantistica: algoritmo quantistico per l'ottimizzazione del portafoglio, 2018. URL https: / / arxiv.org/ abs / 1811.03975.
arXiv: 1811.03975

, Davide Venturelli e Alexei Kondratyev. Approccio di ricottura quantistica inversa ai problemi di ottimizzazione del portafoglio. Quantum Machine Intelligence, 1, 2019. 10.1007 / s42484-019-00001-w.
https: / / doi.org/ 10.1007 / s42484-019-00001-w

, Daniel J. Egger, Jakub Marecek e Stefan Woerner. Ottimizzazione quantistica a caldo, 2020b. URL https: / / arxiv.org/ abs / 2009.10095.
arXiv: 2009.10095

, Héctor Abraham et. al. Qiskit: un framework open source per il calcolo quantistico. 2019. 10.5281 / zenodo.2562110.
https: / / doi.org/ 10.5281 / zenodo.2562110

, Michele Mosca. Ricerca quantistica, conteggio e amplificazione di ampiezza mediante analisi di autovettori. In Proceedings of Randomized Algorithms, Workshop of Mathematical Foundations of Computer Science, pagine 90–100, 1998. URL https: / / eccc.weizmann.ac.il/ / resources / pdf / moscafi.pdf.
https: / / eccc.weizmann.ac.il/ / resources / pdf / moscafi.pdf

, Gilles Brassard, Peter Hoyer, Michele Mosca e Alain Tapp. Amplificazione e stima quantistica dell'ampiezza. Contemporary Mathematics, 305, 2002. 10.1090 / conm / 305.
https: / / doi.org/ 10.1090 / conm / 305

, Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tomoki Tanaka, Tamiya Onodera e Naoki Yamamoto. Stima dell'ampiezza senza stima della fase. Quantum Information Processing, 19 (2), gennaio 2020. ISSN 1573-1332. 10.1007 / s11128-019-2565-2.
https:/​/​doi.org/​10.1007/​s11128-019-2565-2

, Scott Aaronson e Patrick Rall. Conteggio approssimativo quantistico, semplificato. Simposio sulla semplicità negli algoritmi, pagine 24–32, gennaio 2020. 10.1137 / 1.9781611976014.5.
https: / / doi.org/ 10.1137 / 1.9781611976014.5 mila

, Michel Boyer, Gilles Brassard, Peter Høyer e Alain Tapp. Limiti stretti nella ricerca quantistica. Fortschritte der Physik, 46 (4-5): 493–505, giugno 1998. ISSN 1521-3978. 10.1002 / (SICI) 1521-3978 (199806) 46: 4/5 <493 :: AID-PROP493> 3.0.CO; 2-P.
, Benjamín Barán e Marcos Villagra. Ottimizzazione multiobiettiva Grover Adaptive Search, pagine 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

, Yunseong Nam, Yuan Su e Dmitri Maslov. Trasformata di Fourier quantistica approssimativa con porte o (n log (n)) t. npj Quantum Information, 6 (1), marzo 2020. ISSN 2056-6387. 10.1038 / s41534-020-0257-5.
https:/​/​doi.org/​10.1038/​s41534-020-0257-5

, Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin e David Petrie Moulton. Un nuovo circuito di addizione quantum ripple carry, 2004. URL https: / / arxiv.org/ abs / quant-ph / 0410184.
arXiv: Quant-ph / 0410184

, Thomas G. Draper, Samuel A. Kutin, Eric M. Rains e Krysta M. Svore. Un sommatore quantico carry-lookahead di profondità logaritmica. Informazioni quantistiche. Comput., 6 (4): 351–369, luglio 2006. ISSN 1533-7146. 10.26421 / QIC6.4-5-4.
https: / / doi.org/ 10.26421 / QIC6.4-5-4

, Craig Gidney. Dimezzare il costo dell'addizione quantistica. Quantum, 2: 74, giugno 2018. ISSN 2521-327X. 10.22331 / q-2018-06-18-74.
https:/​/​doi.org/​10.22331/​q-2018-06-18-74

, Andrew W. Cross, Lev S. Bishop, Sarah Sheldon, Paul D. Nation e Jay M. Gambetta. Convalida di computer quantistici utilizzando circuiti modello randomizzati. Physical Review A, 100 (3), settembre 2019. ISSN 2469-9934. 10.1103 / physreva.100.032328.
https: / / doi.org/ 10.1103 / physreva.100.032328

, A. Dewes, FR Ong, V. Schmitt, R. Lauro, N. Boulant, P. Bertet, D. Vion e D. Esteve. Caratterizzazione di un processore a due transmon con lettura individuale dei qubit a colpo singolo. Phys. Rev. Lett., 108: 057002, febbraio 2012. 10.1103 / PhysRevLett.108.057002.
https: / / doi.org/ 10.1103 / PhysRevLett.108.057002

, Svante Janson. Momenti di tipo gamma e area del processo del supremo browniano. Probab. Sondaggi, 7: 1–52, 2010. 10.1214 / 10-PS160.
https: / / doi.org/ 10.1214 / 10-PS160

, Michael A. Nielsen e Isaac L. Chuang. Calcolo quantistico e informazione quantistica: edizione per il decimo anniversario. Cambridge University Press, New York, NY, USA, 10a edizione, 10. ISBN 2011, 1107002176. 9781107002173 / CBO10.1017.
https: / / doi.org/ 10.1017 / CBO9780511976667

Citato da

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

[2] Claudio Gambella e Andrea Simonetto, "Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers", arXiv: 2001.02069.

[3] Austin Gilliam, Marco Pistoia e Constantin Gonciulea, "Ottimizzazione della ricerca quantistica utilizzando una versione generalizzata dell'algoritmo di Grover", arXiv: 2005.06468.

[4] Austin Gilliam, Marco Pistoia e Constantin Gonciulea, "Canonical Construction of Quantum Oracles", arXiv: 2006.10656.

[5] Austin Gilliam, Marco Pistoia e Constantin Gonciulea, "Ottimizzazione della ricerca quantistica con una versione binomiale dell'algoritmo di Grover", arXiv: 2007.10894.

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

[7] Sayantan Pramanik, M Girish Chandra, Shampa Sarkar e Manoj Nambiar, "Ricerca di fase approssimativa e stima di Eigen utilizzando l'algoritmo di Grover modificato", arXiv: 2012.11497.

[8] Su Yeon Chang, Steven Herbert, Sofia Vallecorsa, Elías F. Combarro e Ross Duncan, "Modello GAN a circuito quantistico a due parametri in fisica delle alte energie", arXiv: 2103.15470.

[9] Marika Svensson, Martin Andersson, Mattias Grönkvist, Pontus Vikstål, Devdatt Dubhashi, Giulia Ferrini e Göran Johansson, "Un metodo euristico per risolvere programmi lineari interi su larga scala combinando Branch-and-Price con un algoritmo quantistico", arXiv: 2103.15433.

[10] Yidong Liao, Min-Hsiu Hsieh e Chris Ferrie, "Quantum Optimization for Training Quantum Neural Networks", arXiv: 2103.17047.

Le citazioni sopra sono di ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2021-04-10 02:42:05). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.

On Il servizio citato da Crossref non sono stati trovati dati su citazioni (ultimo tentativo 2021-04-10 02:42:03).

Questo documento è pubblicato in Quantum sotto il Creative Commons Attribuzione 4.0 Internazionale (CC BY 4.0) licenza. Il copyright rimane dei detentori del copyright originali come gli autori o le loro istituzioni.

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

Timestamp:

Di più da Diario quantistico