1IBM Quantum, IBM Research – Zürich, Säumerstrasse 4, 8803 Rüschlikon, Zwitserland
2Tsjechische Technische Universiteit, Karlovo nam. 13, Praag 2, Tsjechië
Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.
Abstract
Er is een toenemende belangstelling voor kwantumalgoritmen voor problemen met het programmeren van gehele getallen en combinatorische optimalisatie. Klassieke oplossers voor dergelijke problemen maken gebruik van relaxaties, die binaire variabelen vervangen door continue variabelen, bijvoorbeeld in de vorm van hoger-dimensionale matrix-gewaardeerde problemen (semidefinite programmering). Volgens het vermoeden van Unique Games bieden deze versoepelingen vaak de beste prestatieverhoudingen die klassiek beschikbaar zijn in polynomiale tijd. Hier bespreken we hoe kwantumoptimalisatie warm kan worden gestart met een begintoestand die overeenkomt met de oplossing van een versoepeling van een combinatorisch optimalisatieprobleem en hoe eigenschappen van de bijbehorende kwantumalgoritmen kunnen worden geanalyseerd. Dit zorgt er met name voor dat het kwantumalgoritme de prestatiegaranties van het klassieke algoritme kan erven. We illustreren dit in de context van portfolio-optimalisatie, waar onze resultaten aangeven dat het warm starten van het Quantum Approximate Optimization Algorithm (QAOA) vooral gunstig is op lage diepte. Evenzo toont recursieve QAOA voor MAXCUT-problemen een systematische toename in de grootte van de verkregen snede voor volledig verbonden grafieken met willekeurige gewichten, wanneer Goemans-Williamson gerandomiseerde afronding wordt gebruikt bij een warme start. Het is eenvoudig om dezelfde ideeën toe te passen op andere schema's met gerandomiseerde afronding en optimalisatieproblemen.
Uitgelichte afbeelding: het kwantumcircuit van QAOA met een warme start.
Populaire samenvatting
► BibTeX-gegevens
► Referenties
[1] Nikolaj Moll, Panagiotis Barkoutsos, Lev S. Bishop, Jerry M. Chow, Andrew Cross, Daniel J. Egger, Stefan Filipp, Andreas Fuhrer, Jay M. Gambetta, Marc Ganzhorn en et al. Kwantumoptimalisatie met behulp van variatiealgoritmen op korte termijn kwantumapparaten. Kwantumwetenschap. Technol., 3 (3): 030503, 2018. 10.1088/2058-9565/aab822.
https: / / doi.org/ 10.1088 / 2058-9565 / aab822
[2] Abhinav Kandala, Kristan Temme, Antonio D. Corcoles, Antonio Mezzacapo, Jerry M. Chow en Jay M. Gambetta. Foutbeperking vergroot het rekenbereik van een lawaaierige kwantumprocessor. Natuur, 567: 491-495, 2018. 10.1038/s41586-019-1040-7.
https://doi.org/10.1038/s41586-019-1040-7
[3] Marc Ganzhorn, Daniel J. Egger, Panagiotis Kl. Barkoutsos, Pauline Ollitrault, Gian Salis, Nikolaj Moll, Andreas Fuhrer, Peter Mueller, Stefan Woerner, Ivano Tavernelli en Stefan Filipp. Gate-efficiënte simulatie van moleculaire eigentoestanden op een kwantumcomputer. Fys. Rev. Applied, 11: 044092, april 2019. 10.1103/PhysRevApplied.11.044092.
https: / / doi.org/ 10.1103 / PhysRevApplied.11.044092
[4] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe en Seth Lloyd. Kwantummachine leren. Nature, 549 (7671): 195-202, 2017. 10.1038/nature23474.
https: / / doi.org/ 10.1038 / nature23474
[5] Vojtech Havlicek, Antonio D. Corcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow en Jay M. Gambetta. Begeleid leren met door kwantum verbeterde functieruimten. Natuur, 567: 209 – 212, 2019. 10.1038/s41586-019-0980-2.
https://doi.org/10.1038/s41586-019-0980-2
[6] Daniel J. Egger, Claudio Gambella, Jakub Mareček, Scott McFaddin, Martin Mevissen, Rudy Raymond, Aandrea Simonetto, Sefan Woerner en Elena Yndurain. Quantum computing voor financiën: state-of-the-art en toekomstperspectieven. IEEE Trans. op Quantum Eng., 1: 1-24, 2020. 10.1109/TQE.2020.3030314.
https: / / doi.org/ 10.1109 / TQE.2020.3030314
[7] Stefan Woerner en Daniel J. Egger. Kwantumrisicoanalyse. npj Quantum Inf., 5: 15, 2019. 10.1038/s41534-019-0130-6.
https://doi.org/10.1038/s41534-019-0130-6
[8] Patrick Rebentrost, Brajesh Gupt en Thomas R. Bromley. Quantum computationele financiering: Monte Carlo-prijsstelling van financiële derivaten. Phys. Rev.A, 98: 022321, augustus 2018. 10.1103 / PhysRevA.98.022321.
https: / / doi.org/ 10.1103 / PhysRevA.98.022321
[9] Nikitas Stamatopoulos, Daniel J. Egger, Yue Sun, Christa Zoufal, Raban Iten, Ning Shen en Stefan Woerner. Optieprijzen met behulp van kwantumcomputers. Quantum, 4:291, 2020. 10.22331/q-2020-07-06-291.
https://doi.org/10.22331/q-2020-07-06-291
[10] Ana Martin, Bruno Candelas, Ángel Rodríguez-Rozas, José D. Martín-Guerrero, Xi Chen, Lucas Lamata, Román Orús, Enrique Solano en Mikel Sanz. Op weg naar de prijsbepaling van financiële derivaten met een IBM-kwantumcomputer. Fys. Rev. Research, 3: 013167, februari 2021. 10.1103/PhysRevResearch.3.013167.
https: / / doi.org/ 10.1103 / PhysRevResearch.3.013167
[11] Roman Orus, Samuel Mugel en Enrique Lizaso. Quantum computing voor financiën: overzicht en vooruitzichten. Rev. Phys., 4: 100028, 2019. 10.1016/j.revip.2019.100028.
https: / / doi.org/ 10.1016 / j.revip.2019.100028
[12] Daniel J. Egger, Ricardo G. Gutierrez, Jordi Cahue Mestre en Stefan Woerner. Kredietrisicoanalyse met behulp van kwantumcomputers. IEEE Trans. Computer, 1: 1-1, nov 2020. 10.1109/TC.2020.3038063.
https: / / doi.org/ 10.1109 / TC.2020.3038063
[13] Almudena Carrera Vazquez en Stefan Woerner. Efficiënte toestandsvoorbereiding voor schatting van kwantumamplitude. Fys. Toegepast, 15: 034027, maart 2021. 10.1103/PhysRevApplied.15.034027.
https: / / doi.org/ 10.1103 / PhysRevApplied.15.034027
[14] Lee Braine, Daniel J. Egger, Jennifer Glick en Stefan Woerner. Quantumalgoritmen voor gemengde binaire optimalisatie toegepast op transactieafwikkeling. IEEE Trans. op Quantum Eng., 2: 1-8, 2021. 10.1109/TQE.2021.3063635.
https: / / doi.org/ 10.1109 / TQE.2021.3063635
[15] Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli en Stefan Woerner. Verbetering van variabele kwantumoptimalisatie met behulp van cvr. Quantum, 4: 256, april 2020. 10.22331/q-2020-04-20-256.
https://doi.org/10.22331/q-2020-04-20-256
[16] Edward Farhi, Jeffrey Goldstone en Sam Gutmann. Een kwantumbenaderend optimalisatie-algoritme, 2014a. URL https://arxiv.org/abs/1411.4028.
arXiv: 1411.4028
[17] Edward Farhi, Jeffrey Goldstone en Sam Gutmann. Een kwantumbenaderend optimalisatie-algoritme toegepast op een beperkingsprobleem met begrensd voorkomen, 2014b. URL https://arxiv.org/abs/1412.6062.
arXiv: 1412.6062
[18] Zhi-Cheng Yang, Armin Rahmani, Alireza Shabani, Hartmut Neven en Claudio Chamon. Optimalisatie van variabele kwantumalgoritmen met behulp van het minimumprincipe van pontryagin. Fys. Rev. X, 7:021027, mei 2017. 10.1103/PhysRevX.7.021027.
https: / / doi.org/ 10.1103 / PhysRevX.7.021027
[19] Mark W. Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, Richard Harris, Andrew J. Berkley, Jan Johansson, Paul Bunyk en et al. Quantum annealing met gefabriceerde spins. Nature, 473 (7346): 194-198, mei 2011. 10.1038/nature10012.
https: / / doi.org/ 10.1038 / nature10012
[20] Glen Bigan Mbeng, Rosario Fazio en Giuseppe Santoro. Quantum annealing: een reis door digitalisering, controle en hybride kwantumvariatieschema's, 2019. URL https://arxiv.org/abs/1906.08948.
arXiv: 1906.08948
[21] Michael Juenger, Elisabeth Lobe, Petra Mutzel, Gerhard Reinelt, Franz Rendl, Giovanni Rinaldi en Tobias Stollenwerk. Prestaties van een quantum annealer voor Ising grondtoestandsberekeningen op chimera grafieken, 2019. URL https://arxiv.org/abs/1904.11965.
arXiv: 1904.11965
[22] Rami Barends, Alireza Shabani, Lucas Lamata, Julian Kelly, Antonio Mezzacapo, Urtzi Las Heras, Ryan Babbush, Austin G. Fowler, Brooks Campbell, Yu Chen en et al. Gedigitaliseerde adiabatische kwantumcomputers met een supergeleidend circuit. Nature, 534 (7606): 222–226, juni 2016. 10.1038/nature17658.
https: / / doi.org/ 10.1038 / nature17658
[23] Madita Willsch, Dennis Willsch, Fengping Jin, Hans De Raedt en Kristel Michielsen. Benchmarking van het kwantumbenaderende optimalisatie-algoritme. Quantum Inf. Proces., 19 (7): 197, juni 2020. 10.1007/s11128-020-02692-8.
https://doi.org/10.1007/s11128-020-02692-8
[24] Sergey Bravyi, Alexander Kliesch, Robert Koenig en Eugene Tang. Obstakels voor variabele kwantumoptimalisatie van symmetriebescherming. Fys. Rev. Lett., 125: 260505, december 2020a. 10.1103/PhysRevLett.125.260505.
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
[25] Gavin E. Crooks. Prestaties van het kwantum-benaderingsoptimalisatie-algoritme op het maximum-cut-probleem, 2018. URL https://arxiv.org/abs/1811.08419.
arXiv: 1811.08419
[26] Edward Farhi, Jeffrey Goldstone, Sam Gutmann en Hartmut Neven. Quantum-algoritmen voor vaste qubit-architecturen, 2017. URL https://arxiv.org/abs/1703.06199.
arXiv: 1703.06199
[27] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor Rieffel, Davide Venturelli en Rupak Biswas. Van het kwantumbenaderende optimalisatie-algoritme tot een kwantumalternerende operator ansatz. Algoritmen, 12 (2): 34, februari 2019. 10.3390/a12020034.
https: / / doi.org/ 10.3390 / a12020034
[28] Linghua Zhu, Ho Lun Tang, George S. Barron, Nicholas J. Mayhall, Edwin Barnes en Sophia E. Economou. Een adaptief algoritme voor het optimaliseren van kwantumbenadering voor het oplossen van combinatorische problemen op een kwantumcomputer, 2020. URL https://arxiv.org/abs/2005.10258.
arXiv: 2005.10258
[29] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy en Eleanor G. Rieffel. XY-mixers: analytische en numerieke resultaten voor de quantum alternerende operator ansatz. Fys. Rev. A, 101: 012320, januari 2020. 10.1103/PhysRevA.101.012320.
https: / / doi.org/ 10.1103 / PhysRevA.101.012320
[30] Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev en Prasanna Balaprakash. Variatie-quantumcircuits leren optimaliseren om combinatorische problemen op te lossen. Proceedings of the AAAI Conference on Artificial Intelligence, 34 (03): 2367–2375, april 2020. 10.1609/aaai.v34i03.5616.
https: / / doi.org/ 10.1609 / aaai.v34i03.5616
[31] Matteo M. Wauters, Emanuele Panizon, Glen B. Mbeng en Giuseppe E. Santoro. Door versterking ondersteunde kwantumoptimalisatie. Fys. Rev. Research, 2: 033446, september 2020. 10.1103/PhysRevResearch.2.033446.
https: / / doi.org/ 10.1103 / PhysRevResearch.2.033446
[32] Ruslan Shaydulin, Ilya Safro en Jeffrey Larson. Multistart-methoden voor kwantumbenaderende optimalisatie. 2019 IEEE High Performance Extreme Computing Conference (HPEC), pagina's 1–8, september 2019. 10.1109/HPEC.2019.8916288.
https://doi.org/10.1109/HPEC.2019.8916288
[33] Ruslan Shaydulin en Yuri Alexeev. Evaluatie van kwantumbenaderingsoptimalisatiealgoritme: een casestudy. In 2019 tiende International Green and Sustainable Computing Conference (IGSC), pagina's 1-6, 2019. 10.1109/IGSC48788.2019.8957201.
https://doi.org/10.1109/IGSC48788.2019.8957201
[34] Roeland Wiersema, Cunlu Zhou, Yvette de Sereville, Juan Felipe Carrasquilla, Yong Baek Kim en Henry Yuen. Onderzoek naar verstrengeling en optimalisatie binnen de hamiltoniaanse variantie ansatz. PRX Quantum, 1: 020319, december 2020. 10.1103/PRXQuantum.1.020319.
https: / / doi.org/ 10.1103 / PRXQuantum.1.020319
[35] Fernando GSL Brandao, Michael Broughton, Edward Farhi, Sam Gutmann en Hartmut Neven. Voor vaste controleparameters concentreert de objectieve functiewaarde van het kwantum-benaderende optimalisatie-algoritme zich voor typische gevallen, 2018. URL https://arxiv.org/abs/1812.04170.
arXiv: 1812.04170
[36] Matthew B. Hastings. Klassieke en kwantumbegrensde algoritmen voor dieptebenadering, 2019. URL https://arxiv.org/abs/1905.07047.
arXiv: 1905.07047
[37] Sergey Bravyi, Alexander Kliesch, Robert Koenig en Eugene Tang. Hybride kwantum-klassieke algoritmen voor geschatte grafiekkleuring, 2020b. URL https://arxiv.org/abs/2011.13420.
arXiv: 2011.13420
[38] Mahabubul Alam, Abdullah Ash-Saki en Swaroop Ghosh. Analyse van kwantumbenaderingsoptimalisatiealgoritme onder realistische ruis in supergeleidende qubits, 2019. URL https://arxiv.org/abs/1907.09631.
arXiv: 1907.09631
[39] Vishwanathan Akshay, Hariphan Philathong, Mauro ES Morales en Jacob D. Biamonte. Bereikbaarheidstekorten bij optimalisatie van kwantumbenadering. Fys. Rev. Lett., 124: 090504, maart 2020a. 10.1103/PhysRevLett.124.090504.
https: / / doi.org/ 10.1103 / PhysRevLett.124.090504
[40] Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, Sergio Boixo en et al. Quantum benaderende optimalisatie van niet-planaire grafiekproblemen op een vlakke supergeleidende processor. nat. Phys., 17 (3): 332-336, maart 2021. 10.1038/s41567-020-01105-j.
https: / / doi.org/ 10.1038 / s41567-020-01105-y
[41] Yulong Dong, Xiang Meng, Lin Lin, Robert Kosut en K. Birgitta Whaley. Robuuste besturingsoptimalisatie voor algoritmen voor kwantumbenadering IFAC-PapersOnLine, 53 (2): 242–249, 2020. 10.1016/j.ifacol.2020.12.130. 21e IFAC Wereldcongres.
https:///doi.org/10.1016/j.ifacol.2020.12.130
[42] Nathan Lacroix, Christoph Hellings, Christian Kraglund Andersen, Agustin Di Paolo, Ants Remm, Stefania Lazar, Sebastian Krinner, Graham J. Norris, Mihai Gabureac, Johannes Heinsoo en et al. Verbetering van de prestaties van diepe kwantumoptimalisatie-algoritmen met continue poortsets. PRX Quantum, 1: 110304, oktober 2020. 10.1103/PRXQuantum.1.020304.
https: / / doi.org/ 10.1103 / PRXQuantum.1.020304
[43] Nathan Earnest, Caroline Tornow en Daniel J. Egger. Pulsefficiënte circuittranspilatie voor kwantumtoepassingen op op cross-resonantie gebaseerde hardware, 2021. URL https://arxiv.org/abs/2105.01063.
arXiv: 2105.01063
[44] Pranav Gokhale, Ali Javadi-Abhari, Nathan Earnest, Yunong Shi en Frederic T. Chong. Geoptimaliseerde kwantumcompilatie voor kortetermijnalgoritmen met openpulse, 2020. URL https://www.microarch.org/micro53/papers/738300a186.pdf. 10.1109/MICRO50266.2020.00027.
https:///doi.org/10.1109/MICRO50266.2020.00027
https:///www.microarch.org/micro53/papers/738300a186.pdf
[45] David C. McKay, Thomas Alexander, Luciano Bello, Michael J. Biercuk, Lev Bishop, Jiayin Chen, Jerry M. Chow, Antonio D. Córcoles, Daniel J. Egger, Stefan Filipp en et al. Qiskit-backendspecificaties voor OpenQASM- en OpenPulse-experimenten, 2018. URL https://arxiv.org/abs/1809.03452.
arXiv: 1809.03452
[46] Thomas Alexander, Naoki Kanazawa, Daniel J. Egger, Lauren Capelluto, Christopher J. Wood, Ali Javadi-Abhari en David C. McKay. Qiskit pulse: kwantumcomputers programmeren via de cloud met pulsen. Kwantumwetenschap. Technol., 5 (4): 044006, aug 2020. 10.1088/2058-9565/aba404.
https: / / doi.org/ 10.1088 / 2058-9565 / aba404
[47] Anirudha Majumdar, Georgina Hall en Amir Ali Ahmadi. Recente schaalbaarheidsverbeteringen voor semidefinitief programmeren met toepassingen in machine learning, besturing en robotica. Ann. Rev. Controle Robot. auton. Syst., 3: 331-360, 2020. 10.1146/annurev-control-091819-074326.
https://doi.org/10.1146/annurev-control-091819-074326
[48] Miguel F. Anjos en Jean B. Lasserre. Handboek over semidefinite, conische en polynomiale optimalisatie, volume 166. Springer Science & Business Media, 2011. 10.1007/978-1-4614-0769-0.
https://doi.org/10.1007/978-1-4614-0769-0
[49] Lenore Blum, Felipe Cucker, Michael Shub en Steve Smale. Complexiteit en echte berekening. Springer Science & Business Media, 2012. 10.1007/978-1-4612-0701-6.
https://doi.org/10.1007/978-1-4612-0701-6
[50] Lorant Porkolab en Leonid Khachiyan. Over de complexiteit van semidefinite programma's. J. Glob. Optimaal, 10 (4): 351-365, 1997. 10.1023/A:1008203903341.
https: / / doi.org/ 10.1023 / A: 1008203903341
[51] Alp Yurtsever, Joel A. Tropp, Olivier Fercoq, Madeleine Udell en Volkan Cevher. Schaalbare semi-definitieve programmering. SIAM J. Math. Data Sci., 3 (1): 171-200, 2021. 10.1137/19M1305045.
https: / / doi.org/ 10.1137 / 19M1305045
[52] Prabhakar Raghavan en Clark D. Tompson. Gerandomiseerde afronding: een techniek voor aantoonbaar goede algoritmen en algoritmische bewijzen. Combinatorica, 7 (4): 365-374, december 1987. 10.1007/BF02579324.
https: / / doi.org/ 10.1007 / BF02579324
[53] Michel X. Goemans en David P. Williamson. Verbeterde benaderingsalgoritmen voor maximale snij- en verzadigingsproblemen met behulp van semidefinite programmering. J. ACM, 42 (6): 1115-1145, nov 1995. 10.1145/227683.227684.
https: / / doi.org/ 10.1145 / 227683.227684
[54] Howard Karloff. Hoe goed is het Goemans-Williamson MAX CUT-algoritme? SIAM J. Comput., 29 (1): 336–350, 1999. 10.1137/S0097539797321481.
https: / / doi.org/ 10.1137 / S0097539797321481
[55] Subhash Khot, Guy Kindler, Elchanan Mossel en Ryan O'Donnell. Optimale onbenaderbaarheidsresultaten voor MAX-CUT en andere 2-variabele CSP's? SIAM J. Comput., 37 (1): 319-357, 2007. 10.1137/S0097539705447372.
https: / / doi.org/ 10.1137 / S0097539705447372
[56] Subhas Khot. Op het unieke vermoeden van games (invited survey). In 2012 IEEE 27th Conference on Computational Complexity, pagina's 99-121, Los Alamitos, CA, VS, juni 2010. IEEE Computer Society. 10.1109/CCC.2010.19.
https: / / doi.org/ 10.1109 / CCC.2010.19
[57] Subhash A. Khot en Nisheeth K. Vishnoi. Het unieke vermoeden van games, integraliteitskloof voor snijproblemen en de inbedbaarheid van meetwaarden van het negatieve type in l1. J. ACM, 62 (1): 1–39, 2015. 10.1145/2629614.
https: / / doi.org/ 10.1145 / 2629614
[58] Kunal Marwaha. Lokale klassieke MAX-CUT-algoritme presteert beter dan $p=2$ QAOA op regelmatige grafieken met een hoge omtrek. Quantum, 5: 437, april 2021. 10.22331/q-2021-04-20-437.
https://doi.org/10.22331/q-2021-04-20-437
[59] Peter L. Hammer en Sergiu Rudeanu. Booleaanse methoden in operationeel onderzoek en aanverwante gebieden. Springer Science & Business Media, 1968. 10.1007/978-3-642-85823-9.
https://doi.org/10.1007/978-3-642-85823-9
[60] Jean B. Lasserre. Een MAX-CUT formulering van 0/1 programma's. oper. Onderzoek Lett., 44 (2): 158 – 164, 2016. 10.1016/j.orl.2015.12.014.
https:///doi.org/10.1016/j.orl.2015.12.014
[61] Panos M. Pardalos en Georg Schnitger. Het controleren van lokale optimaliteit in beperkte kwadratische programmering is np-moeilijk. oper. Onderzoek Lett., 7 (1): 33-35, 1988. 10.1016/0167-6377(88)90049-1.
https://doi.org/10.1016/0167-6377(88)90049-1
[62] Kim Allemand, Komei Fukuda, Thomas M Liebling en Erich Steiner. Een polynoom geval van onbeperkte nul-één kwadratische optimalisatie. Wiskunde. Programma., 91 (1): 49-52, 2001. 10.1007/s101070100233.
https: / / doi.org/ 10.1007 / s101070100233
[63] Milan Hladík, Michal Černý en Miroslav Rada. Een nieuwe polynoom oplosbare klasse van kwadratische optimalisatieproblemen met box-beperkingen. arXiv:1911.10877, 2019. URL https://arxiv.org/abs/1911.10877.
arXiv: 1911.10877
[64] Jacek Gondzio en Andreas Grothey. Niet-lineaire financiële planningsproblemen oplossen met $10^9$ beslissingsvariabelen op massaal parallelle architecturen. WIT Trans Modeling Simul., 43: 11, 2006. 10.2495/CF060101.
https:///doi.org/10.2495/CF060101
[65] Svatopluk Poljak, Franz Rendl en Henry Wolkowicz. Een recept voor semi-definitieve ontspanning voor (0, 1)-kwadratische programmering. J. Glob. Optimaal, 7 (1): 51-73, 1995. 10.1007/BF01100205.
https: / / doi.org/ 10.1007 / BF01100205
[66] Joran Van Apeldoorn, András Gilyén, Sander Gribling en Ronald de Wolf. Quantum SDP-solvers: betere boven- en ondergrenzen. Quantum, 4: 230, 2020. 10.22331/q-2020-02-14-230.
https://doi.org/10.22331/q-2020-02-14-230
[67] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore en Xiaodi Wu. Quantum SDP Solvers: grote versnellingen, optimaliteit en toepassingen voor kwantumleren. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 van Leibniz International Proceedings in Informatics (LIPIcs), pagina's 27:1–27:14, Dagstuhl, Duitsland, 2019. Schloss Dagstuhl–Leibniz-Zentrum für Informatica. ISBN 978-3-95977-109-2. 10.4230/LIPics.ICALP.2019.27.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.27
[68] Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin en Chunhao Wang. Quantum-geïnspireerd sublineair algoritme voor het oplossen van semidefinite programmering met een lage rangorde. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 van Leibniz International Proceedings in Informatics (LIPIcs), pagina's 23:1–23:15, Dagstuhl, Duitsland, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik . ISBN 978-3-95977-159-7. 10.4230/LIPIcs.MFCS.2020.23.
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2020.23
[69] Jacek Gondzio. Warme start van de oer-duale methode toegepast in het snijvlakschema. Wiskunde. Programma., 83 (1-3): 125–143, 1998. 10.1007/BF02680554.
https: / / doi.org/ 10.1007 / BF02680554
[70] Andreas Lucas. Formuleringen van veel NP-problemen formuleren. Voorkant. Phys., 2: 5, 2014. 10.3389/fphy.2014.00005.
https: / / doi.org/ 10.3389 / fphy.2014.00005
[71] Bas Lodewijks. Het in kaart brengen van np-harde en NP-complete optimalisatieproblemen aan kwadratische onbeperkte binaire optimalisatieproblemen. arXiv:1911.08043, 2019. URL https://arxiv.org/abs/1911.08043.
arXiv: 1911.08043
[72] Jean B. Lasserre. Globale optimalisatie met polynomen en het probleem van momenten. SIAM J. Optim., 11 (3): 796-817, 2001. 10.1137/S1052623400366802.
https: / / doi.org/ 10.1137 / S1052623400366802
[73] Jean B. Lasserre. Convergente SDP-relaxaties in polynomiale optimalisatie met schaarste. SIAM J. Optim., 17 (3): 822–843, 2006. 10.1137/05064504X.
https: / / doi.org/ 10.1137 / 05064504X
[74] Bissan Ghaddar, Juan C. Vera en Miguel F. Anjos. Tweede-orde kegelrelaxaties voor binaire kwadratische polynoomprogramma's. SIAM J. Optim., 21 (1): 391-414, 2011. 10.1137/100802190.
https: / / doi.org/ 10.1137 / 100802190
[75] Moses Charikar en Anthony Wirth. Maximaliseren van kwadratische programma's: uitbreiding van de ongelijkheid van Grothendieck. In het 45e jaarlijkse IEEE-symposium over de grondslagen van de informatica, pagina's 54-60. IEEE, 2004. 10.1109/FOCS.2004.39.
https: / / doi.org/ 10.1109 / FOCS.2004.39
[76] Mikhail Krechetov, Jakub Mareček, Yury Maximov en Martin Takáč. Entropie-bestraft semidefinite programmering. In Proceedings van de achtentwintigste internationale gezamenlijke conferentie over kunstmatige intelligentie, 2019. 10.24963/ijcai.2019/157.
https:///doi.org/10.24963/ijcai.2019/157
[77] Sartaj Sahni en Teofilo Gonzalez. P-volledige benaderingsproblemen. J. ACM, 23 (3): 555-565, 1976. 10.1145/321958.321975. Zie Lemma A2.
https: / / doi.org/ 10.1145 / 321958.321975
[78] Michael Mitzenmacher en Eli Upfal. Waarschijnlijkheid en informatica: Randomisatie en probabilistische technieken in algoritmen en data-analyse. Universiteitspers van Cambridge, 2017.
[79] Sepehr Abbasi-Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz en Mohit Singh. Kleverige browniaanse afronding en zijn toepassingen om tevredenheidsproblemen te beperken. In Proceedings van het veertiende jaarlijkse ACM-SIAM-symposium over discrete algoritmen, pagina's 854-873. SIAM, 2020. 10.1137/1.9781611975994.52.
https: / / doi.org/ 10.1137 / 1.9781611975994.52
[80] Ronen Eldan en Assaf Naor. Krivine diffusies bereiken de goemans-williamson benaderingsverhouding. arXiv:1906.10615, 2019. URL https://arxiv.org/abs/1906.10615.
arXiv: 1906.10615
[81] Jamie Morgenstern, Samira Samadi, Mohit Singh, Uthaipon Tantipongpipat en Santosh Vempala. Redelijke dimensionaliteitsreductie en iteratieve afronding voor SDP's. arXiv:1902.11281, 2019. URL https://arxiv.org/abs/1902.11281v1.
arXiv: 1902.11281
[82] Samuel Karlin en Howard E. Taylor. Een tweede cursus in stochastische processen. Elsevier, 1981. p. 257 en de volgende.
[83] Julia Kempe, Oded Regev en Ben Toner. Het unieke vermoeden van spellen met verstrengelde bewijzers is onjuist. In algebraïsche methoden in computationele complexiteit, 2007.
[84] Julia Kempe, Oded Regev en Ben Toner. Unieke spellen met verstrengelde bewijzers zijn eenvoudig. SIAM J. Comput., 39 (7): 3207–3229, 2010. 10.1137/090772885.
https: / / doi.org/ 10.1137 / 090772885
[85] Charles H. Bennett, Ethan Bernstein, Gilles Brassard en Umesh Vazirani. Sterke en zwakke punten van quantum computing. SIAM J. Comput., 26 (5): 1510-1523, 1997. 10.1137 / S0097539796300933.
https: / / doi.org/ 10.1137 / S0097539796300933
[86] Harry Markowitz. Portefeuille selectie. J. Finance, 7 (1): 77–91, 1952. 10.2307/2975974.
https: / / doi.org/ 10.2307 / 2975974
[87] H.Abraham et al. Qiskit: een open-source raamwerk voor kwantumcomputing, 2019. URL https://doi.org/10.5281/zenodo.2562111.
https: / / doi.org/ 10.5281 / zenodo.2562111
[88] Johan Håstad. Enkele optimale onbenaderbaarheidsresultaten. J. ACM, 48 (4): 798-859, 2001. 10.1145/502090.502098.
https: / / doi.org/ 10.1145 / 502090.502098
[89] Vishwanathan Akshay, Hariphan Philathong, Igor Zacharov en Jacob D. Biamonte. Bereikbaarheidstekorten impliciet in Google's kwantumbenadering van grafische problemen, 2020b. URL https://arxiv.org/abs/2007.09148.
arXiv: 2007.09148
[90] Rebekah Herrman, James Ostrowski, Travis S. Humble en George Siopsis. Ondergrenzen van de circuitdiepte van het kwantumbenaderende optimalisatie-algoritme. Quantum Inf. Proces., 20 (2): 59, februari 2021. 10.1007/s11128-021-03001-7.
https://doi.org/10.1007/s11128-021-03001-7
[91] Zhihui Wang, Stuart Hadfield, Zhang Jiang en Eleanor G. Rieffel. Quantum geschatte optimalisatie-algoritme voor maxcut: een fermionische weergave. Fys. Rev. A, 97: 022304, februari 2018. 10.1103/PhysRevA.97.022304.
https: / / doi.org/ 10.1103 / PhysRevA.97.022304
[92] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler en Mikhail D. Lukin. Quantum-benaderingsoptimalisatie-algoritme: prestaties, mechanisme en implementatie op apparaten op korte termijn. Fys. Rev. X, 10: 021067, juni 2020. 10.1103/PhysRevX.10.021067.
https: / / doi.org/ 10.1103 / PhysRevX.10.021067
[93] Jason Larkin, Matías Jonsson, Daniel Justice en Gian Giacomo Guerreschi. Evaluatie van kwantumbenaderingsoptimalisatie-algoritme op basis van de benaderingsratio van enkele steekproeven, 2020. URL https://arxiv.org/abs/2006.04831.
arXiv: 2006.04831
[94] qiskit-optimalisatie. https://github.com/Qiskit/qiskit-optimization. Betreden: 25. 04. 2021.
https:///github.com/Qiskit/qiskit-optimalisatie
[95] Andreas Bärtschi en Stephan Eidenbenz. Grover-mixers voor qaoa: complexiteit verschuiven van mixerontwerp naar staatsvoorbereiding. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pagina's 72-82, 2020. 10.1109/QCE49297.2020.00020.
https: / / doi.org/ 10.1109 / QCE49297.2020.00020
[96] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler en Swati Gupta. Overbrugging van klassiek en kwantum met door SDP geïnitialiseerde warme starts voor QAOA, 2020. URL https://arxiv.org/abs/2010.14021.
arXiv: 2010.14021
[97] Iain Dunning, Swati Gupta en John Silberholz. Wat werkt wanneer het beste? een systematische evaluatie van heuristieken voor Max-Cut en QUBO. INFORMEERT J. Comput., 30 (3): 608–624, 2018. 10.1287/ijoc.2017.0798.
https: / / doi.org/ 10.1287 / ijoc.2017.0798
[98] Panagiotis Kl. Barkoutsos, Jerome F. Gonthier, Igor Sokolov, Nikolaj Moll, Gian Salis, Andreas Fuhrer, Marc Ganzhorn, Daniel J. Egger, Matthias Troyer, Antonio Mezzacapo en et al. Quantumalgoritmen voor elektronische structuurberekeningen: Particle-hole hamiltoniaans en geoptimaliseerde golffunctie-uitbreidingen. Fys. Rev. A, 98: 022322, aug 2018. 10.1103/PhysRevA.98.022322.
https: / / doi.org/ 10.1103 / PhysRevA.98.022322
[99] Sanjeev Arora en Shmuel Safra. Probabilistische controle van bewijzen: een nieuwe karakterisering van np. J. ACM, 45 (1): 70-122, 1998. 10.1145/273865.273901.
https: / / doi.org/ 10.1145 / 273865.273901
[100] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan en Mario Szegedy. Bewijsverificatie en de hardheid van benaderingsproblemen. J. ACM, 45 (3): 501-555, 1998. 10.1145/278298.278306.
https: / / doi.org/ 10.1145 / 278298.278306
[101] Irit Dinur. De PCP-stelling door gap-amplificatie. J. ACM, 54 (3): 12–es, jun 2007. 10.1145/1236457.1236459.
https: / / doi.org/ 10.1145 / 1236457.1236459
[102] Sanjeev Arora en Boaz Barak. Computationele complexiteit: een moderne benadering. Cambridge University Press, 2009.
[103] Subhash Khot. Op de kracht van unieke 2-prover 1-ronde games. In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC '02, pagina's 767-775, New York, NY, VS, 2002. Association for Computing Machinery. 10.1145/509907.510017.
https: / / doi.org/ 10.1145 / 509907.510017
[104] Prasad Raghavendra. Optimale algoritmen en onbenaderbaarheidsresultaten voor elke CSP? In Proceedings van het veertigste jaarlijkse ACM-symposium over Theory of computing, pagina's 245–254, 2008. 10.1145/1374376.1374414.
https: / / doi.org/ 10.1145 / 1374376.1374414
[105] Prasad Raghavendra en David Steurer. Hoe een CSP af te ronden. In 2009 50e jaarlijkse IEEE Symposium on Foundations of Computer Science, pagina's 586-594, 2009. 10.1109/FOCS.2009.74.
https: / / doi.org/ 10.1109 / FOCS.2009.74
[106] Subhash Khot, Dor Minzer en Muli Safra. Pseudo-willekeurige sets in Grassmann-grafieken hebben een bijna perfecte expansie. In Proceedings of the 592th Annual Symposium on Foundations of Computer Science (FOCS), pagina's 601–2018, 10.1109. 2018.00062/FOCS.XNUMX.
https: / / doi.org/ 10.1109 / FOCS.2018.00062
[107] Boaz Barak, Prasad Raghavendra en David Steurer. Afronding van semi-definitieve programmeerhiërarchieën via globale correlatie. In Proceedings van het tweeënvijftigste jaarlijkse symposium over de grondslagen van de informatica, pagina's 472-481. IEEE, 2011. 10.1109/FOCS.2011.95.
https: / / doi.org/ 10.1109 / FOCS.2011.95
[108] Samuel B. Hopkins, Tselil Schramm en Luca Trevisan. Subexponentiële LP's benaderen de max-cut. In Proceedings van het eenenzestigste jaarlijkse symposium over fundamenten van computerwetenschappen (FOCS), pagina's 943-953. IEEE, 2020. 10.1109/FOCS46700.2020.00092.
https://doi.org/10.1109/FOCS46700.2020.00092
[109] Albert Einstein, Boris Podolsky en Nathan Rosen. Kan de kwantummechanische beschrijving van de fysieke werkelijkheid als compleet worden beschouwd? Fys. Rev., 47 (10): 777, 1935. 10.1103/PhysRev.47.777.
https: / / doi.org/ 10.1103 / PhysRev.47.777
[110] Boris S. Cirelson. Kwantumgeneralisaties van de ongelijkheid van Bell. Let. Wiskunde. Phys., 4 (2): 93-100, 1980. 10.1007/BF00417500.
https: / / doi.org/ 10.1007 / BF00417500
[111] A. Natarajan en T. Vidick. Laaggradige testen voor kwantumtoestanden en een kwantumverstrengelde PCP-game voor QMA. In Proceedings of the nineth Annual Symposium on Foundations of Computer Science (FOCS), pagina's 731–742, 2018. 10.1109/FOCS.2018.00075.
https: / / doi.org/ 10.1109 / FOCS.2018.00075
[112] Dorit Aharonov, Itai Arad, Zeph Landau en Umesh Vazirani. Het detecteerbaarheidslemma en de versterking van de kwantumgap. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, pagina's 417-426, New York, NY, VS, 2009. Association for Computing Machinery. ISBN 9781605585062. 10.1145/1536414.1536472.
https: / / doi.org/ 10.1145 / 1536414.1536472
[113] Moses Charikar, Konstantin Makarychev en Yury Makarychev. Bijna optimale algoritmen voor unieke games. In Proceedings van het achtendertigste jaarlijkse ACM-symposium over Theory of computing, pagina's 205-214, 2006. 10.1145/1132516.1132547.
https: / / doi.org/ 10.1145 / 1132516.1132547
[114] Dimitris Achlioptas, Assaf Naor en Yuval Peres. Strenge locatie van faseovergangen in harde optimalisatieproblemen. Nature, 435 (7043): 759-764, 2005. 10.1038/nature03602.
https: / / doi.org/ 10.1038 / nature03602
[115] Don Coppersmith, David Gamarnik, Mohammad T. Hajiaghayi en Gregory B. Sorkin. Willekeurige MAX SAT, willekeurige MAX CUT en hun faseovergangen. Willekeurige structuur. Algoritmen, 24 (4): 502-545, 2004. 10.1002/rsa.20015.
https: / / doi.org/ 10.1002 / rsa.20015
Geciteerd door
[1] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong- Chuan Kwek en Alán Aspuru-Guzik, "Noisy intermediate-scale quantum (NISQ) algoritmen", arXiv: 2101.08448.
[2] Austin Gilliam, Stefan Woerner en Constantin Gonciulea, "Grover Adaptive Search for Constrained Polynomial Binary Optimization", arXiv: 1912.04088.
[3] Sergey Bravyi, Alexander Kliesch, Robert Koenig en Eugene Tang, "Hybride kwantumklassieke algoritmen voor geschatte grafiekkleuring", arXiv: 2011.13420.
[4] Amir M Aghaei, Bela Bauer, Kirill Shtengel en Ryan V. Mishmash, "Efficiënte voorbereiding van matrix-product-toestand van sterk verstrengelde proeftoestanden: zwakke Mott-isolatoren op het driehoekige rooster herzien", arXiv: 2009.12435.
[5] Stefan H. Sack en Maksym Serbyn, "Quantum-annealing-initialisatie van het kwantumbenaderende optimalisatie-algoritme", arXiv: 2101.05742.
[6] M. Werninghaus, DJ Egger en S. Filipp, "Hogesnelheidskalibratie en karakterisering van supergeleidende kwantumprocessors zonder Qubit-reset", PRX Quantum 2 2, 020324 (2021).
[7] Constantin Dalyac, Loïc Henriet, Emmanuel Jeandel, Wolfgang Lechner, Simon Perdrix, Marc Porcheron en Margarita Veshchezerova, "Kwalificerende kwantumbenaderingen voor harde industriële optimalisatieproblemen. Een case study op het gebied van slim opladen van elektrische voertuigen”, arXiv: 2012.14859.
[8] Sami Boulebnane, "Het verbeteren van het Quantum Approximate Optimization Algorithm met postselectie", arXiv: 2011.05425.
[9] Stuart M. Harwood, Dimitar Trenev, Spencer T. Stober, Panagiotis Barkoutsos, Tanvi P. Gujarati en Sarah Mostame, "Het verbeteren van de variatie-kwantum-eigensolver met behulp van variatie-adiabatische kwantumcomputing", arXiv: 2102.02875.
[10] Johanna Barzen, "Van Digital Humanities tot Quantum Humanities: Potentials and Applications", arXiv: 2103.11825.
[11] Jonathan Wurtz en Peter Love, "Klassiek optimale variatiekwantumalgoritmen", arXiv: 2103.17065.
[12] Ioannis Kolotouros en Petros Wallden, "Een evoluerende objectieve functie voor verbeterde variabele kwantumoptimalisatie", arXiv: 2105.11766.
Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2021-06-17 13:56:21). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.
Kon niet ophalen Door Crossref geciteerde gegevens tijdens laatste poging 2021-06-17 13:56:19: kon niet geciteerde gegevens voor 10.22331 / q-2021-06-17-479 niet ophalen van Crossref. Dit is normaal als de DOI recent is geregistreerd.
Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.
Coinsmart. Beste Bitcoin-beurs in Europa
Bron: https://quantum-journal.org/papers/q-2021-06-17-479/
