1JPMorgan Chase
2IBM Quantum, IBM Research – Zürich
Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.
Abstrakt
I dette papir diskuterer vi Grover Adaptive Search (GAS) for Constrained Polynomial Binary Optimization (CPBO) problemer, og især Quadratic Unconstrained Binary Optimization (QUBO) problemer, som et særligt tilfælde. GAS kan give en kvadratisk fremskyndelse for kombinatoriske optimeringsproblemer sammenlignet med brute force-søgning. Dette kræver dog udvikling af effektive orakler til at repræsentere problemer og flagstater, der opfylder bestemte søgekriterier. Generelt kan dette opnås ved hjælp af kvantearitmetik, men dette er dyrt med hensyn til Toffoli-porte såvel som nødvendige ancilla-qubits, hvilket kan være uoverkommeligt på kort sigt. Inden for dette arbejde udvikler vi en måde at konstruere effektive orakler til at løse CPBO-problemer ved hjælp af GAS-algoritmer. Vi demonstrerer denne tilgang og den potentielle fremskyndelse af porteføljeoptimeringsproblemet, dvs. en QUBO, ved hjælp af simulering og eksperimentelle resultater opnået på ægte kvantehardware. Vores tilgang gælder dog for højere grads polynomielle objektivfunktioner såvel som begrænsede optimeringsproblemer.
Udvalgt billede: Outputsandsynlighederne for GAS for to iterationer kører på ægte kvantehardware med respektive tærskler $y$ og $r$ applikationer fra Grover-operatøren. De gyldige måleresultater er vist med blåt, mens de ugyldige måleresultater er vist i gråt.
Populært resumé
► BibTeX-data
► Referencer
[1] Kærlighed K. Grover. En hurtig kvantemekanisk algoritme til databasesøgning. I Proceedings of the Twenty-Eightth Annual ACM Symposium on Theory of Computing, STOC '96, side 212-219, New York, NY, USA, 1996. ACM. ISBN 0-89791-785-5. 10.1145/237814.237866.
https:///doi.org/10.1145/237814.237866
[2] Peter W. Shor. Polynomial-tidsalgoritmer til primfaktorisering og diskrete logaritmer på en kvantecomputer. SIAM Journal on Computing, 26 (5): 1484–1509, okt 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, og et al. På vej mod kvantekemi på en kvantecomputer. Nature Chemistry, 2 (2): 106-111, jan 2010. ISSN 1755-4349. 10.1038/nchem.483.
https://doi.org/10.1038/nchem.483
[4] Aram W. Harrow, Avinatan Hassidim og Seth Lloyd. Kvantealgoritme til lineære ligningssystemer. Physical Review Letters, 103 (15), okt 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 Cincio og Patrick J. Coles. Variational quantum linear solver, 2020. URL https:///arxiv.org/abs/1909.05820.
arXiv: 1909.05820
[6] Patrick Rebentrost, Brajesh Gupt og Thomas R. Bromley. Kvanteberegningsfinansiering: Monte carlo-prissætning af finansielle derivater. Phys. Rev. A, 98: 022321, aug 2018. 10.1103/PhysRevA.98.022321.
https:///doi.org/10.1103/PhysRevA.98.022321
[7] Stefan Woerner og Daniel J. Egger. Kvanterisikoanalyse. 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 og S. Woerner. Kreditrisikoanalyse ved hjælp af kvantecomputere. IEEE-transaktioner på computere, side 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 og Stefan Woerner. Optionsprissætning ved brug af kvantecomputere. Quantum, 4: 291, jul 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 og 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 og Jeremy L. O'Brien. En variationsegenværdiløser på en fotonisk kvanteprocessor. Nature Communications, 5: 4213, 2014. ISSN 20411723. 10.1038/ncomms5213.
https:///doi.org/10.1038/ncomms5213
[12] Giacomo Nannicini. Ydeevne af hybride kvanteklassiske variationsheuristika til kombinatorisk optimering. Physical Review E, 99: 013304, jan 2019. 10.1103/PhysRevE.99.013304.
https:///doi.org/10.1103/PhysRevE.99.013304
[13] Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli og Stefan Woerner. Forbedring af variationskvanteoptimering ved hjælp af 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 og S. Woerner. Kvantealgoritmer til blandet binær optimering anvendt til transaktionsafvikling. 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 og John Preskill. Robusthed af adiabatisk kvanteberegning. 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, et al. Kvanteudglødning med fremstillede spins. Nature, 473 (7346): 194–198, 2011. 10.1038/nature10012.
https:///doi.org/10.1038/nature10012
[17] Christoph Dürr og Peter Høyer. En kvantealgoritme til at finde minimum, 1996. URL https:///arxiv.org/abs/quant-ph/9607014.
arXiv:quant-ph/9607014
[18] D. Bulger, WP Baritompa og GR Wood. Implementering af ren adaptiv søgning med Grovers kvantealgoritme. Journal of Optimization Theory and Applications, 116 (3): 517–529, Mar 2003. ISSN 1573-2878. 10.1023/A:1023061218864.
https://doi.org/10.1023/A:1023061218864
[19] WP Baritompa, DW Bulger og GR Wood. Grovers kvantealgoritme anvendt til global optimering. SIAM J. om optimering, 15 (4): 1170–1184, april 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 og Constantin Gonciulea. Grundlæggende mønstre for effektiv kvanteberegning, 2019. URL https:///arxiv.org/abs/1907.11513.
arXiv: 1907.11513
[21] Thomas G. Draper. Tilføjelse på en kvantecomputer, 2000. URL https:///arxiv.org/abs/quant-ph/0008033.
arXiv:quant-ph/0008033
[22] Román Orús, Samuel Mugel og Enrique Lizaso. Kvanteberegning til finansiering: Overblik og udsigter. Reviews in Physics, 4: 100028, nov 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 og Elena Yndurain. Kvanteberegning til finansiering: State-of-the-art og fremtidsudsigter. 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 og Seth Lloyd. Quantum computational finance: quantum algorithm for portfolio optimization, 2018. URL https:///arxiv.org/abs/1811.03975.
arXiv: 1811.03975
[25] Davide Venturelli og Alexei Kondratyev. Omvendt kvanteudglødningstilgang til porteføljeoptimeringsproblemer. 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 og Stefan Woerner. Varmstartende kvanteoptimering, 2020b. URL https:///arxiv.org/abs/2009.10095.
arXiv: 2009.10095
[27] Héctor Abraham et. al. Qiskit: En open source-ramme til kvanteberegning. 2019. 10.5281/zenodo.2562110.
https:///doi.org/10.5281/zenodo.2562110
[28] Michele Mosca. Kvantesøgning, optælling og amplitudeforstærkning ved egenvektoranalyse. In Proceedings of Randomized Algorithms, Workshop of Mathematical Foundations of Computer Science, side 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 og Alain Tapp. Kvanteamplitudeforstærkning og estimering. Contemporary Mathematics, 305, 2002. 10.1090/conm/305.
https://doi.org/10.1090/conm/305
[30] Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tomoki Tanaka, Tamiya Onodera og Naoki Yamamoto. Amplitudestimering uden faseestimering. Quantum Information Processing, 19 (2), jan 2020. ISSN 1573-1332. 10.1007/s11128-019-2565-2.
https://doi.org/10.1007/s11128-019-2565-2
[31] Scott Aaronson og Patrick Rall. Kvante omtrentlig optælling, forenklet. Symposium on Simplicity in Algorithms, side 24-32, jan 2020. 10.1137/1.9781611976014.5.
https:///doi.org/10.1137/1.9781611976014.5
[32] Michel Boyer, Gilles Brassard, Peter Høyer og Alain Tapp. Snævre grænser for kvantesøgning. Fortschritte der Physik, 46 (4-5): 493-505, jun 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 og Marcos Villagra. Multiobjektiv optimering Grover Adaptive Search, side 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 og Dmitri Maslov. Tilnærmet kvantefourier-transformation med o(n log(n)) t-porte. npj Quantum Information, 6 (1), Mar 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 og David Petrie Moulton. Et nyt quantum ripple-carry additionskredsløb, 2004. URL https:///arxiv.org/abs/quant-ph/0410184.
arXiv:quant-ph/0410184
[36] Thomas G. Draper, Samuel A. Kutin, Eric M. Rains og Krysta M. Svore. En logaritmisk-dybde kvante-bære-lookahead adder. Kvante info. Comput., 6 (4): 351-369, juli 2006. ISSN 1533-7146. 10.26421/QIC6.4-5-4.
https:///doi.org/10.26421/QIC6.4-5-4
[37] Craig Gidney. Halvering af omkostningerne ved kvantetilsætning. Quantum, 2: 74, jun 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 og Jay M. Gambetta. Validering af kvantecomputere ved hjælp af randomiserede modelkredsløb. Physical Review A, 100 (3), sep. 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 og D. Esteve. Karakterisering af en to-transmon-processor med individuel single-shot qubit-udlæsning. Phys. Rev. Lett., 108: 057002, feb 2012. 10.1103/PhysRevLett.108.057002.
https:///doi.org/10.1103/PhysRevLett.108.057002
[40] Svante Janson. Momenter af gamma-type og brownian supremum-procesområdet. Sandsynligvis. Surveys, 7: 1–52, 2010. 10.1214/10-PS160.
https://doi.org/10.1214/10-PS160
[41] Michael A. Nielsen og Isaac L. Chuang. Kvanteberegning og kvanteinformation: 10th Anniversary Edition. Cambridge University Press, New York, NY, USA, 10. udgave, 2011. ISBN 1107002176, 9781107002173. 10.1017/CBO9780511976667.
https:///doi.org/10.1017/CBO9780511976667
Citeret af
[1] Daniel J. Egger, Claudio Gambella, Jakub Marecek, Scott McFaddin, Martin Mevissen, Rudy Raymond, Andrea Simonetto, Stefan Woerner og Elena Yndurain, "Quantum Computing for Finance: State of the Art and Future Prospects", arXiv: 2006.14510.
[2] Claudio Gambella og Andrea Simonetto, "Multi-blok ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers", arXiv: 2001.02069.
[3] Austin Gilliam, Marco Pistoia og Constantin Gonciulea, "Optimering af kvantesøgning ved hjælp af en generaliseret version af Grovers algoritme", arXiv: 2005.06468.
[4] Austin Gilliam, Marco Pistoia og Constantin Gonciulea, "Canonical Construction of Quantum Oracles", arXiv: 2006.10656.
[5] Austin Gilliam, Marco Pistoia og Constantin Gonciulea, "Optimering af kvantesøgning med en binomial version af Grovers algoritme", arXiv: 2007.10894.
[6] Julien Gacon, Christa Zoufal, Giuseppe Carleo og Stefan Woerner, "Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information", arXiv: 2103.09232.
[7] Sayantan Pramanik, M Girish Chandra, Shampa Sarkar og Manoj Nambiar, "Omtrentlig fasesøgning og egenestimering ved hjælp af modificeret Grover's Algorithm", arXiv: 2012.11497.
[8] Su Yeon Chang, Steven Herbert, Sofia Vallecorsa, Elías F. Combarro og 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 og Göran Johansson, "A Heuristic 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 og Chris Ferrie, "Quantum Optimization for Training Quantum Neural Networks", arXiv: 2103.17047.
Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2021-04-10 02:42:05). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.
On Crossrefs citeret af tjeneste ingen data om at citere værker blev fundet (sidste forsøg 2021-04-10 02:42:03).
Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.
- adgang
- algoritme
- algoritmer
- analyse
- applikationer
- april
- OMRÅDE
- Kunst
- austin
- forfattere
- Cambridge
- kemi
- Kommunikation
- Datalogi
- computere
- computing
- opbygge
- ophavsret
- kredit
- data
- Database
- Den
- Derivater
- udvikle
- Udvikling
- manufakturhandler
- energi
- Engineering
- FAST
- finansiere
- finansielle
- Framework
- fremtiden
- GAS
- Gates
- Generelt
- Global
- halvering
- Hardware
- Harvard
- Høj
- HTTPS
- Hybrid
- IBM
- IEEE
- billede
- info
- oplysninger
- institutioner
- Intelligens
- internationalt
- JavaScript
- Johnson
- juli
- Licens
- Liste
- kærlighed
- mand
- fremstillet
- markere
- matematik
- blandet
- model
- net
- Neural
- neurale netværk
- New York
- NY
- åbent
- Option
- Papir
- ydeevne
- Fysik
- portefølje
- trykke
- prissætning
- Programmer
- Publicering
- Quantum
- kvantecomputere
- quantum computing
- qubit
- Tilfældigt
- forskning
- Resultater
- vende
- gennemgå
- Anmeldelser
- Risiko
- ROBERT
- Kør
- Videnskab
- Søg
- afregning
- simulation
- SOLVE
- Tilstand
- Stater
- Systemer
- Kurser
- transaktion
- Transaktioner
- universitet
- USA
- bind
- W
- inden for
- Arbejde
- virker
- år
- Yuan
