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

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

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

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

Рачунарска комплексност

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

Гранични квантни полином (ГКП) је класа проблема одлучивања која се у полиномијалном времену може решити универзалним квантним компјутером. То је повезано са важним класичним класама сложености по хијерархији $P\subseteq BPP\subseteq BQP\subseteq PSPACE$ Да ли је било који од ових услова исправан, још увек је отворено питање.

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

Суперполиномијално убрзање

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

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

Овај алгоритам проналази основну факторизацију n-битног целог броја у $\tilde{O}(n^3)$ времену, а најпознатији класични алгоритам захтева $2^{O(n^{1/3})}$ времена и најбоља горња граница за сложеност овог проблема је $O(2^{n/3+o(1)})$. Такође може обезбедити убрзање за било који проблем који смањује целобројно факторисање, укључујући и чланарски проблем за матричне групе над пољима чудног поретка.

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

Boson sampling

Ова рачунарска парадигма заснована на идентичним фотонима послатим путем линеарне оптичке мреже може решити одређене проблеме узорковања и претраживања који су, узимајући у обзир неколико претпоставки, неатрактивни за класичне рачунаре. Међутим, показано је да се BosonSampling у систему са довољно великим губицима и буком може ефикасно симулирати. Највећа експериментална имплементација BosonSamplingа до сада имала је 6 начина па је могла да носи до 6 фотона у исто време. Најбољи предложени класични алгоритам за симулирање БосонСамплинга трају у времену $O(n{2}^n+m{n}^2)$ за систем са n фотона и m излазних модова. BosonSampling је отвореног кода имплементиран у R. Алгоритам доводи до процене 50 фотона потребних за демонстрацију квантне доминације са BosonSampling.

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

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

Сумњичавост

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

Литература

• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book