Quantum Goemansi-Williamsoni algoritm Hadamardi testi ja ligikaudsete amplituudipiirangutega

Taasavaldanud Platon

järgijaid: 0

Taylor L. Patti^1,2, Jean Kossaifi², Anima Anandkumar^3,2ja Susanne F. Yelin¹

¹Harvardi ülikooli füüsika osakond, Cambridge, Massachusetts 02138, USA
²NVIDIA, Santa Clara, California 95051, USA
³Arvutus- ja matemaatikateaduste osakond (CMS), California Tehnoloogiainstituut (Caltech), Pasadena, CA 91125 USA

Kas see artikkel on huvitav või soovite arutada? Scite või jätke SciRate'i kommentaar.

Abstraktne

Poolkindlad programmid on optimeerimismeetodid, millel on lai valik rakendusi, näiteks keeruliste kombinatoorsete probleemide lähendamine. Üks sellistest poolkindlatest programmidest on Goemansi-Williamsoni algoritm, populaarne täisarvude lõdvestamise tehnika. Tutvustame Goemansi-Williamsoni algoritmi variatsioonilist kvantalgoritmi, mis kasutab poolkindlate programmide ligikaudseks lahendamiseks ainult $n{+}1$ kubitti, konstantset arvu ahela ettevalmistusi ja $text{poly}(n)$ ootusväärtusi kuni $N=2^n$ muutujate ja $M sim O(N)$ piirangutega. Tõhus optimeerimine saavutatakse objektiivse maatriksi kodeerimisega õigesti parameetritega unitaarina, mis on tingitud abikubitist, tehnikast, mida tuntakse Hadamardi testina. Hadamardi test võimaldab meil optimeerida sihtfunktsiooni, hinnates ainult ühe lisakubiti ootusväärtust, selle asemel, et hinnata eraldi eksponentsiaalselt palju ootusväärtusi. Samamoodi illustreerime, et poolkindlaid programmeerimispiiranguid saab tõhusalt jõustada teise Hadamardi testi rakendamisega, samuti Pauli stringi amplituudipiirangute polünoomilise arvu kehtestamisega. Näitame oma protokolli tõhusust, töötades välja Goemansi-Williamsoni algoritmi tõhusa kvantrakenduse erinevate NP-raskete probleemide jaoks, sealhulgas MaxCut. Meie meetod ületab analoogsete klassikaliste meetodite jõudlust GSeti raamatukogu hästi uuritud MaxCuti probleemide alamhulga puhul.

Kvant-Goemansi-Williamsoni algoritm Hadamardi testi ja ligikaudsete amplituudipiirangutega PlatoBlockchain andmeintellektiga. Vertikaalne otsing. Ai.

Esiletõstetud pilt: HTAAC-QSDP diagramm Goemansi-Williamsoni algoritmi jaoks $n=3$ mitteabikubitiga. a) Klassikaline $N$ muutujate probleem (siin $N$ tipu MaxCut ülesanne, kus $N=8$). Ühtsuse $U_W$ genereerimiseks kasutatakse kaalumaatriksit $W$. b) Hadamardi testi kasutatakse eesmärgifunktsiooni ja populatsiooni tasakaalustamise piirangute tõhusaks hindamiseks. $n$-qubit olek $|psirangle = U_V|mathbf{0}rangle$ valmistatakse ette variatsioonilise kvantahelaga $U_V$. $n+1$th (abi) qubit lähtestatakse kujul $(|0rangle -i |1rangle)/sqrt{2}$. Seejärel viiakse läbi Hadamardi test: $U_W$ rakendatakse juhitava ühikuna, mis on tingitud abikubitist, mida seejärel mõõdetakse, et arvutada $langle sigma_{n+1} rangle_{W,t} = text{Im} [langle psi|U_W|psi rangle]$ või $langle sigma_{n+1} rangle_{P,t} = tekst{Im}[langle psi|U_P|psi rangle]$. c) $M=2^n$ SDP amplituudipiirangute piirangud jõustatakse ligikaudu ainult $m sim text{poly}(n)$ Pauli stringipiirangutega. Nende arvutamiseks kogutakse $n$-qubit Pauli-$z$ mõõtmised ja kasutatakse marginaalset statistikat, et hinnata $m$ ootusväärtusi.

