Pređi na sadržaj

Kvantna nadmoć

S Vikipedije, slobodne enciklopedije

Kvantna nadmoć je potencijalna sposobnost kvantnih računarskih uređaja da reše probleme koje klasični računari praktično ne mogu. [1] U računskim kompleksno-teorijskim terminima ovo generalno znači obezbeđivanje superpolinomijalnog ubrzavanja preko najpoznatijeg ili mogućeg klasičnog algoritma. [2] Termin je prvobitno popularizovao Džon Priskil (John Preskill), ali koncept kvantne računarske prednosti, posebno za simuliranje kvantnih sistema, datira još od Juri Maninovog (1980) i Ričard Fajnmanovog (1981) predloga o kvantnom računarstvu.

Šorov algoritam za integracione faktore, koji radi u polinomijalnom vremenu na kvantnom računaru, pruža superpolinomijalno ubrzanje nad najpoznatijim klasičnim algoritmom. [3] Za faktorisanje se smatra da je teško koristeći klasične resurse, ali trenutno nema dokaza o ovoj činjenici. Teškoće dokazivanja onoga što se ne može uraditi sa klasičnim računarstvom je uobičajeni problem u definitivnoj demonstraciji kvantne nadmoći.

Kao i integracioni faktori, veruje se da je uzimanje uzoraka izlaznih distribucija slučajnih kvantnih kola teško za klasične računare zasnovane na pretpostavkama razumne složenosti. Gugl je ranije najavio planove da do kraja 2017. godine demonstrira kvantnu nadmoć rešavanjem ovog problema sa nizom od 49 superprovodnih kubita. [4] Međutim, od početka januara 2018. godine samo Intel je najavio takav hardver. [5] U oktobru 2017. godine IBM je demonstrirao simulaciju od 56 kubita na konvencionalnom superkompjuteru, povećavajući broj kubita potrebnih za kvantnu nadmoć.[6]

Računarska kompleksnost[uredi | uredi izvor]

Argumenti složenosti se tiču toga kako se količina nekog resursa potrebnog za rešavanje problema skalira s ulaznom veličinom za taj problem. Kao produžetak klasične teorije računske složenosti, teorija kvantne složenosti govori o tome šta bi radni, univerzalni kvantni kompjuter mogao postići. Ovde se ne uzima u obzir težine izgradnje ovog kompjutera ili rešavanje dekoherencije i buke. [7] Pošto su kvantne informacije generalizacija klasičnih informacija, jasno je da kvantni kompjuter može efikasno simulirati bilo koji klasični algoritam.

Granični kvantni polinom (GKP) je klasa problema odlučivanja koja se u polinomijalnom vremenu može rešiti univerzalnim kvantnim kompjuterom. [8] To je povezano sa važnim klasičnim klasama složenosti po hijerarhiji [9] Da li je bilo koji od ovih uslova ispravan, još uvek je otvoreno pitanje.

Suprotno problemima odlučivanja koji zahtevaju da ili ne odgovore, problemi uzorkovanja traže uzorke iz raspodele verovatnoće. [10] Ako postoji klasični algoritam koji može efikasno uzeti uzorak iz izlaza proizvoljnog kvantnog kruga, polinomijalna hijerarhija bi se srušila na treći nivo, što se smatra vrlo malo verovatnim. BosonSampling je specifičniji predlog, čija klasična tvrdoća zavisi od nepouzdanosti izračunavanja trajne veličine velike matrice s kompleksnim unosima, što je P# -kompletan problem [11]. Argumenti koji su korišćeni da bi se došlo do ovog zaključka takođe su proširene na IQP Sampling, [12] gde je potrebna samo pretpostavka o složenosti problema u proseku i najgorem slučaju problema.

Superpolinomijalno ubrzanje[uredi | uredi izvor]

Sledeći algoritmi obezbeđuju superpolinomijalno ubrzanje preko najpoznatijih klasičnih algoritama:[13]

Šorov algoritam za faktorizaciju celih brojeva[uredi | uredi izvor]

Ovaj algoritam pronalazi osnovnu faktorizaciju n-bitnog celog broja u vremenu, a najpoznatiji klasični algoritam zahteva vremena i najbolja gornja granica za složenost ovog problema je . [14] Takođe može obezbediti ubrzanje za bilo koji problem koji smanjuje celobrojno faktorisanje, uključujući i članarski problem za matrične grupe nad poljima čudnog poretka. [15]

Ovaj algoritam je važan praktično i istorijski za kvantno računarstvo. To je bio prvi polinomijalni vremenski kvantni algoritam predložen za problem za koji se veruje da je težak za klasično računarstvo. Ovo uverenje je toliko jako da se bezbednost današnjeg najčešćeg protokola šifriranja zasniva na njemu. [16] Kvantni kompjuter koji uspešno i ponovljivo pokreće ovaj algoritam ima potencijal da prekine ovaj sistem šifriranja.[17]

