1IBM Quantum, IBM Research - Zürich, Säumerstrasse 4, 8803 Rüschlikon, Sveits
2Tsjekkiske tekniske universitet, Karlovo nam. 13, Praha 2, Tsjekkia
Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.
Abstrakt
Det er en økende interesse for kvantealgoritmer for problemer med heltallsprogrammering og kombinatorisk optimalisering. Klassiske løsere for slike problemer benytter avspenninger, som erstatter binære variabler med kontinuerlige, for eksempel i form av høyere dimensjonale matrisevurderte problemer (semidefinert programmering). Under Unique Games Conjecture gir disse avslapningene ofte de beste ytelsesforholdene som er tilgjengelige klassisk på polynomisk tid. Her diskuterer vi hvordan man kan starte opp kvanteoptimalisering med en starttilstand som tilsvarer løsningen på en avslapping av et kombinatorisk optimaliseringsproblem og hvordan man analyserer egenskapene til de tilknyttede kvantealgoritmene. Spesielt gjør dette at kvantealgoritmen kan arve ytelsesgarantiene til den klassiske algoritmen. Vi illustrerer dette i sammenheng med porteføljeoptimalisering, der resultatene våre indikerer at varmstart av Quantum Approximate Optimization Algorithm (QAOA) er spesielt gunstig ved lav dybde. På samme måte viser rekursiv QAOA for MAXCUT-problemer en systematisk økning i størrelsen på det oppnådde kuttet for fullkoblede grafer med tilfeldige vekter, når Goemans-Williamson randomisert avrunding brukes i en varm start. Det er greit å bruke de samme ideene på andre randomiserte avrundingsordninger og optimaliseringsproblemer.
Utvalgt bilde: Kvantakretsen til QAOA med varmstart.
Populært sammendrag
► BibTeX-data
► Referanser
[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 og et al. Kvanteoptimalisering ved hjelp av variasjonsalgoritmer på nærtids kvanteenheter. Quantum Sci. 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 og Jay M. Gambetta. Feilreduksjon utvider beregningsrekkevidden til en støyende kvanteprosessor. Nature, 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 og Stefan Filipp. Gateeffektiv simulering av molekylære egenstater på en kvantecomputer. Phys. Rev. Anvendt, 11: 044092, apr 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 og Seth Lloyd. Quantum maskinlæring. Natur, 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 og Jay M. Gambetta. Overvåket læring med kvanteforbedrede funksjonsrom. Nature, 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 og Elena Yndurain. Quantum computing for økonomi: Toppmoderne og fremtidsutsikter. IEEE Trans. på Quantum Eng., 1: 1–24, 2020. 10.1109 / TQE.2020.3030314.
https: / / doi.org/ 10.1109 / TQE.2020.3030314
[7] Stefan Woerner og Daniel J. Egger. Kvante risikoanalyse. 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 og Thomas R. Bromley. Kvantumberegningsfinansiering: Monte Carlo-prising av finansielle derivater. Phys. Rev. A, 98: 022321, aug 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 og Stefan Woerner. Prissetting av opsjoner ved hjelp av kvantecomputere. 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 og Mikel Sanz. Mot å prissette finansielle derivater med en IBM kvantecomputer. Phys. Rev. Research, 3: 013167, Feb 2021. 10.1103 / PhysRevResearch.3.013167.
https: / / doi.org/ 10.1103 / PhysRevResearch.3.013167
[11] Roman Orus, Samuel Mugel og Enrique Lizaso. Quantum computing for økonomi: Oversikt og potensielle kunder. 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 og Stefan Woerner. Kredittrisikoanalyse ved bruk av kvantecomputere. IEEE Trans. Beregning., 1: 1–1, nov 2020. 10.1109 / TC.2020.3038063.
https: / / doi.org/ 10.1109 / TC.2020.3038063
[13] Almudena Carrera Vazquez og Stefan Woerner. Effektiv tilstandsforberedelse for estimering av kvantamplitude. Phys. Rev. Anvendt, 15: 034027, mar 2021. 10.1103 / PhysRevApplied.15.034027.
https: / / doi.org/ 10.1103 / PhysRevApplied.15.034027
[14] Lee Braine, Daniel J. Egger, Jennifer Glick og Stefan Woerner. Kvantealgoritmer for blandet binær optimalisering brukes til transaksjonsoppgjør. IEEE Trans. på 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 og Stefan Woerner. Forbedre variasjonskvantumoptimalisering ved hjelp av cvar. Quantum, 4: 256, apr 2020. 10.22331 / q-2020-04-20-256.
https://doi.org/10.22331/q-2020-04-20-256
[16] Edward Farhi, Jeffrey Goldstone og Sam Gutmann. En kvantetilnærmet optimaliseringsalgoritme, 2014a. URL https: / / arxiv.org/ abs / 1411.4028.
arxiv: 1411.4028
[17] Edward Farhi, Jeffrey Goldstone og Sam Gutmann. En kvantetilnærmet optimaliseringsalgoritme brukt på et begrenset forekomstbegrensningsproblem, 2014b URL https: / / arxiv.org/ abs / 1412.6062.
arxiv: 1412.6062
[18] Zhi-Cheng Yang, Armin Rahmani, Alireza Shabani, Hartmut Neven og Claudio Chamon. Optimalisering av variasjonelle kvantealgoritmer ved bruk av pontryagins minimumsprinsipp. Phys. Rev. X, 7: 021027, mai 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, et al. Quantum gløding med produserte spinn. Nature, 473 (7346): 194–198, mai 2011. 10.1038 / nature10012.
https: / / doi.org/ 10.1038 / nature10012
[20] Glen Bigan Mbeng, Rosario Fazio og Giuseppe Santoro. Kvante annealing: en reise gjennom digitalisering, kontroll og hybrid kvantevariasjon, 2019. URL https: / / arxiv.org/ abs / 1906.08948.
arxiv: 1906.08948
[21] Michael Juenger, Elisabeth Lobe, Petra Mutzel, Gerhard Reinelt, Franz Rendl, Giovanni Rinaldi og Tobias Stollenwerk. Ytelse av en kvante annealer for Ising grunntilstandsberegninger på kimærgrafer, 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 og et al. Digitalisert adiabatisk kvanteberegning med en superledende krets. Nature, 534 (7606): 222–226, Jun 2016. 10.1038 / nature17658.
https: / / doi.org/ 10.1038 / nature17658
[23] Madita Willsch, Dennis Willsch, Fengping Jin, Hans De Raedt og Kristel Michielsen. Benchmarking av den tilnærmede optimaliseringsalgoritmen. Quantum Inf. Prosess., 19 (7): 197, Jun 2020. 10.1007 / s11128-020-02692-8.
https://doi.org/10.1007/s11128-020-02692-8
[24] Sergey Bravyi, Alexander Kliesch, Robert Koenig og Eugene Tang. Hindringer for variasjonell kvanteoptimalisering fra symmetribeskyttelse. Phys. Prest Lett., 125: 260505, des 2020a. 10.1103 / PhysRevLett.125.260505.
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
[25] Gavin E. Crooks. Ytelse for den kvante tilnærmede optimaliseringsalgoritmen på maksimalt kuttproblem, 2018. URL https: / / arxiv.org/ abs / 1811.08419.
arxiv: 1811.08419
[26] Edward Farhi, Jeffrey Goldstone, Sam Gutmann og Hartmut Neven. Kvantealgoritmer for faste qubit-arkitekturer, 2017. URL https: / / arxiv.org/ abs / 1703.06199.
arxiv: 1703.06199
[27] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor Rieffel, Davide Venturelli og Rupak Biswas. Fra den tilnærmede optimaliseringsalgoritmen til den kvante til en kvante alternerende operatør ansatz. Algoritmer, 12 (2): 34, feb 2019. 10.3390 / a12020034.
https: / / doi.org/ 10.3390 / a12020034
[28] Linghua Zhu, Ho Lun Tang, George S. Barron, Nicholas J. Mayhall, Edwin Barnes og Sophia E. Economou. En adaptiv kvantetilnærmet optimaliseringsalgoritme for å løse kombinatoriske problemer på en kvantecomputer, 2020. URL https: / / arxiv.org/ abs / 2005.10258.
arxiv: 2005.10258
[29] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy og Eleanor G. Rieffel. XY-miksere: Analytiske og numeriske resultater for den kvante alternerende operatøren ansatz. Phys. Rev. A, 101: 012320, jan 2020. 10.1103 / PhysRevA.101.012320.
https: / / doi.org/ 10.1103 / PhysRevA.101.012320
[30] Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev og Prasanna Balaprakash. Lære å optimalisere variasjonelle kvantekretser for å løse kombinatoriske problemer. Proceedings of the AAAI Conference on Artificial Intelligence, 34 (03): 2367–2375, Apr 2020. 10.1609 / aaai.v34i03.5616.
https: / / doi.org/ 10.1609 / aaai.v34i03.5616
[31] Matteo M. Wauters, Emanuele Panizon, Glen B. Mbeng og Giuseppe E. Santoro. Forsterkning-læringsassistert kvanteoptimalisering. Phys. Rev. Research, 2: 033446, sep 2020. 10.1103 / PhysRevResearch.2.033446.
https: / / doi.org/ 10.1103 / PhysRevResearch.2.033446
[32] Ruslan Shaydulin, Ilya Safro og Jeffrey Larson. Multistart-metoder for kvantumtilnærmet optimalisering. 2019 IEEE High Performance Extreme Computing Conference (HPEC), side 1–8, september 2019. 10.1109 / HPEC.2019.8916288.
https: / / doi.org/ 10.1109 / HPEC.2019.8916288
[33] Ruslan Shaydulin og Yuri Alexeev. Evaluering av kvantetilnærmet optimaliseringsalgoritme: En casestudie. I 2019 Tiende internasjonale grønne og bærekraftige databehandlingskonferanse (IGSC), side 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 og Henry Yuen. Utforske forvikling og optimalisering innen den Hamilton-variasjonelle ansatz. PRX Quantum, 1: 020319, des 2020. 10.1103 / PRXQuantum.1.020319.
https: / / doi.org/ 10.1103 / PRXQuantum.1.020319
[35] Fernando GSL Brandao, Michael Broughton, Edward Farhi, Sam Gutmann og Hartmut Neven. For faste kontrollparametere konsentrerer den kvante tilnærmet optimaliseringsalgoritmens objektive funksjonsverdi seg for typiske tilfeller, 2018. URL https: / / arxiv.org/ abs / 1812.04170.
arxiv: 1812.04170
[36] Matthew B. Hastings. Klassiske algoritmer for tilnærming av dybde og kvanteavgrensning, 2019. URL https: / / arxiv.org/ abs / 1905.07047.
arxiv: 1905.07047
[37] Sergey Bravyi, Alexander Kliesch, Robert Koenig og Eugene Tang. Hybrid kvanteklassiske algoritmer for omtrentlig graffarging, 2020b. URL https: / / arxiv.org/ abs / 2011.13420.
arxiv: 2011.13420
[38] Mahabubul Alam, Abdullah Ash-Saki og Swaroop Ghosh. Analyse av kvantetilnærmet optimaliseringsalgoritme under realistisk støy i superledende qubits, 2019. URL https: / / arxiv.org/ abs / 1907.09631.
arxiv: 1907.09631
[39] Vishwanathan Akshay, Hariphan Philathong, Mauro ES Morales og Jacob D. Biamonte. Reachability underskudd i kvante tilnærmet optimalisering. Phys. Prest Lett., 124: 090504, mar 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 og et al. Kvantumtilnærmet optimalisering av ikke-plane grafproblemer på en plan superledende prosessor. Nat. Phys., 17 (3): 332–336, Mar 2021. 10.1038 / s41567-020-01105-y.
https: / / doi.org/ 10.1038 / s41567-020-01105-y
[41] Yulong Dong, Xiang Meng, Lin Lin, Robert Kosut og K. Birgitta Whaley. Robust kontrolloptimalisering for kvante omtrentlige optimaliseringsalgoritmer. IFAC-PapersOnLine, 53 (2): 242-249, 2020. 10.1016 / j.ifacol.2020.12.130. 21. IFAC verdens kongress.
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 og et al. Forbedre ytelsen til dype kvanteoptimaliseringsalgoritmer med kontinuerlige portsett. PRX Quantum, 1: 110304, okt 2020. 10.1103 / PRXQuantum.1.020304.
https: / / doi.org/ 10.1103 / PRXQuantum.1.020304
[43] Nathan Earnest, Caroline Tornow og Daniel J. Egger. Pulseffektiv kretstranspilering for kvanteapplikasjoner på kryssresonansbasert maskinvare, 2021. URL https: / / arxiv.org/ abs / 2105.01063.
arxiv: 2105.01063
[44] Pranav Gokhale, Ali Javadi-Abhari, Nathan Earnest, Yunong Shi og Frederic T. Chong. Optimalisert kvantesammensetning for kortvarige algoritmer med 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 og et al. Qiskit backend spesifikasjoner for OpenQASM og OpenPulse eksperimenter, 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 og David C. McKay. Qiskit-puls: programmering av kvantedatamaskiner gjennom skyen med pulser. Quantum Sci. Technol., 5 (4): 044006, aug 2020. 10.1088 / 2058-9565 / aba404.
https: / / doi.org/ 10.1088 / 2058-9565 / aba404
[47] Anirudha Majumdar, Georgina Hall og Amir Ali Ahmadi. Nylige forbedringer av skalerbarhet for semi-definert programmering med applikasjoner innen maskinlæring, kontroll og robotikk. Annu. Rev. Control 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 og Jean B. Lasserre. Håndbok om semidefinite, conic and polynomial optimization, bind 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 og Steve Smale. Kompleksitet og reell beregning. 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 og Leonid Khachiyan. Om kompleksiteten til semidefinitive programmer. J. Glob. Optim., 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 og Volkan Cevher. Skalerbar semifinitiv programmering. SIAM J. Math. Data Sci., 3 (1): 171-200, 2021. 10.1137 / 19M1305045.
https: / / doi.org/ 10.1137 / 19M1305045
[52] Prabhakar Raghavan og Clark D. Tompson. Randomisert avrunding: En teknikk for beviselig gode algoritmer og algoritmiske bevis. Combinatorica, 7 (4): 365–374, desember 1987. 10.1007 / BF02579324.
https: / / doi.org/ 10.1007 / BF02579324
[53] Michel X. Goemans og David P. Williamson. Forbedrede tilnærmelsesalgoritmer for maksimale kutt- og tilfredsstillelsesproblemer ved bruk av semidefinert programmering. J. ACM, 42 (6): 1115–1145, nov 1995. 10.1145 / 227683.227684.
https: / / doi.org/ 10.1145 / 227683.227684
[54] Howard Karloff. Hvor god er Goemans – Williamson MAX CUT-algoritmen? SIAM J. Comput., 29 (1): 336-350, 1999. 10.1137 / S0097539797321481.
https: / / doi.org/ 10.1137 / S0097539797321481
[55] Subhash Khot, Guy Kindler, Elchanan Mossel og Ryan O'Donnell. Optimale resultater for utilnærmelighet for MAX-CUT og andre 2-variable CSP-er? SIAM J. Comput., 37 (1): 319–357, 2007. 10.1137 / S0097539705447372.
https: / / doi.org/ 10.1137 / S0097539705447372
[56] Subhas Khot. På den unike spillgissingen (invitert undersøkelse). I 2012 IEEE 27. konferanse om beregningskompleksitet, side 99–121, Los Alamitos, CA, USA, juni 2010. IEEE Computer Society. 10.1109 / CCC.2010.19.
https: / / doi.org/ 10.1109 / CCC.2010.19
[57] Subhash A. Khot og Nisheeth K. Vishnoi. Den unike spekulasjonen, integritetsgapet for kuttproblemer og innebygging av beregninger av negativ type til 1. J. ACM, 62 (1): 1–39, 2015. 10.1145 / 2629614.
https: / / doi.org/ 10.1145 / 2629614
[58] Kunal Marwaha. Lokal klassisk MAX-CUT-algoritme overgår $ p = 2 $ QAOA på vanlige grafer med høy omkrets. 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 og Sergiu Rudeanu. Boolske metoder i operasjonsforskning og relaterte områder. 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. En MAX-CUT-formulering av 0/1-programmer. Oper. Res. 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 og Georg Schnitger. Å sjekke lokal optimalitet i begrenset kvadratisk programmering er np-vanskelig. Oper. Res. 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 og Erich Steiner. Et polynomisk tilfelle av ubegrenset null-en kvadratisk optimalisering. Matte. Program., 91 (1): 49–52, 2001. 10.1007 / s101070100233.
https: / / doi.org/ 10.1007 / s101070100233
[63] Milan Hladík, Michal Černý og Miroslav Rada. En ny polynomisk løsbar klasse av kvadratiske optimaliseringsproblemer med boksbegrensninger. arXiv: 1911.10877, 2019. URL https: / / arxiv.org/ abs / 1911.10877.
arxiv: 1911.10877
[64] Jacek Gondzio og Andreas Grothey. Løse ulineære økonomiske planleggingsproblemer med $ 10 ^ 9 $ beslutningsvariabler på massivt parallelle arkitekturer. WIT Trans Modeling Simul., 43: 11, 2006. 10.2495 / CF060101.
https: / / doi.org/ 10.2495 / CF060101
[65] Svatopluk Poljak, Franz Rendl og Henry Wolkowicz. En oppskrift på halvfint avslapning for (0, 1) -kvadratisk programmering. J. Glob. Optim., 7 (1): 51–73, 1995. 10.1007 / BF01100205.
https: / / doi.org/ 10.1007 / BF01100205
[66] Joran Van Apeldoorn, András Gilyén, Sander Gribling og Ronald de Wolf. Quantum SDP-løsere: Bedre øvre og nedre grenser. 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 og Xiaodi Wu. Quantum SDP Solvers: Store Speed-Ups, optimalitet og applikasjoner for Quantum Learning. I 46. internasjonalt kollokvium om automata, språk og programmering (ICALP 2019), bind 132 av Leibniz International Proceedings in Informatics (LIPIcs), side 27: 1–27: 14, Dagstuhl, Tyskland, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 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 og Chunhao Wang. Kvanteinspirert sublinear algoritme for å løse lavrangerte semidefinit programmering. I 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), bind 170 av Leibniz International Proceedings in Informatics (LIPIcs), side 23: 1–23: 15, Dagstuhl, Tyskland, 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. Varm start på primal-dual-metoden som brukes i skjæreplanskjemaet. Matte. Program., 83 (1-3): 125–143, 1998. 10.1007 / BF02680554.
https: / / doi.org/ 10.1007 / BF02680554
[70] Andrew Lucas. Ising formuleringer av mange NP-problemer. Front. Phys., 2: 5, 2014. 10.3389 / fphy.2014.00005.
https: / / doi.org/ 10.3389 / fphy.2014.00005
[71] Bas Lodewijks. Kartlegging av np-harde og NP-komplette optimaliseringsproblemer til kvadratiske ubegrensede binære optimaliseringsproblemer. arXiv: 1911.08043, 2019. URL https: / / arxiv.org/ abs / 1911.08043.
arxiv: 1911.08043
[72] Jean B. Lasserre. Global optimalisering med polynomer og øyeblikkets problem. SIAM J. Optim., 11 (3): 796–817, 2001. 10.1137 / S1052623400366802.
https: / / doi.org/ 10.1137 / S1052623400366802
[73] Jean B. Lasserre. Konvergente SDP-avslapping i polynomoptimalisering med sparsitet. SIAM J. Optim., 17 (3): 822–843, 2006. 10.1137 / 05064504X.
https: / / doi.org/ 10.1137 / 05064504X
[74] Bissan Ghaddar, Juan C. Vera og Miguel F. Anjos. Andreordens kjegleavslapping for binære kvadratiske polynomprogrammer. SIAM J. Optim., 21 (1): 391-414, 2011. 10.1137 / 100802190.
https: / / doi.org/ 10.1137 / 100802190
[75] Moses Charikar og Anthony Wirth. Maksimering av kvadratiske programmer: Utvide Grothendiecks ulikhet. I det 45. årlige IEEE-symposiet om grunnlag for datalogi, side 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 og Martin Takáč. Entropipenalisert semidefinit programmering. In Proceedings of the Twenty-Eight International Joint Conference on Artificial Intelligence, 2019. 10.24963 / ijcai.2019 / 157.
https: / / doi.org/ 10.24963 / ijcai.2019 / 157
[77] Sartaj Sahni og Teofilo Gonzalez. P-komplette tilnærmingsproblemer. J. ACM, 23 (3): 555–565, 1976. 10.1145 / 321958.321975. Se Lemma A2.
https: / / doi.org/ 10.1145 / 321958.321975
[78] Michael Mitzenmacher og Eli Upfal. Sannsynlighet og databehandling: Randomisering og sannsynlighetsteknikker i algoritmer og dataanalyse. Cambridge universitetspresse, 2017.
[79] Sepehr Abbasi-Zadeh, Nikhil Bansal, Guru Guruganesh, Aleksandar Nikolov, Roy Schwartz og Mohit Singh. Klebrig brownian-avrunding og dens applikasjoner for å begrense tilfredsstillelsesproblemer. I Proceedings of the Fourtenth Annual ACM-SIAM Symposium on Discrete Algorithms, side 854–873. SIAM, 2020. 10.1137 / 1.9781611975994.52.
https: / / doi.org/ 10.1137 / 1.9781611975994.52
[80] Ronen Eldan og Assaf Naor. Krivine-diffusjoner oppnår tilnærmelsesforholdet goemans – williamson. arXiv: 1906.10615, 2019. URL https: / / arxiv.org/ abs / 1906.10615.
arxiv: 1906.10615
[81] Jamie Morgenstern, Samira Samadi, Mohit Singh, Uthaipon Tantipongpipat og Santosh Vempala. Rettferdig dimensjonsreduksjon og iterativ avrunding for SDPer. arXiv: 1902.11281, 2019. URL https: / / arxiv.org/ abs / 1902.11281v1.
arxiv: 1902.11281
[82] Samuel Karlin og Howard E. Taylor. Et andre kurs i stokastiske prosesser. Elsevier, 1981. s. 257 og det følgende.
[83] Julia Kempe, Oded Regev og Ben Toner. Den unike spillgissingen med sammenfiltrede provers er falsk. I algebraiske metoder i beregningskompleksitet, 2007.
[84] Julia Kempe, Oded Regev og Ben Toner. Unike spill med sammenfiltrede provers er enkle. 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 og Umesh Vazirani. Styrker og svakheter ved kvanteberegning. SIAM J. Comput., 26 (5): 1510-1523, 1997. 10.1137 / S0097539796300933.
https: / / doi.org/ 10.1137 / S0097539796300933
[86] Harry Markowitz. Porteføljevalg. J. Finance, 7 (1): 77–91, 1952. 10.2307 / 2975974.
https: / / doi.org/ 10.2307 / 2975974
[87] H. Abraham et al. Qiskit: Et open source-rammeverk for kvanteberegning, 2019. URL https: / / doi.org/ 10.5281 / zenodo.2562111.
https: / / doi.org/ 10.5281 / zenodo.2562111
[88] Johan Håstad. Noen optimale utilgjengelighetsresultater. 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 og Jacob D. Biamonte. Reachability underskudd implisitt i Googles kvante tilnærmet optimalisering av grafproblemer, 2020b. URL https: / / arxiv.org/ abs / 2007.09148.
arxiv: 2007.09148
[90] Rebekah Herrman, James Ostrowski, Travis S. Humble og George Siopsis. Lavere grenser på kretsdybden til den tilnærmet optimaliseringsalgoritmen. Quantum Inf. Prosess., 20 (2): 59, feb 2021. 10.1007 / s11128-021-03001-7.
https://doi.org/10.1007/s11128-021-03001-7
[91] Zhihui Wang, Stuart Hadfield, Zhang Jiang og Eleanor G. Rieffel. Kvantlig tilnærmet optimaliseringsalgoritme for maxcut: En fermionisk visning. Phys. Rev. A, 97: 022304, feb 2018. 10.1103 / PhysRevA.97.022304.
https: / / doi.org/ 10.1103 / PhysRevA.97.022304
[92] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler og Mikhail D. Lukin. Kvantumtilnærmet optimaliseringsalgoritme: Ytelse, mekanisme og implementering på nærtidsenheter. Phys. Rev. X, 10: 021067, Jun 2020. 10.1103 / PhysRevX.10.021067.
https: / / doi.org/ 10.1103 / PhysRevX.10.021067
[93] Jason Larkin, Matías Jonsson, Daniel Justice og Gian Giacomo Guerreschi. Evaluering av tilnærmet optimaliseringsalgoritme basert på kvantum basert på tilnærmelsesforholdet for enkeltprøver, 2020. URL https: / / arxiv.org/ abs / 2006.04831.
arxiv: 2006.04831
[94] qiskit-optimalisering. https: / / github.com/ Qiskit / qiskit-optimalisering. Tilgang: 25. 04. 2021.
https: / / github.com/ Qiskit / qiskit-optimalisering
[95] Andreas Bärtschi og Stephan Eidenbenz. Grover-miksere for qaoa: Skiftende kompleksitet fra mikserdesign til klargjøring av staten. I 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), side 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 og Swati Gupta. Bruer klassisk og kvante med SDP initialiserte oppstart for QAOA, 2020. URL https: / / arxiv.org/ abs / 2010.14021.
arxiv: 2010.14021
[97] Iain Dunning, Swati Gupta og John Silberholz. Hva fungerer best når? en systematisk evaluering av heuristikker for Max-Cut og QUBO. INFORMS 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 og et al. Kvantealgoritmer for elektroniske strukturberegninger: Partikkelhulls Hamilton og optimaliserte bølgefunksjonsutvidelser. Phys. Rev. A, 98: 022322, aug 2018. 10.1103 / PhysRevA.98.022322.
https: / / doi.org/ 10.1103 / PhysRevA.98.022322
[99] Sanjeev Arora og Shmuel Safra. Probabilistisk kontroll av bevis: En ny karakterisering av 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 og Mario Szegedy. Bevisverifisering og hardheten til tilnærmingsproblemer. J. ACM, 45 (3): 501–555, 1998. 10.1145 / 278298.278306.
https: / / doi.org/ 10.1145 / 278298.278306
[101] Irit Dinur. PCP-teoremet ved gapforsterkning. J. ACM, 54 (3): 12 – es, jun 2007. 10.1145 / 1236457.1236459.
https: / / doi.org/ 10.1145 / 1236457.1236459
[102] Sanjeev Arora og Boaz Barak. Beregningskompleksitet: en moderne tilnærming. Cambridge University Press, 2009.
[103] Subhash Khot. På kraften til unike 2-prover 1-runde spill. I Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, STOC '02, side 767–775, New York, NY, USA, 2002. Association for Computing Machinery. 10.1145 / 509907.510017.
https: / / doi.org/ 10.1145 / 509907.510017
[104] Prasad Raghavendra. Optimale algoritmer og utilgjengelighetsresultater for hver CSP? I Proceedings of the fortieth annual ACM symposium on Theory of computing, side 245–254, 2008. 10.1145 / 1374376.1374414.
https: / / doi.org/ 10.1145 / 1374376.1374414
[105] Prasad Raghavendra og David Steurer. Hvordan runde en hvilken som helst CSP. I 2009 50. årlige IEEE Symposium on Foundations of Computer Science, side 586–594, 2009. 10.1109 / FOCS.2009.74.
https: / / doi.org/ 10.1109 / FOCS.2009.74
[106] Subhash Khot, Dor Minzer og Muli Safra. Pseudorandom-sett i grassmann-graf har nesten perfekt utvidelse. I Proceedings of the fifty-ninth Annual Symposium on Foundations of Computer Science (FOCS), side 592–601, 2018. 10.1109 / FOCS.2018.00062.
https: / / doi.org/ 10.1109 / FOCS.2018.00062
[107] Boaz Barak, Prasad Raghavendra og David Steurer. Avrunding av semidefinerte programmeringshierarkier via global korrelasjon. I Proceedings of the fiftysecond annual symposium on fondations of computer science, side 472–481. IEEE, 2011. 10.1109 / FOCS.2011.95.
https: / / doi.org/ 10.1109 / FOCS.2011.95
[108] Samuel B. Hopkins, Tselil Schramm og Luca Trevisan. Subexponential LP er omtrent maks. I Proceedings of the sixtyfirst Annual Symposium on Foundations of Computer Science (FOCS), side 943–953. IEEE, 2020. 10.1109 / FOCS46700.2020.00092.
https: / / doi.org/ 10.1109 / FOCS46700.2020.00092
[109] Albert Einstein, Boris Podolsky og Nathan Rosen. Kan kvantemekanisk beskrivelse av fysisk virkelighet betraktes som fullstendig? Phys. Rev., 47 (10): 777, 1935. 10.1103 / PhysRev.47.777.
https: / / doi.org/ 10.1103 / PhysRev.47.777
[110] Boris S. Cirel'son. Kvantale generaliseringer av Bells ulikhet. Lett. Matte. Phys., 4 (2): 93–100, 1980. 10.1007 / BF00417500.
https: / / doi.org/ 10.1007 / BF00417500
[111] A. Natarajan og T. Vidick. Lavgradstesting for kvantetilstander, og et kvantviklet spill PCP for QMA. I Proceedings of the fiftyninth Annual Symposium on Foundations of Computer Science (FOCS), side 731–742, 2018. 10.1109 / FOCS.2018.00075.
https: / / doi.org/ 10.1109 / FOCS.2018.00075
[112] Dorit Aharonov, Itai Arad, Zeph Landau og Umesh Vazirani. Detekterbarhetslemmaet og forsterkning av kvantegapet. I Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, side 417–426, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 9781605585062. 10.1145 / 1536414.1536472.
https: / / doi.org/ 10.1145 / 1536414.1536472
[113] Moses Charikar, Konstantin Makarychev og Yury Makarychev. Nesten optimale algoritmer for unike spill. I Proceedings of the eighty-eight year ACM symposium on Theory of computing, side 205–214, 2006. 10.1145 / 1132516.1132547.
https: / / doi.org/ 10.1145 / 1132516.1132547
[114] Dimitris Achlioptas, Assaf Naor og Yuval Peres. Rigorøs plassering av faseoverganger i harde optimaliseringsproblemer. Nature, 435 (7043): 759–764, 2005. 10.1038 / nature03602.
https: / / doi.org/ 10.1038 / nature03602
[115] Don Coppersmith, David Gamarnik, Mohammad T. Hajiaghayi og Gregory B. Sorkin. Tilfeldig MAX SAT, random MAX CUT og deres faseoverganger. Tilfeldig struktur. Algoritmer, 24 (4): 502–545, 2004. 10.1002 / rsa.20015.
https: / / doi.org/ 10.1002 / rsa.20015
Sitert av
[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, og Alán Aspuru-Guzik, “Noisy intermediate-scale quantum (NISQ) algorithms”, arxiv: 2101.08448.
[2] Austin Gilliam, Stefan Woerner og Constantin Gonciulea, "Grover Adaptive Search for Constrained Polynomial Binary Optimization", arxiv: 1912.04088.
[3] Sergey Bravyi, Alexander Kliesch, Robert Koenig og Eugene Tang, "Hybrid kvanteklassiske algoritmer for tilnærmet graffarging", arxiv: 2011.13420.
[4] Amir M Aghaei, Bela Bauer, Kirill Shtengel og Ryan V. Mishmash. arxiv: 2009.12435.
[5] Stefan H. Sack og Maksym Serbyn, "Initiering av kvant annealing av den tilnærmede optimaliseringsalgoritmen", arxiv: 2101.05742.
[6] M. Werninghaus, DJ Egger og S. Filipp, "Høyhastighets kalibrering og karakterisering av superledende kvanteprosessorer uten Qubit Reset", PRX Quantum 2 2, 020324 (2021).
[7] Constantin Dalyac, Loïc Henriet, Emmanuel Jeandel, Wolfgang Lechner, Simon Perdrix, Marc Porcheron og Margarita Veshchezerova, “Kvalifiserende kvantemetoder for harde industrielle optimaliseringsproblemer. En casestudie innen smartlading av elbiler ”, arxiv: 2012.14859.
[8] Sami Boulebnane, “Forbedring av den tilnærmede optimaliseringsalgoritmen for kvante med postseleksjon”, arxiv: 2011.05425.
[9] Stuart M. Harwood, Dimitar Trenev, Spencer T. Stober, Panagiotis Barkoutsos, Tanvi P. Gujarati og Sarah Mostame, "Improving the variational quantum eigensolver using variational adiabatic quantum computing", arxiv: 2102.02875.
[10] Johanna Barzen, "Fra digitale humaniora til kvante humaniora: potensialer og applikasjoner", arxiv: 2103.11825.
[11] Jonathan Wurtz og Peter Love, "Klassisk optimale variasjonelle kvantealgoritmer", arxiv: 2103.17065.
[12] Ioannis Kolotouros og Petros Wallden, "En utviklende objektiv funksjon for forbedret variasjonell kvanteoptimalisering", arxiv: 2105.11766.
Sitatene ovenfor er fra SAO / NASA ADS (sist oppdatert vellykket 2021-06-17 13:56:21). Listen kan være ufullstendig fordi ikke alle utgivere gir passende og fullstendige sitasjonsdata.
Kunne ikke hente Crossref sitert av data under siste forsøk 2021-06-17 13:56:19: Kunne ikke hente siterte data for 10.22331 / q-2021-06-17-479 fra Crossref. Dette er normalt hvis DOI nylig ble registrert.
Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.
Myntsmart. Beste Bitcoin-Börse i Europa
Kilde: https://quantum-journal.org/papers/q-2021-06-17-479/