Populaarne kokkuvõte

Poolkindlad programmid võimaldavad meil ligikaudselt hinnata suurt hulka raskeid probleeme, sealhulgas NP-rasked probleeme. Üks selline poolkindel programm on Goemansi-Williamsoni algoritm, mis suudab lahendada raskeid probleeme, näiteks MaxCut. Tutvustame Goemansi-Williamsoni algoritmi variatsioonilist kvantalgoritmi, mis kasutab ainult $n{+}1$ kubitti, konstantset arvu ahela ettevalmistusi ja polünoomilist arvu ootusväärtusi, et ligikaudu lahendada poolkindlaid programme eksponentsiaalse arvuga muutujad ja piirangud. Kodeerime probleemi kvantahelasse (või ühtsesse) ja loeme selle välja ühe abikubiidi abil, tehnikat, mida tuntakse Hadamardi testina. Samamoodi illustreerime, et probleemipiiranguid saab jõustada 1) teise Hadamardi testiga ja 2) Pauli stringipiirangute polünoomilise arvuga. Näitame oma protokolli tõhusust, töötades välja Goemansi-Williamsoni algoritmi tõhusa kvantrakenduse erinevate NP-raskete probleemide jaoks, sealhulgas MaxCut. Meie meetod ületab analoogsete klassikaliste meetodite jõudlust hästi uuritud MaxCuti probleemide alamhulga puhul.

► BibTeX-i andmed