Boson sampling[uredi | uredi izvor]

Ova računarska paradigma zasnovana na identičnim fotonima poslatim putem linearne optičke mreže može rešiti određene probleme uzorkovanja i pretraživanja koji su, uzimajući u obzir nekoliko pretpostavki, neatraktivni za klasične računare. Međutim, pokazano je da se BosonSampling u sistemu sa dovoljno velikim gubicima i bukom može efikasno simulirati. [18] Najveća eksperimentalna implementacija BosonSamplinga do sada imala je 6 načina pa je mogla da nosi do 6 fotona u isto vreme. [19] Najbolji predloženi klasični algoritam za simuliranje BosonSamplinga traju u vremenu za sistem sa n fotona i m izlaznih modova. [20] BosonSampling je otvorenog koda implementiran u R. Algoritam dovodi do procene 50 fotona potrebnih za demonstraciju kvantne dominacije sa BosonSampling.

Uzorkovanje izlazne distribucije slučajnih kvantnih kola[uredi | uredi izvor]

Najpoznatiji algoritam za simuliranje proizvoljnog slučajnog kvantnog kruga zahteva količinu vremena koja eksponencijalno raste sa brojem kubita, što dovodi do jedne grupe da proceni da oko 50 kubita može biti dovoljno da demonstrira kvantnu nadmoć. Google je objavio svoju nameru da do kraja 2017. godine demonstrira kvantnu nadmoć gradnjom i pokretanjem 49-kubitnog čipa koji će u razumnom vremenu moći da uzorke distribuira nedostupnim za bilo koji trenutni klasični računar. Ali najveća simulacija kvantnog kola uspešno završena na superkompjuteru sada sadrži 56 kubita. Ovo može zahtevati povećanje broja kubita da bi se pokazala kvantna nadmoć.

Sumnjičavost[uredi | uredi izvor]

Kvantni računari su mnogo podložniji greškama nego klasični računari zbog dekoherencije i buke. [21] Teorema praga navodi da bučni kvantni kompjuter može koristiti kvantne ispravljujuće greške [22][23] kako bi simulirale besprekorni kvantni kompjuter pod pretpostavkom da je greška uvedena u svakom računarskom ciklusu manja od nekog broja [24]. Numeričke simulacije sugerišu da taj broj može biti čak 3%. [25] Međutim, nije poznato kako će se resursi potrebni za ispravljanje greške skalirati s brojem kubita. [26] Skeptici ukazuju na nepoznato ponašanje buke u skaliranim kvantnim sistemima kao potencijalne blokade za uspešno sprovođenje kvantnog računarstva i demonstraciju kvantne dominacije.[27][21]

