Квантна надмоћ

С Википедије, слободне енциклопедије

Квантна надмоћ је потенцијална способност квантних рачунарских уређаја да реше проблеме које класични рачунари практично не могу. [1] У рачунским комплексно-теоријским терминима ово генерално значи обезбеђивање суперполиномијалног убрзавања преко најпознатијег или могућег класичног алгоритма. [2] Термин је првобитно популаризовао Џон Прискил (John Preskill), али концепт квантне рачунарске предности, посебно за симулирање квантних система, датира још од Јури Маниновог (1980) и Ричард Фајнмановог (1981) предлоgа о квантном рачунарству.

Шоров алгоритам за интеграционе факторе, који ради у полиномијалном времену на квантном рачунару, пружа суперполиномијално убрзање над најпознатијим класичним алгоритмом. [3] За факторисање се сматра да је тешко користећи класичне ресурсе, али тренутно нема доказа о овој чињеници. Тешкоће доказивања онога што се не може урадити са класичним рачунарством је уобичајени проблем у дефинитивној демонстрацији квантне надмоћи.

Као и интеграциони фактори, верује се да је узимање узорака излазних дистрибуција случајних квантних кола тешко за класичне рачунаре засноване на претпоставкама разумне сложености. Гугл је раније најавио планове да до краја 2017. године демонстрира квантну надмоћ решавањем овог проблема са низом од 49 суперпроводних кубита. [4] Међутим, од почетка јануара 2018. године само Интел је најавио такав хардвер. [5] У октобру 2017. године IBM је демонстрирао симулацију од 56 кубита на конвенционалном суперкомпјутеру, повећавајући број кубита потребних за квантну надмоћ.[6]

Рачунарска комплексност[уреди | уреди извор]

Аргументи сложености се тичу тога како се количина неког ресурса потребног за решавање проблема скалира с улазном величином за тај проблем. Као продужетак класичне теорије рачунске сложености, теорија квантне сложености говори о томе шта би радни, универзални квантни компјутер могао постићи. Овде се не узима у обзир тежине изградње овог компјутера или решавање декохеренције и буке. [7] Пошто су квантне информације генерализација класичних информација, јасно је да квантни компјутер може ефикасно симулирати било који класични алгоритам.

Гранични квантни полином (ГКП) је класа проблема одлучивања која се у полиномијалном времену може решити универзалним квантним компјутером. [8] То је повезано са важним класичним класама сложености по хијерархији [9] Да ли је било који од ових услова исправан, још увек је отворено питање.

Супротно проблемима одлучивања који захтевају да или не одговоре, проблеми узорковања траже узорке из расподеле вероватноће. [10] Ако постоји класични алгоритам који може ефикасно узети узорак из излаза произвољног квантног круга, полиномијална хијерархија би се срушила на трећи ниво, што се сматра врло мало вероватним. BosonSampling је специфичнији предлог, чија класична тврдоћа зависи од непоузданости израчунавања трајне величине велике матрице с комплексним уносима, што је P# -комплетан проблем [11]. Аргументи који су коришћени да би се дошло до овог закључка такође су проширене на IQP Sampling, [12] где је потребна само претпоставка о сложености проблема у просеку и најгорем случају проблема.

Суперполиномијално убрзање[уреди | уреди извор]

Следећи алгоритми обезбеђују суперполиномијално убрзање преко најпознатијих класичних алгоритама:[13]

Шоров алгоритам за факторизацију целих бројева[уреди | уреди извор]

Овај алгоритам проналази основну факторизацију n-битног целог броја у времену, а најпознатији класични алгоритам захтева времена и најбоља горња граница за сложеност овог проблема је . [14] Такође може обезбедити убрзање за било који проблем који смањује целобројно факторисање, укључујући и чланарски проблем за матричне групе над пољима чудног поретка. [15]

Овај алгоритам је важан практично и историјски за квантно рачунарство. То је био први полиномијални временски квантни алгоритам предложен за проблем за који се верује да је тежак за класично рачунарство. Ово уверење је толико јако да се безбедност данашњег најчешћег протокола шифрирања заснива на њему. [16] Квантни компјутер који успешно и поновљиво покреће овај алгоритам има потенцијал да прекине овај систем шифрирања.[17]

Boson sampling[уреди | уреди извор]