@artikkel{Patti2023quantumgoemans, doi = {10.22331/q-2023-07-12-1057}, url = {https://doi.org/10.22331/q-2023-07-12-1057}, pealkiri { = {Quantum G}oemansi-{W}illiamsoni {A}lgoritm {H}adamardi {T}esti ja {A}ligikaudse {A}mplituudi {C}piiranguga}, autor = {Patti, Taylor L. ja Kossaifi, Jean ja Anandkumar, Anima ja Yelin, Susanne F.}, ajakiri = {{Quantum}}, issn = {2521-327X}, väljaandja = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}} , maht = {7}, leheküljed = {1057}, kuu = juuli, aasta = {2023} }

► Viited

[1] Stephen P. Boyd ja Lieven Vandenberghe. "Kumer optimeerimine". Cambridge Press. (2004).
https:///doi.org/10.1017/CBO9780511804441

[2] Michel X. Goemans. "Pooldefineeritud programmeerimine kombinatoorses optimeerimises". Mathematical Programming 79, 143–161 (1997).
https:///doi.org/10.1007/BF02614315

[3] Lieven Vandenberghe ja Stephen Boyd. "Poolkindla programmeerimise rakendused". Rakendusarvuline matemaatika 29, 283–299 (1999).
https://doi.org/10.1016/S0168-9274(98)00098-1

[4] Wenjun Li, Yang Ding, Yongjie Yang, R. Simon Sherratt, Jong Hyuk Park ja Jin Wang. Põhiliste np-raskete probleemide parameetrilised algoritmid: uuring. Inimkesksed arvuti- ja infoteadused 10, 29 (2020).
https:///doi.org/10.1186/s13673-020-00226-w

[5] Christoph Helmberg. "Pooldefineeritud programmeerimine kombinatoorseks optimeerimiseks". Konrad-Zuse-Zentrum fur Informationstechnik Berlin. (2000).
https:///doi.org/10.1007/BF02614315

[6] Michel X. Goemans ja David P. Williamson. "Täiustatud lähendusalgoritmid maksimaalse lõikamise ja rahuldamisprobleemide jaoks, kasutades poolkindlat programmeerimist". J. ACM, 42, 1115–1145 (1995).
https:///doi.org/10.1145/227683.227684

[7] Florian A. Potra ja Stephen J. Wright. "Sisepunkti meetodid". Journal of Computational and Applied Mathematics 124, 281–302 (2000).
https://doi.org/10.1016/S0377-0427(00)00433-7

[8] Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan ja Zhao Song. "Kiirem sisepunkti meetod poolkindlaks programmeerimiseks". 2020. aastal toimub IEEE 61. iga-aastane arvutiteaduse aluste sümpoosion (FOCS). Lk 910–918. IEEE (2020).
https:///doi.org/10.1109/FOCS46700.2020.00089

[9] Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao ja Ruizhe Zhang. "SDP kiirem lahendamine: tugev ipm-raamistik ja tõhus rakendamine". 2022. aastal toimub IEEE 63. iga-aastane arvutiteaduse aluste sümpoosion (FOCS). Lk 233–244. IEEE (2022).
https:///doi.org/10.1109/FOCS54457.2022.00029

[10] David P. Williamson ja David B. Shmoys. "Lähendusalgoritmide disain". Cambridge University Press. (2011).
https:///doi.org/10.1017/CBO9780511921735

[11] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn jt. "Kvantoptimeerimine lühiajaliste kvantseadmete variatsioonialgoritmide abil". Quantum Science and Technology 3, 030503 (2018).
https:///doi.org/10.1088/2058-9565/aab822

[12] Edward Farhi, Jeffrey Goldstone, Sam Gutmann ja Michael Sipser. "Kvantarvutus adiabaatilise evolutsiooni abil" (2000). arXiv:quant-ph/0001106.
arXiv:quant-ph/0001106

[13] Tameem Albash ja Daniel A. Lidar. "Adiabaatiline kvantarvutus". Rev. Mod. Phys. 90, 015002 (2018).
https:///doi.org/10.1103/RevModPhys.90.015002

[14] Sepehr Ebadi, Alexander Keesling, Madelyn Cain, Tout T Wang, Harry Levine, Dolev Bluvstein, Giulia Semeghini, Ahmed Omran, JG Liu, Rhine Samajdar jt. "Maksimaalse sõltumatu komplekti kvantoptimeerimine Rydbergi aatomimassiivide abil". Science 376, 1209–1215 (2022).
https:///doi.org/10.1126/science.abo6587

[15] Tadashi Kadowaki ja Hidetoshi Nishimori. "Kvantlõõmutamine põiksuunalises mudelis". Phys. Rev. E 58, 5355–5363 (1998).
https:///doi.org/10.1103/PhysRevE.58.5355

[16] Elizabeth Gibney. "D-laine uuendus: kuidas teadlased kasutavad maailma kõige vastuolulisemat kvantarvutit". Loodus 541 (2017).
https:///doi.org/10.1038/541447b

[17] Edward Farhi, Jeffrey Goldstone ja Sam Gutmann. "Kvantligikaudne optimeerimisalgoritm". arXiv (2014). arXiv:1411.4028.
https:///doi.org/10.48550/arXiv.1411.4028
arXiv: 1411.4028

[18] Juan M Arrazola, Ville Bergholm, Kamil Brádler, Thomas R Bromley, Matt J Collins, Ish Dhand, Alberto Fumagalli, Thomas Gerrits, Andrey Goussev, Lukas G Helt jt. "Palju footonitega kvantahelad programmeeritaval nanofotoonilisel kiibil". Nature 591, 54–60 (2021).
https://doi.org/10.1038/s41586-021-03202-1

[19] Fernando GSL Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore ja Xiaodi Wu. "Kvant-SDP lahendajad: suured kiirused, optimaalsus ja rakendused kvantõppele". 46. rahvusvaheline automaatide, keelte ja programmeerimise kollokvium (ICALP 2019) 132, 27:1–27:14 (2019).
https:///doi.org/10.4230/LIPIcs.ICALP.2019.27

[20] Joran Van Apeldoorn ja András Gilyén. "Rakendustega kvant-sdp-lahenduse täiustused". 46. rahvusvahelise automaatide, keelte ja programmeerimise kollokviumi toimetistes (2019).
https:///doi.org/10.4230/LIPICS.ICALP.2019.99

[21] Joran van Apeldoorn, Andràs Gilyèn, Sander Gribling ja Ronald de Wolf. "Quantum sdp-solvers: paremad ülemised ja alumised piirid". Quantum 4, 230 (2020).
https://doi.org/10.22331/q-2020-02-14-230

[22] Fernando GSL Brandão ja Krysta M. Svore. "Kvantkiirendused poolkindlate programmide lahendamiseks". 2017. aastal toimus IEEE 58. iga-aastane arvutiteaduse aluste sümpoosion (FOCS). Lk 415–426. (2017).
https:///doi.org/10.1109/FOCS.2017.45

[23] Fernando GS L. Brandão, Richard Kueng ja Daniel Stilck França. "Kiiremad kvant- ja klassikalised SDP lähendused ruutarvuliseks binaarseks optimeerimiseks". Quantum 6, 625 (2022).
https://doi.org/10.22331/q-2022-01-20-625

[24] Dhrumil Patel, Patrick J. Coles ja Mark M. Wilde. "Variatsioonilised kvantalgoritmid poolkindlaks programmeerimiseks" (2021). arXiv:2112.08859.
arXiv: 2112.08859

[25] Anirban N. Chowdhury, Guang Hao Low ja Nathan Wiebe. "Variatsiooniline kvantalgoritm kvantgibbsi olekute ettevalmistamiseks" (2020). arXiv:2002.00055.
arXiv: 2002.00055

[26] Taylor L Patti, Omar Shehab, Khadijeh Najafi ja Susanne F Yelin. "Markovi ahela Monte Carlo täiustatud variatsioonilised kvantalgoritmid". Quantum Science and Technology 8, 015019 (2022).
https:///doi.org/10.1088/2058-9565/aca821

[27] Youle Wang, Guangxi Li ja Xin Wang. "Variational quantum gibbsi oleku ettevalmistamine kärbitud taylori seeriaga". Rakendatud füüsiline ülevaade 16, 054035 (2021).
https:///doi.org/10.1103/PhysRevApplied.16.054035

[28] Sanjeev Arora, Elad Hazan ja Satyen Kale. "Korrutatavate kaalude värskendamise meetod: metaalgoritm ja rakendused". Arvutusteooria 8, 121–164 (2012).
https:///doi.org/10.4086/toc.2012.v008a006

[29] Iordanis Kerenidis ja Anupam Prakash. "Kvant-sisepunkti meetod lps ja sdps jaoks". ACM tehingud Quantum Computing 1 (2020).
https:///doi.org/10.1145/3406306

[30] Brandon Augustino, Giacomo Nannicini, Tamás Terlaky ja Luis F. Zuluaga. "Kvant-sisepunkti meetodid poolkindlaks optimeerimiseks" (2022). arXiv:2112.06025.
arXiv: 2112.06025

[31] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio ja Patrick J. Coles. "Variatsioonilised kvantalgoritmid". Nature Reviews Physics 3, 625–644 (2021).
https://doi.org/10.1038/s42254-021-00348-9

[32] Kishor Bharti, Tobias Haug, Vlatko Vedral ja Leong-Chuan Kwek. "Mürakas keskmise skaala kvantalgoritm poolkindlaks programmeerimiseks". Phys. Rev. A 105, 052445 (2022).
https:///doi.org/10.1103/PhysRevA.105.052445

[33] Lennart Bittel ja Martin Kliesch. "Variatsiooniliste kvantalgoritmide treenimine on np-raske." Phys. Rev. Lett. 127, 120502 (2021).
https:///doi.org/10.1103/PhysRevLett.127.120502

[34] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush ja Hartmut Neven. Viljatud platood kvantnärvivõrgu treeningmaastikel. Nature Communications 9, 4812 (2018).
https://doi.org/10.1038/s41467-018-07090-4

[35] Carlos Ortiz Marrero, Mária Kieferová ja Nathan Wiebe. "Põimumisest põhjustatud viljatud platood". PRX Quantum 2, 040316 (2021).
https:///doi.org/10.1103/PRXQuantum.2.040316

[36] Taylor L. Patti, Khadijeh Najafi, Xun Gao ja Susanne F. Yelin. "Tanglement devised viljatu platoo leevendamine". Phys. Rev. Res. 3, 033090 (2021).
https:///doi.org/10.1103/PhysRevResearch.3.033090

[37] Arthur Pesah, M. Cerezo, Samson Wang, Tyler Volkoff, Andrew T. Sornborger ja Patrick J. Coles. "Kvantkonvolutsiooniliste närvivõrkude viljatute platoode puudumine". Phys. Rev. X 11, 041011 (2021).
https:///doi.org/10.1103/PhysRevX.11.041011

[38] Dorit Aharonov, Vaughan Jones ja Zeph Landau. "Polünoomne kvantalgoritm Jonesi polünoomi lähendamiseks". Algorithmica, 55, 395–421 (2009).
https://doi.org/10.1007/s00453-008-9168-0

[39] Clayton W. komandör. “Maksimaalne lõikeprobleem, maksimaalne lõikeprobleem, maksimaalne lõikeprobleem, maksimaalne lõikamine”. Lk 1991–1999. Springer USA. Boston, MA (2009).
https://doi.org/10.1007/978-0-387-74759-0_358

[40] Steven J. Benson, Yinyu Yeb ja Xiong Zhang. "Segaline lineaarne ja poolmääratud programmeerimine kombinatoorseks ja ruutlikuks optimeerimiseks". Optimeerimismeetodid ja tarkvara 11, 515–544 (1999).
https:///doi.org/10.1080/10556789908805761

[41] Changhui Choi ja Yinyu Ye. "Hõredate poolmääratletud programmide lahendamine kahe skaleerimise algoritmi abil iteratiivse lahendajaga". Käsikiri, Iowa ülikooli juhtimisteaduste osakond, Iowa City, IA 52242 (2000). url: web.stanford.edu/ yyye/yyye/cgsdp1.pdf.
https:///web.stanford.edu/~yyye/yyye/cgsdp1.pdf

[42] Angelika Wiegele. "Biq maci teek – keskmise suurusega maksimaalselt lõigatud ja ruutarvuliste 0-1 programmeerimisjuhtumite kogu". Alpen-Adria-Universität Klagenfurt (2007). url: biqmac.aau.at/biqmaclib.pdf.
https:///biqmac.aau.at/biqmaclib.pdf

[43] Stefan H. Schmieta. Segatud poolmääratletud-ruut-lineaarsete programmide dimacsi teek. 7. DIMACSi juurutamise väljakutse (2007). URL: http:///archive.dimacs.rutgers.edu.
http:///archive.dimacs.rutgers.edu

[44] Yoshiki Matsuda. "Maksimaalse lõikeprobleemi võrdlus simuleeritud bifurkatsioonimasinas". Keskmine (2019). url: medium.com/toshiba-sbm/benchmarking-the-max-cut-problem-on-the-simulated-bifurcation-machine-e26e1127c0b0.
https:///medium.com/toshiba-sbm/benchmarking-the-max-cut-problem-on-the-simulated-bifurcation-machine-e26e1127c0b0

[45] RM Karp. "Tõstatavus kombinatoorsete probleemide hulgas". Springer USA. Boston, MA (1972).

[46] Dimitri P Bertsekas. "Piiratud optimeerimine ja lagrange'i kordaja meetodid". Akadeemiline ajakirjandus. (1982).
https://doi.org/10.1016/C2013-0-10366-2

[47] G Mauro D'Ariano, Matteo GA Paris ja Massimiliano F Sacchi. "Kvanttomograafia". Kujutise ja elektronfüüsika edusammud 128, 206–309 (2003).
https:///doi.org/10.48550/arXiv.quant-ph/0302028
arXiv:quant-ph/0302028

[48] Alessandro Bisio, Giulio Chiribella, Giacomo Mauro D'Ariano, Stefano Facchini ja Paolo Perinotti. "Optimaalne kvanttomograafia". IEEE Journal of Selected Topics in Quantum Electronics 15, 1646–1660 (2009).
https:///doi.org/10.1109/JSTQE.2009.2029243

[49] Max S. Kaznady ja Daniel FV James. "Kvanttomograafia numbrilised strateegiad: täieliku optimeerimise alternatiivid". Phys. Rev. A 79, 022109 (2009).
https:///doi.org/10.1103/PhysRevA.79.022109

[50] Javier Peña. "Esimest järku meetodite lähenemine kumera konjugaadi kaudu". Operations Research Letters 45, 561–564 (2017).
https:///doi.org/10.1016/j.orl.2017.08.013

[51] Alan Frieze ja Mark Jerrum. Täiustatud lähendusalgoritmid maxk-lõike ja maksimaalse poolitamise jaoks. Algorithmica 18, 67–81 (1997).
https:///doi.org/10.1007/BF02523688

[52] Clark David Thompson. "Vlsi keerukuse teooria". Doktoritöö. Carnegie Melloni ülikool. (1980). url: dl.acm.org/doi/10.5555/909758.
https:///dl.acm.org/doi/10.5555/909758

[53] Chu Min Li ja Felip Manya. "Maxsat, kõvad ja pehmed piirangud". Rahuldavuse käsiraamatus. Lk 903–927. IOS Press (2021).
https://doi.org/10.3233/978-1-58603-929-5-613

[54] Nicholas J Higham. "Lähima korrelatsioonimaatriksi arvutamine – finantsprobleem." IMA Journal of Numerical Analysis 22, 329–343 (2002).
https:///doi.org/10.1093/imanum/22.3.329

[55] Tadayoshi Fushiki. "Positiivsete poolkindlate korrelatsioonimaatriksite hindamine kumera ruutkeskse poolmääratletud programmeerimise abil". Neural Computation 21, 2028–2048 (2009).
https:///doi.org/10.1162/neco.2009.04-08-765

[56] Todd MJ. "Uuring otsingusuundade kohta alg-kahe sisepunkti meetodites poolkindla programmeerimise jaoks". Optimeerimismeetodid ja tarkvara 11, 1–46 (1999).
https:///doi.org/10.1080/10556789908805745

[57] Roger Fletcher. "Karistusfunktsioonid". Matemaatiline programmeerimine Tehnika tase: Bonn 1982, lk 87–114 (1983).
https://doi.org/10.1007/978-3-642-68874-4_5

[58] Robert M Freund. "Piiratud optimeerimise karistus- ja tõkkemeetodid". Loengukonspektid, Massachusettsi Tehnoloogiainstituut (2004). url: ocw.mit.edu/courses/15-084j-nonlinear-programming-spring-2004.
https:///ocw.mit.edu/courses/15-084j-nonlinear-programming-spring-2004

[59] Eric Ricardo Anschuetz. "Kriitilised punktid kvantgeneratiivsetes mudelites". Rahvusvahelisel õpirepresentatsioonide konverentsil. (2022). url: openreview.net/forum?id=2f1z55GVQN.
https:///openreview.net/forum?id=2f1z55GVQN

[60] Amir Beck. "Esimese järgu meetodid optimeerimisel". SIAM. (2017).
https:///doi.org/10.1137/1.9781611974997

[61] Sanjeev Arora ja Satyen Kale. "Kombinatoorne, ürgne-kaheline lähenemine poolkindlatele programmidele". J. ACM 63 (2016).
https:///doi.org/10.1145/2837020

[62] Taylor L. Patti, Jean Kossaifi, Susanne F. Yelin ja Anima Anandkumar. "Tensorly-quantum: Quantum masinõpe tensormeetoditega" (2021). arXiv:2112.10239.
arXiv: 2112.10239

[63] Jean Kossaifi, Yannis Panagakis, Anima Anandkumar ja Maja Pantic. “Tensorly: Tensor learning in python”. Journal of Machine Learning Research 20, 1–6 (2019). url: http:///jmlr.org/papers/v20/18-277.html.
http:///jmlr.org/papers/v20/18-277.html

[64] cuQuantum meeskond. „Nvidia/cuquantum: cuquantum v22.11” (2022).

[65] Diederik P. Kingma ja Jimmy Ba. “Adam: stohhastilise optimeerimise meetod” (2017). arXiv: 1412.6980.
arXiv: 1412.6980

[66] Brahim Chaourar. "Lineaarne ajaalgoritm maksimaalse lõikeprobleemi variandi jaoks paralleelsetes graafikutes". Edusammud operatsioonide uurimisel (2017).
https:///doi.org/10.1155/2017/1267108

[67] Juri Makarychev. “Kuratowski graafiku tasapinnalisuse kriteeriumi lühike tõestus”. Journal of Graph Theory, 25, 129–131 (1997).
<a href="https://doi.org/10.1002/(SICI)1097-0118(199706)25:23.0.CO;2-O”>https://doi.org/10.1002/(SICI)1097-0118(199706)25:2<129::AID-JGT4>3.0.CO;2-O

[68] Béla Bollobás. "Juhuslike graafikute areng - hiiglaslik komponent". Lk 130–159. Cambridge'i õpingud edasijõudnute matemaatikas. Cambridge University Press. (2001). 2 väljaanne.
https:///doi.org/10.1017/CBO9780511814068.008

[69] Sanjeev Arora, David Karger ja Marek Karpinski. "Polünoomaja lähendamise skeemid np-raskete probleemide tihedate juhtumite jaoks". Journal of Computer and System Sciences 58, 193–210 (1999).
https:///doi.org/10.1006/jcss.1998.1605

[70] Rick Durrett. “Erdös–rényi juhuslikud graafikud”. Lk 27–69. Cambridge'i seeria statistilises ja tõenäosuslikus matemaatikas. Cambridge University Press. (2006).
https:///doi.org/10.1017/CBO9780511546594.003

[71] Gary Chartrand ja Ping Zhang. "Kromaatilise graafi teooria". Taylor ja Francis. (2008).
https:///doi.org/10.1201/9781584888017

[72] John van de Wetering. "Zx-arvutus töötavale kvantarvutiteadlasele" (2020). arXiv:2012.13966.
arXiv: 2012.13966

[73] Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons ja Seyon Sivarajah. "Faasividinate süntees madalate vooluahelate jaoks". Electronic Proceedings in Theoretical Computer Science 318, 213–228 (2020).
https:///doi.org/10.4204/eptcs.318.13

[74] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe ja Shuchen Zhu. "Traavli vea teooria kommutaatori skaleerimisega". Phys. Rev. X 11, 011020 (2021).
https:///doi.org/10.1103/PhysRevX.11.011020

[75] Joseph W Britton, Brian C Sawyer, Adam C Keith, CC Joseph Wang, James K Freericks, Hermann Uys, Michael J Biercuk ja John J Bollinger. "Mõeldud kahemõõtmelised interaktsioonid sadade keerutustega püütud ioonide kvantsimulaatoris". Nature 484, 489–492 (2012).
https:///doi.org/10.1038/nature10981

[76] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, Harry Levine, Ahmed Omran, Hannes Pichler, Soonwon Choi, Alexander S Zibrov, Manuel Endres, Markus Greiner jt. "Paljude kehade dünaamika uurimine 51-aatomilisel kvantsimulaatoril". Nature 551, 579–584 (2017).
https:///doi.org/10.1038/nature24622

[77] Gheorghe-Sorin Paraoanu. "Hiljutised edusammud ülijuhtivaid ahelaid kasutades kvantsimulatsioonis". Journal of Low Temperature Physics 175, 633–654 (2014).
https://doi.org/10.1007/s10909-014-1175-8

[78] Katsuki Fujisawa, Hitoshi Sato, Satoshi Matsuoka, Toshio Endo, Makoto Yamashita ja Maho Nakata. "Kõrge jõudlusega üldine lahendaja äärmiselt suuremahuliste poolkindlate programmeerimisprobleemide jaoks". SC '12: kõrgjõudlusega andmetöötluse, võrkude loomise, salvestuse ja analüüsi rahvusvahelise konverentsi materjalid. Lk 1–11. (2012).
https:///doi.org/10.1109/SC.2012.67

[79] Adrian S. Lewis ja Michael L. Overton. "Omaväärtuse optimeerimine". Acta Numerica 5, 149–190 (1996).
https:///doi.org/10.1017/S0962492900002646

[80] Xiaosi Xu, Jinzhao Sun, Suguru Endo, Ying Li, Simon C. Benjamin ja Xiao Yuan. "Lineaaralgebra variatsioonialgoritmid". Science Bulletin 66, 2181–2188 (2021).
https:///doi.org/10.1016/j.scib.2021.06.023

Viidatud

Ei saanud tuua Ristviide viidatud andmete alusel viimase katse ajal 2023-07-12 14:07:40: 10.22331/q-2023-07-12-1057 viidatud andmeid ei saanud Crossrefist tuua. See on normaalne, kui DOI registreeriti hiljuti. Peal SAO/NASA KUULUTUSED teoste viitamise andmeid ei leitud (viimane katse 2023-07-12 14:07:40).

See raamat on avaldatud Quantum all Creative Commons Attribution 4.0 International (CC BY 4.0) litsents. Autoriõigus jääb algsetele autoriõiguste valdajatele, näiteks autoritele või nende institutsioonidele.

SEO-põhise sisu ja PR-levi. Võimenduge juba täna.
PlatoData.Network Vertikaalne generatiivne Ai. Jõustage ennast. Juurdepääs siia.
PlatoAiStream. Web3 luure. Täiustatud teadmised. Juurdepääs siia.
PlatoESG. Autod/elektrisõidukid, Süsinik, CleanTech, Energia, Keskkond päikeseenergia, Jäätmekäitluse. Juurdepääs siia.
BlockOffsets. Keskkonnakompensatsiooni omandi ajakohastamine. Juurdepääs siia.
Allikas: https://quantum-journal.org/papers/q-2023-07-12-1057/

Ajatempel: Juuli 12, 2023

Ajatempel: Juuli 14, 2022

Kvant-Goemansi-Williamsoni algoritm Hadamardi testi ja ligikaudsete amplituudipiirangutega

Taasavaldanud Platon

Abstraktne

Populaarne kokkuvõte

► BibTeX-i andmed

► Viited

Viidatud

Veel alates Quantum Journal

Püsiv mittelokaalsus ülikülma aatomi keskkonnas

Efektiivne versus Floqueti teooria Kerri parameetrilise ostsillaatori jaoks

Suhtelise superpositsiooni mõõtmine materjali kvantjoonlauaga

TFermion: kvantkeemia kvantfaasi hindamise algoritmide mitte-Cliffordi värava kulude hindamise raamatukogu

Põimumise entroopia tootmine kvantnärvivõrkudes

Mõõtmeteooriate ja bosoniliste süsteemide tõestatult täpne simulatsioon

Juhusliku juurdepääsu koodid kvantkontekstilise liiasuse kaudu

Kvantarvutiga juhitavate väravate toimingute algolekust sõltuv optimeerimine

Kiire kvantahela lõikamine juhuslike mõõtmistega

Mitteperioodiliste optiliste kellade statistiline ajadomeeni iseloomustus

Meist

Vertikaalne otsing ja Ai

Platvorm

Püsi ühenduses

konto