Reference[uredi | uredi izvor]

  1. ^ Preskill, John (26. 3. 2012). „Quantum computing and the entanglement frontier”. arXiv:1203.5813 Slobodan pristup [quant-ph]. 
  2. ^ Papageorgiou, Anargyros; Traub, Joseph F. (12. 8. 2013). „Measures of quantum computing speedup”. Physical Review A. 88 (2): 022316. Bibcode:2013PhRvA..88b2316P. ISSN 1050-2947. arXiv:1307.7488 Slobodan pristup. doi:10.1103/PhysRevA.88.022316. 
  3. ^ Shor, P. (1. 1. 1999). „Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM Review. 41 (2): 303—332. Bibcode:1999SIAMR..41..303S. ISSN 0036-1445. doi:10.1137/S0036144598347011. 
  4. ^ „Google Plans to Demonstrate the Supremacy of Quantum Computing”. IEEE Spectrum: Technology, Engineering, and Science News (na jeziku: engleski). Pristupljeno 11. 1. 2018. 
  5. ^ „CES 2018: Intel's 49-Qubit Chip Shoots for Quantum Supremacy”. IEEE Spectrum: Technology, Engineering, and Science News (na jeziku: engleski). Pristupljeno 22. 7. 2017. 
  6. ^ „Google’s quantum computing plans threatened by IBM curveball”. 20. 10. 2017. Pristupljeno 22. 10. 2017. 
  7. ^ Watrous, John (2009). Ph. D, Robert A. Meyers, ur. Encyclopedia of Complexity and Systems Science (na jeziku: engleski). Springer New York. str. 7174—7201. ISBN 9780387758886. doi:10.1007/978-0-387-30440-3_428. 
  8. ^ Tereza, Tusarova (26. 9. 2004). „Quantum Complexity Classes” (na jeziku: engleski). arXiv:cs/0409051v1 Slobodan pristup. 
  9. ^ Vazirani, Umesh. „A Survey of Quantum Complexity Theory” (PDF). Proceedings of Symposia in Applied Mathematics. 
  10. ^ Lund, A. P.; Bremner, Michael J.; Ralph, T. C. (13. 4. 2017). „Quantum sampling problems, BosonSampling and quantum supremacy”. Npj Quantum Information (na jeziku: engleski). 3 (1): 15. Bibcode:2017npjQI...3...15L. ISSN 2056-6387. doi:10.1038/s41534-017-0018-2. 
  11. ^ Gard 2015, str. 167–192
  12. ^ Bremner, Michael J.; Montanaro, Ashley; Shepherd, Dan J. (18. 8. 2016). „Average-case complexity versus approximate simulation of commuting quantum computations”. Physical Review Letters. 117 (8): 080501. Bibcode:2016PhRvL.117h0501B. ISSN 0031-9007. PMID 27588839. arXiv:1504.07999 Slobodan pristup. doi:10.1103/PhysRevLett.117.080501. 
  13. ^ Jordan, Stephen. „Quantum Algorithm Zoo”. math.nist.gov (na jeziku: engleski). Arhivirano iz originala 29. 4. 2018. g. Pristupljeno 29. 7. 2017. 
  14. ^ Rubinstein, Michael (19. 10. 2006). „The distribution of solutions to xy = N mod a with an application to factoring integers”. arXiv:math/0610612 Slobodan pristup. 
  15. ^ Babai, László; Beals, Robert; Seress, Ákos (2009). „Polynomial-time Theory of Matrix Groups”. Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing. STOC '09. New York, NY, USA: ACM: 55—64. ISBN 9781605585062. doi:10.1145/1536414.1536425. 
  16. ^ Rivest, R. L.; Shamir, A.; Adleman, L. (februar 1978). „A Method for Obtaining Digital Signatures and Public-key Cryptosystems”. Commun. ACM. 21 (2): 120—126. ISSN 0001-0782. doi:10.1145/359340.359342. 
  17. ^ Bernstein, Daniel (2009). Post-Quantum Cryptography (na jeziku: engleski). Springer. ISBN 978-3-540-88701-0. 
  18. ^ Rahimi-Keshari, Saleh; Ralph, Timothy C.; Caves, Carlton M. (20. 6. 2016). „Sufficient Conditions for Efficient Classical Simulation of Quantum Optics”. Physical Review X. 6 (2): 021039. Bibcode:2016PhRvX...6b1039R. doi:10.1103/PhysRevX.6.021039. 
  19. ^ Carolan, Jacques; Harrold, Christopher; Sparrow, Chris; Martín-López, Enrique; Russell, Nicholas J.; Silverstone, Joshua W.; Shadbolt, Peter J.; Matsuda, Nobuyuki; Oguma, Manabu (14. 8. 2015). „Universal linear optics”. Science (na jeziku: engleski). 349 (6249): 711—716. ISSN 0036-8075. PMID 26160375. doi:10.1126/science.aab3642. 
  20. ^ Clifford, Peter; Clifford, Raphaël (5. 6. 2017). „The Classical Complexity of Boson Sampling”. arXiv:1706.01260 Slobodan pristup [cs.DS]. 
  21. ^ a b Kalai, Gil (2. 6. 2011). „How Quantum Computers Fail: Quantum Codes, Correlations in Physical Systems, and Noise Accumulation”. arXiv:1106.0485 Slobodan pristup [quant-ph]. 
  22. ^ Shor, Peter W. (1. 10. 1995). „Scheme for reducing decoherence in quantum computer memory”. Physical Review A. 52 (4): R2493—R2496. Bibcode:1995PhRvA..52.2493S. doi:10.1103/PhysRevA.52.R2493. 
  23. ^ Steane, A. M. (29. 7. 1996). „Error Correcting Codes in Quantum Theory”. Physical Review Letters. 77 (5): 793—797. Bibcode:1996PhRvL..77..793S. PMID 10062908. doi:10.1103/PhysRevLett.77.793. 
  24. ^ Aharonov, Dorit; Ben-Or, Michael (30. 6. 1999). „Fault-Tolerant Quantum Computation With Constant Error Rate”. arXiv:quant-ph/9906129 Slobodan pristup. 
  25. ^ Knill, E. (3. 3. 2005). „Quantum computing with realistically noisy devices”. Nature (na jeziku: engleski). 434 (7029): 39—44. Bibcode:2005Natur.434...39K. ISSN 0028-0836. PMID 15744292. doi:10.1038/nature03350. 
  26. ^ Kalai, Gil (3. 5. 2016). „The Quantum Computer Puzzle (Expanded Version)”. arXiv:1605.00992 Slobodan pristup [quant-ph]. 
  27. ^ Dyakonov 2007, str. 4–18

Literatura[uredi | uredi izvor]

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Квантна_надмоћ&oldid=27069047”