Кіріспе
Кванттық компьютерлерде алгоритмдер жұмыс істейді, әдетте суперпозицияға және/немесе түйісуге сүйене отырып.
Кванттық есептеулерде кванттық алгоритм – кванттық есептеудің нақты моделінде жұмыс істейтін алгоритм, ең көп қолданылатын модель – есептеудің кванттық схемалық моделі. Классикалық (немесе кванттық емес) алгоритм – мәселені шешу үшін нұсқаулардың шекті тізбегі немесе қадамдық процедура, онда әрбір қадам немесе нұсқау классикалық компьютерде орындалуы мүмкін. Сол сияқты, кванттық алгоритм – бұл қадамдық процедура, онда әрбір қадам кванттық компьютерде орындалуы мүмкін. Барлық классикалық алгоритмдер кванттық компьютерде де орындалуы мүмкін болса да, «кванттық алгоритм» термині көбінесе кванттық болып көрінетін немесе кванттық суперпозиция немесе кванттық түйісу сияқты кванттық есептеудің маңызды ерекшеліктерін пайдаланатын алгоритмдер үшін қолданылады. Классикалық компьютерлерді пайдалану арқылы шешілмейтін мәселелер кванттық компьютерлерді пайдалану арқылы да шешілмейді. Кванттық алгоритмдерді қызықты ететіні – олар кейбір мәселелерді классикалық алгоритмдерге қарағанда жылдам шеше алуы мүмкін, себебі кванттық алгоритмдер пайдаланатын кванттық суперпозиция мен кванттық түйісу классикалық компьютерлерде тиімді түрде модельделеуге келмейді (Кванттық басымдыққа қараңыз). Ең белгілі алгоритмдер – факторлау үшін Шор алгоритмі және құрылымдалмаған деректер базасын немесе реттелмеген тізімді іздеу үшін Гровер алгоритмі. Шор алгоритмі факторлаудың ең жақсы белгілі классикалық алгоритміне – жалпы сандық өріс ілгісіне – қарағанда әлдеқайда (жартылай экспоненциалды түрде) жылдам жұмыс істейді. Гровер алгоритмі сол тапсырманы орындау үшін ең жақсы классикалық алгоритмге – сызықтық іздеуге – қарағанда квадратикалық жылдамдықпен жұмыс істейді.
Шолу
Кванттық алгоритмдер, кванттық есептеудің қалыпты қолданылатын схемалық моделінде, әдетте, кіріс кубиттеріне әсер ететін және өлшеумен аяқталатын кванттық схема арқылы сипатталады. Кванттық схема қарапайым кванттық қақпалардан тұрады, олардың әрқайсысы шектеулі сандағы кубиттерге әсер етеді. Кванттық алгоритмдер гамильтондық оракул моделі сияқты кванттық есептеудің басқа да модельдерінде де тұжырымдалуы мүмкін. Кванттық алгоритмдерді алгоритмде қолданылатын негізгі техникалар бойынша жіктеуге болады. Кванттық алгоритмдерде кеңінен қолданылатын техникалар/идеялар: фазалық кері байланыс, фазалық бағалау, кванттық Фурье түрлендіруі, кванттық серуен, амплитуданы күшейту және топологиялық кванттық өріс теориясы. Кванттық алгоритмдер шешілетін мәселе түріне қарай да топтастырылуы мүмкін; мысалы, алгебралық мәселелерге арналған кванттық алгоритмдер туралы шолуды қараңыз.
Кванттық Фурье түрлендіруіне негізделген алгоритмдер
Кванттық Фурье түрлендіруі дискретті Фурье түрлендіруінің кванттық аналогы болып табылады және бірнеше кванттық алгоритмдерде қолданылады. Хадамард түрлендіруі де F2 өрісіндегі n өлшемді векторлық кеңістіктегі кванттық Фурье түрлендіруінің мысалы болып табылады. Кванттық Фурье түрлендіруін кванттық компьютерде полиномдық мөлшердегі кванттық қақпаларды ғана пайдаланып тиімді жүзеге асыруға болады.
Немісше Джосса алгоритмі
Deutsch–Jozsa алгоритмі кез келген детерминистік классикалық компьютер үшін қара қорап проблемасын шешеді, бұл проблеманы шешу үшін қара қорапқа экспоненциалды түрде көптеген сұраныстар қажет, бірақ кванттық компьютер бір сұраныспен оны шеше алады. Дегенмен, шектелген қателіктері бар классикалық және кванттық алгоритмдерді салыстырғанда, ешқандай жылдамдық артықшылығы байқалмайды, себебі классикалық ықтималдық алгоритмі кішкентай қателік мүмкіндігімен тұрақты мөлшердегі сұраныстар арқылы осы мәселені шеше алады. Алгоритм f функциясы тұрақты ма (барлық кіріс мәндері үшін 0 немесе барлық кіріс мәндері үшін 1) әлде теңгерімді ме (кіріс доменінің жартысы үшін 1, ал қалған жартысы үшін 0 қайтарады) екенін анықтайды.
Бернштейн-Вазирани алгоритмі
Бернштейн-Вазирани алгоритмі – ең жақсы белгілі классикалық алгоритмге қарағанда бір мәселені тиімдірек шешетін алғашқы кванттық алгоритм. Ол BQP және BPP арасындағы айырмашылықты көрсету үшін жасалған.
Саймон алгоритмі
Саймон алгоритмі қара жәшік мәселесін кез келген классикалық алгоритмнен, оның ішінде шектелген қателіктері бар ықтималдық алгоритмдерден де экспоненциалды түрде жылдам шешеді. Бұл алгоритм, біз тиімді деп есептейтін барлық классикалық алгоритмдерге қарағанда экспоненциалды жылдамдыққа қол жеткізеді және Шордың сандық көбейткіштерге жіктеу алгоритмін жасауға түрткі болды.
Кванттық фазаны бағалау алгоритмі
Кванттық фазаны бағалау алгоритмі бірлік қақпаның меншікті векторының өзіндік фазасын анықтау үшін қолданылады, егер кванттық күй сол меншікті векторға пропорционалды болса және қақпаға қолжетімділік болса. Алгоритм басқа алгоритмдерде жиі қолданылатын қосымша процедура болып табылады.
Шордың алгоритмі
Шор алгоритмі дискретті логарифм және бүтін сандарды есепке бөлу мәселелерін полиномиалдық уақытта шешеді, ал ең жақсы белгілі классикалық алгоритмдерге суперполиномиалдық уақыт керек. Бұл мәселелердің P немесе NP-толық екені белгісіз. Сонымен қатар, бұл полиномиалдық уақытта «қара жәшік» емес мәселені шешетін сирек кездесетін кванттық алгоритмдердің бірі, ал ең жақсы классикалық алгоритмдер суперполиномиалдық уақытта жұмыс істейді.
Жасырын кіші топтар проблемасы
Абельдік жасырын кіші топтар мәселесі – кванттық компьютермен шешілетін көптеген мәселелердің жалпыламасы, мысалы, Саймон мәселесі, Пелл теңдеуін шешу, R сақинасының басты идеалын тексеру және көбейткіштерге жіктеу. Абельдік жасырын кіші топтар мәселесі үшін тиімді кванттық алгоритмдер белгілі. Ал, топтың міндетті түрде абельдік болмауымен байланысты жасырын кіші топтар мәселесі – бұрын аталған мәселелердің, сондай-ақ граф изоморфизмі және кейбір торлық мәселелердің жалпыламасы болып табылады. Белгілі бір абельдік емес топтар үшін тиімді кванттық алгоритмдер бар. Алайда, симметриялық топ үшін тиімді алгоритм әлі табылған жоқ, ол граф изоморфизмі үшін де, диэдрлік топ үшін де тиімді алгоритмді қамтамасыз ететін болар еді, соның арқасында белгілі бір торлық мәселелер шешілер еді.
Гаусс сомаларын бағалау
Гаусс қосындысы – экспоненциалдық қосындының бір түрі. Осы қосындыларды бағалау үшін ең белгілі классикалық алгоритм экспоненциалдық уақытты қажет етеді. Дискретті логарифм мәселесі Гаусс қосындысын бағалауға келтіріле алатындықтан, Гаусс қосындыларын бағалауға арналған тиімді классикалық алгоритм дискретті логарифмдерді есептеуге арналған тиімді классикалық алгоритмнің болуын білдіреді, ал мұндай алгоритмнің болуы екіталай деп саналады. Дегенмен, кванттық компьютерлер Гаусс қосындыларын полиномиалдық уақыт ішінде полиномиалдық дәлдікпен бағалай алады.
Амплитудалық күшейткішке негізделген алгоритмдер
Амплитудалық күшейту – кванттық күйдің таңдалған кіші кеңістігін күшейтуге мүмкіндік беретін техника. Амплитудалық күшейтутің қолданылуы әдетте сәйкес келетін классикалық алгоритмдерге қарағанда квадраттық жылдамдыққа қол жеткізеді. Оны Гровер алгоритмінің жалпыланған түрі деп санауға болады.
Гровердің алгоритмі
Гровер алгоритмі N жазбасы бар құрылымдалмаған деректер қорын (немесе реттелмеген тізімді) белгіленген жазбаны табу үшін, классикалық түрде қажетті сұраулардың орнына тек сұрауларды пайдаланады. Классикалық түрде, шектелген қателік мүмкіндігі бар ықтималдық алгоритмдерге рұқсат етілген жағдайда да сұраулар қажет болады. Теориялық тұрғыдан алғанда, Бом механикасындағы жасырын айнымалылардың тарихына қол жеткізе алатын стандартты кванттық компьютердің гипотетикалық кеңейтілген нұсқасы қарастырылған. (Мұндай компьютер толығымен гипотетикалық болып табылады және ол стандартты кванттық компьютер емес, тіпті кванттық механиканың стандартты теориясы бойынша мүмкін емес.) Мұндай гипотетикалық компьютер N элементтен тұратын деректер қорын іздеуді ең көп қадамда жүзеге асыра алады. Бұл Гровер алгоритмі қабылдаған қадамдардан сәл жылдам. Дегенмен, екі іздеу әдісінің де кванттық компьютердің кез келген моделіне NP-толық проблемаларды полиномиалдық уақытта шешуге мүмкіндік бермейді.
Кванттық санау
Кванттық санау іздеу мәселесінің жалпыланған түрін шешеді. Бұл, тізімдегі белгіленген жазбалардың санын санау мәселесін, жай ғана олардың бар-жоқтығын анықтаудың орнына шешеді. Атап айтқанда, ол элементтер тізіміндегі белгіленген жазбалардың санын, тек сұраныстар жасау арқылы, ең көп дегенде қателікпен санайды, мұнда тізімдегі белгіленген элементтердің саны болып табылады. Нақтырақ айтқанда, алгоритм белгіленген жазбалардың саны үшін бағаны, дәлдікпен шығарады.
Кванттық жүріске негізделген алгоритмдер
Кванттық серуендеу – классикалық кездейсоқ серуендеудің кванттық аналогы. Классикалық кездейсоқ жүріс кейбір күйлердің ықтималдық таралымымен сипатталуы мүмкін, ал кванттық серуендеу күйлердің кванттық суперпозициясымен сипатталуы мүмкін. Кванттық серуендеулер кейбір «қара жәшік» проблемалары үшін экспоненциалды жылдамдыққа қол жеткізеді. Олар сондай-ақ көптеген проблемалар үшін полиномиалды жылдамдықпен шешім береді. Кванттық серуендеу алгоритмдерін жасауға арналған негіз бар, және ол әмбебап құрал болып табылады. Бұл, белгілі бір біртүтастықпен шектелген, орташа мөлшердегі бозондардың (мысалы, фотондардың) кірісі, олар кездейсоқ түрде көптеген шығыс режимдеріне таратылады. Жеке фотондар қолданылғанда, мәселе көп фотонды кванттық серуендеуге изоморфты болады. Мәселе сонда бозонның кіріс орналасуына және біртүтастыққа байланысты шығыс ықтималдық таралымының әділ үлгісін алу болып табылады. Бұл мәселені классикалық компьютерлік алгоритммен шешу үшін біртүтас түрлендіру матрицасының тұрақтысын есептеу қажет, бұл тым ұзақ уақытты алуы немесе тіпті мүмкін болмайды. 2014 жылы қолданыстағы технология мен жеке фотон күйін жасаудың стандартты ықтималдық әдістерін тиісті кванттық есептелетін сызықтық оптикалық желіге кіріс ретінде пайдалануға болады және кванттық алгоритмдерді қолдану арқылы шығыс ықтималдық таралымын үлгілеу айқын түрде тиімдірек болады деп ұсынылды. 2015 жылы жүргізілген зерттеулер үлгі алу мәселесінің Фок күйі фотондарынан басқа кірістер үшін де ұқсас күрделілікке ие екенін болжады және когерентті амплитудалық кіріс мөлшеріне байланысты есептеу күрделілігінің классикалық түрде модельдеуге болатын жағдайдан бозондық үлгі алу мәселесі сияқты қиын жағдайға өтуін анықтады.
Элементтердің ажыратылуы
Элементтердің айрықшалығы мәселесі – тізімдегі барлық элементтердің өзгеше екенін анықтау мәселесі. Классикалық жағдайда, өлшемі тізім үшін сұраныс қажет; алайда, кванттық компьютерде сұраныста шешуге болады. Оптималды алгоритмді Андрис Амбанис ұсынды, ал Яоюн Ши диапазонның мөлшері жеткілікті үлкен болғанда төменгі шекті ең тығыз дәлелдеді. Амбанис және Кутин тәуелсіз түрде (және әртүрлі дәлелдер арқылы) осы жұмысты барлық функциялар үшін төменгі шектерді алуға дейін кеңейтті.
Үшбұрышты табу мәселесі
Үшбұрышты табу мәселесі — берілген графта үшбұрыш (3-өлшемді толық подграф) бар-жоғын анықтау мәселесі. Кванттық алгоритмдер үшін белгілі ең төменгі шек — , бірақ ең жақсы белгілі алгоритм O(N1.297) сұраныс қажет етеді, бұл бұрынғы ең жақсы O(N1.3) сұраныстан жақсы нәтиже.
Формуланы бағалау
Формула – әрбір ішкі түйінде қақпасы және әрбір жапырақ түйінде кіріс биті бар ағаш. Мәселе – формуланы бағалау, яғни кіріс деректеріне оракул арқылы қол жеткізілген жағдайда тамыр түйіннің нәтижесін анықтау. Жақсы зерттелген формула – тек NAND қақпаларынан тұратын теңгерімді екілік ағаш. Бұл типтегі формулаға кездейсоқтық қолдана отырып сұраныстар қажет, бірақ кванттық алгоритммен оны сұраныста шешуге болады. Бұл жағдай үшін одан жақсы кванттық алгоритм бұрын белгілі емес, ол бұрыннан белгілі емес Гамильтон оракул модельі үшін табылғанға дейін. Күрделірек формулалар үшін жылдам кванттық алгоритмдер де белгілі.
Топтық коммутативтілік
Мәселе k генераторлармен берілген қара қорап тобының коммутативті екенін анықтау болып табылады. Қара қорап тобы – топтық операцияларды (көбейту, инверсия және бейтарап элементпен салыстыру) орындау үшін қолданылуы тиіс оракул функциясы бар топ. Бұл жағдайда назар аудару қажет нәрсе – сұраныстың күрделілігі, яғни мәселені шешу үшін қажетті оракулға жасалатын шақырулар саны. Детерминистік және рандомизацияланған сұраныс күрделілігі тиісінше және болып табылады. Кванттық алгоритмге сұраныс қажет, ал ең жақсы белгілі классикалық алгоритм сұраныс қолданады.
BQP-толық проблемалар
Күрделілік класы BQP (шекті қателікпен кванттық полиномиялық уақыт) – бұл кванттық компьютердің полиномиялық уақытта, барлық жағдайларда ең көп дегенде 1/3 қателік ықтималдығымен шешіле алатын шешімдік есептердің жиынтығы. Ол классикалық күрделілік класы BPP-нің кванттық аналогы болып табылады. Егер бір есеп BQP-ге жатса және BQP-дегі кез келген есеп оған полиномиялық уақытта келтіріле алса, онда ол BQP-толық деп аталады. Жай тілмен айтқанда, BQP-толық есептер класы – BQP-дегі ең қиын есептермен бірдей қиындық деңгейіне ие және кванттық компьютермен тиімді шешіле алатын (шекті қателікпен) есептердің жиынтығы.
Түйін инварианттарын есептеу
Виттен Черн-Саймонстың топологиялық кванттық өріс теориясын (TQFT) Джонс полиномиалдары тұрғысынан шешуге болатынын көрсетті. Кванттық компьютер TQFT-ны модельдеуге қабілетті, осы арқылы Джонс полиномиалын жуықтап табуға болады, және біздің білуімізше, оны ең жаман жағдайда классикалық түрде есептеу қиын.
Кванттық модельдеу
Кванттық компьютерлердің классикалық компьютерлерге қарағанда күшті болуы мүмкін деген идея Ричард Файнманның классикалық компьютерлерге көптеген бөлшектік кванттық жүйелерді модельдеу үшін экспоненциалды уақыт қажетті сияқты деген байқауынан туындады, бірақ кванттық көп дене жүйелері "өздігінен шешіле алады". Одан бері кванттық компьютерлер кванттық физикалық процестерді классикалық компьютерлерге қарағанда экспоненциалды түрде жылдамдатып модельдей алады деген ой кеңінен дамытылды және толықтырылды. Бозондық және фермиондық жүйелерді модельдеу үшін тиімді (яғни полиномдық уақыт) кванттық алгоритмдер әзірленді, сондай-ақ тек бірнеше жүз кубит қолдана отырып, қазіргі классикалық суперкомпьютерлердің қабілеттерінен асып түсетін химиялық реакцияларды модельдеуге мүмкіндік берді. Кванттық компьютерлер топологиялық кванттық өріс теорияларын да тиімді түрде модельдей алады. Бұл нәтиже өз қызығушылығынан басқа, Джонс және HOMFLY полиномдары сияқты кванттық топологиялық инварианттарды есептеу үшін тиімді кванттық алгоритмдерге және үш өлшемді кеңістіктердің Тураев-Виро инвариантына әкелді.
Сызықтық теңдеулер жүйесін шешу
2009 жылы Арам Харроу, Авинатан Хассидим және Сет Ллойд сызықтық жүйелерді шешуге арналған кванттық алгоритм ұсынды. Алгоритм берілген сызықтық теңдеулер жүйесінің шешім векторындағы скалярлық өлшеу нәтижесін есептейді. Егер сызықтық жүйе сиректеу болса және оның шартты саны төмен болса, сондай-ақ пайдаланушы шешім векторының мәнінен гөрі скалярлық өлшеу нәтижесіне қызығса, онда алгоритмнің жұмыс істеу уақыты , мұнда – сызықтық жүйедегі айнымалылар саны. Бұл ең жылдам классикалық алгоритмге қарағанда экспоненциалдық жылдамдыққа ие, ол (немесе оң жартылай белгілі матрицалар үшін) уақытта жұмыс істейді.
Гибридтік кванттық/классикалық алгоритмдер
Гибридтік кванттық/классикалық алгоритмдер кванттық күйді дайындау және өлшеуді классикалық оңтайландырумен үйлестіреді. Бұл алгоритмдер әдетте эрмиттік оператордың ең төменгі күйдің жеке векторы мен өзіндік мәнін табуға бағытталған.
ҚОАА
Кванттық жуық оңтайландыру алгоритмі кванттық оттепелеуден шабыт алады, кванттық тізбектерді пайдалана отырып, кванттық оттепелеудің дискреттелген жуықтауын жасайды. Оны графтар теориясының мәселелерін шешуге болады. Алгоритм "мақсаттық функцияны" максималдау үшін кванттық операцияларды классикалық түрде оңтайландыруды қолданады.
Вариациялық кванттық өздігінен шешуші
Вариациялық кванттық эйнсольвер (VQE) алгоритмі классикалық оптимизацияны қолданып, Гермиттік оператордың, мысалы молекуланың гамильтониасының, ең төменгі күйін табу үшін ансац күйінің энергияның күтілетін мәнін азайтады. Ол молекулалық гамильтондардың қозу энергияларын табу үшін де қолданылуы мүмкін.
Келісімшарт бойынша кванттық өздігінен шешуші
Келісілген кванттық өздігінен еріткіш (CQE) алгоритмі молекуланың негізгі немесе қозған күй энергиясын және екі электронды азайтылған тығыздық матрицасын табу үшін екі (немесе одан да көп) электронның кеңістігіне Шредингер теңдеуінің жиырылуының (немесе проекциясының) қалдығын азайтады. Ол анти-эрмиттік жиырылған Шредингер теңдеуінен энергияны және екі электронды азайтылған тығыздық матрицасын тікелей есептеуге арналған классикалық әдістерге негізделген.