Ова рачунарска парадигма заснована на идентичним фотонима послатим путем линеарне оптичке мреже може решити одређене проблеме узорковања и претраживања који су, узимајући у обзир неколико претпоставки, неатрактивни за класичне рачунаре. Међутим, показано је да се BosonSampling у систему са довољно великим губицима и буком може ефикасно симулирати. [18] Највећа експериментална имплементација BosonSamplingа до сада имала је 6 начина па је могла да носи до 6 фотона у исто време. [19] Најбољи предложени класични алгоритам за симулирање БосонСамплинга трају у времену за систем са n фотона и m излазних модова. [20] BosonSampling је отвореног кода имплементиран у R. Алгоритам доводи до процене 50 фотона потребних за демонстрацију квантне доминације са BosonSampling.

Узорковање излазне дистрибуције случајних квантних кола[уреди | уреди извор]

Најпознатији алгоритам за симулирање произвољног случајног квантног круга захтева количину времена која експоненцијално расте са бројем кубита, што доводи до једне групе да процени да око 50 кубита може бити довољно да демонстрира квантну надмоћ. Google је објавио своју намеру да до краја 2017. године демонстрира квантну надмоћ градњом и покретањем 49-кубитног чипа који ће у разумном времену моћи да узорке дистрибуира недоступним за било који тренутни класични рачунар. Али највећа симулација квантног кола успешно завршена на суперкомпјутеру сада садржи 56 кубита. Ово може захтевати повећање броја кубита да би се показала квантна надмоћ.

Сумњичавост[уреди | уреди извор]

Квантни рачунари су много подложнији грешкама него класични рачунари због декохеренције и буке. [21] Теорема прага наводи да бучни квантни компјутер може користити квантне исправљујуће грешке [22][23] како би симулирале беспрекорни квантни компјутер под претпоставком да је грешка уведена у сваком рачунарском циклусу мања од неког броја [24]. Нумеричке симулације сугеришу да тај број може бити чак 3%. [25] Међутим, није познато како ће се ресурси потребни за исправљање грешке скалирати с бројем кубита. [26] Скептици указују на непознато понашање буке у скалираним квантним системима као потенцијалне блокаде за успешно спровођење квантног рачунарства и демонстрацију квантне доминације.[27][21]

Референце[уреди | уреди извор]

  1. ^ Preskill, John (26. 3. 2012). „Quantum computing and the entanglement frontier”. arXiv:1203.5813 Слободан приступ [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 Слободан приступ. 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 (на језику: енглески). Приступљено 11. 1. 2018. 
  5. ^ „CES 2018: Intel's 49-Qubit Chip Shoots for Quantum Supremacy”. IEEE Spectrum: Technology, Engineering, and Science News (на језику: енглески). Приступљено 22. 7. 2017. 
  6. ^ „Google’s quantum computing plans threatened by IBM curveball”. 20. 10. 2017. Приступљено 22. 10. 2017. 
  7. ^ Watrous, John (2009). Ph. D, Robert A. Meyers, ур. Encyclopedia of Complexity and Systems Science (на језику: енглески). Springer New York. стр. 7174—7201. ISBN 9780387758886. doi:10.1007/978-0-387-30440-3_428. 
  8. ^ Tereza, Tusarova (26. 9. 2004). „Quantum Complexity Classes” (на језику: енглески). arXiv:cs/0409051v1 Слободан приступ. 
  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 (на језику: енглески). 3 (1): 15. Bibcode:2017npjQI...3...15L. ISSN 2056-6387. doi:10.1038/s41534-017-0018-2. 
  11. ^ Gard 2015, стр. 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 Слободан приступ. doi:10.1103/PhysRevLett.117.080501. 
  13. ^ Jordan, Stephen. „Quantum Algorithm Zoo”. math.nist.gov (на језику: енглески). Архивирано из оригинала 29. 4. 2018. г. Приступљено 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 Слободан приступ. 
  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. (фебруар 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 (на језику: енглески). 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 (на језику: енглески). 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 Слободан приступ [cs.DS]. 
  21. ^ а б Kalai, Gil (2. 6. 2011). „How Quantum Computers Fail: Quantum Codes, Correlations in Physical Systems, and Noise Accumulation”. arXiv:1106.0485 Слободан приступ [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 Слободан приступ. 
  25. ^ Knill, E. (3. 3. 2005). „Quantum computing with realistically noisy devices”. Nature (на језику: енглески). 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 Слободан приступ [quant-ph]. 
  27. ^ Dyakonov 2007, стр. 4–18

Литература[уреди | уреди извор]

Преузето из „https://sr.wikipedia.org/w/index.php?title=Квантна_надмоћ&oldid=27069047”