"Думаю, я смела магу сказаць, што квантавую механіку ніхто не разумее", – Рычард Фейнман.
Тэма квантавых вылічэнняў заўсёды прыцягвала тэхнічных пісьменнікаў і журналістаў. Яе патэнцыял у галіне вылічэнняў і складанасць надалі ёй нейкі містычны арэол. Занадта ўжо часта тэматычныя артыкулы і інфаграфіка падрабязна апісваюць разнастайныя далягляды гэтай галіны, пры гэтым ледзь закранаючы пытанні яе практычнага ўжывання: гэта можа ўвесці ў памылку не занадта ўважлівага чытача.
У навукова-папулярных артыкулах апускаюцца апісанні квантавых сістэм і прыводзяцца сцвярджэнні тыпу:
Звычайны біт можа быць роўны "1" ці "0", але кубіт можа быць адначасова роўны "1" і "0".
Калі вам моцна павязе (у чым я не ўпэўнены), то вам раскажуць, што:
Кубіт знаходзіцца ў суперпазіцыі паміж "1" і "0".
Ніводнае з гэтых тлумачэнняў не выглядае праўдападобным, паколькі мы спрабуем сфармуляваць квантавамеханічны феномен пры дапамозе моўных сродкаў, створаных у вельмі традыцыйным свеце. Каб зразумела растлумачыць прынцыпы квантавых вылічэнняў, неабходна прымяніць іншую мову - матэматычны.
У гэтым кіраўніцтве я раскажу пра матэматычныя інструменты, неабходныя для мадэлявання і разумення квантавых вылічальных сістэм, а таксама пра тое, як ілюстраваць і прымяняць логіку квантавых вылічэнняў. Больш за тое, я прывяду прыклад квантавага алгарытму і раскажу, у чым яго перавага перад традыцыйным кампутарам.
Я прыкладу ўсе намаганні, каб расказаць пра ўсё гэта зразумелая мова, але ўсё ж спадзяюся, што ў чытачоў гэтага артыкула ёсць базавыя ўяўленні аб лінейнай алгебры і лічбавай логіцы (пра лінейную алгебру расказваецца , пра лічбавую логіку ).
Для пачатку давайце прабяжымся па прынцыпах лічбавай логікі. Яна заснавана на выкарыстанні электрычных схем для правядзення вылічэнняў. Каб зрабіць наша апісанне больш абстрактным, спросцім стан электраправода да "1" ці "0", што будзе адпавядаць станам "вкл" або "выкл". Выбудаваўшы транзістары ў вызначанай паслядоўнасці, мы створым так званыя лагічныя элементы, якія прымаюць адно або некалькі значэнняў уваходных сігналаў і што пераўтвараюць іх у выходны сігнал на аснове вызначаных правіл булевай логікі.
Распаўсюджаныя лагічныя элементы і табліцы іх станаў
На аснове ланцугоў такіх базавых элементаў можна ствараць больш складаныя элементы, а на аснове ланцугоў больш складаных элементаў мы ў канчатковым выніку з вялікай дзеллю абстрактнасці можам разлічваць на атрыманне аналогу цэнтральнага працэсара.
Як я ўжо згадваў раней, нам неабходны спосаб матэматычнага адлюстравання лічбавай логікі. Для пачатку давайце прадставім матэматычную традыцыйную логіку. З дапамогай лінейнай алгебры класічныя біты са значэннямі "1" і "0" можна прадставіць у выглядзе двух вектар-слупкоў:
дзе лічбы злева з'яўляюцца вектара. Прадставіўшы нашы біты такім чынам, мы можам мадэляваць лагічныя аперацыі над бітамі з выкарыстаннем вектарных трансфармацый. Звярніце ўвагу: нягледзячы на тое, што пры выкарыстанні двух бітаў у лагічных элементах можна выконваць мноства аперацый ("І" (AND), "Не" (NOT), "Искл. Або" (XOR) і інш.), пры выкарыстанні аднаго біта магчыма выкананне толькі чатырох аперацый: тоеснае пераўтварэнне, адмаўленне, вылічэнне канстанты "0" і вылічэнне канстанты "1". Пры тоесным пераўтварэнні біт застаецца нязменным, пры адмаўленні значэнне біта змяняецца на супрацьлеглае (з "0" на "1" ці з "1" на "0"), а вылічэнне канстанты "1" або "0" усталёўваюць біт у "1" ці "0" па-за залежнасцю ад яго папярэдняга значэння.
| ідэнтычнасць | Тоеснае пераўтварэнне |
| адмаўленне | Адмаўленне |
| Constant-0 | Вылічэнне канстанты «0» |
| Constant-1 | Вылічэнне канстанты «1» |
На падставе прапанаванага намі новага ўяўлення біта досыць лёгка выконваць аперацыі над адпаведным бітам пры дапамозе вектарнай трансфармацыі:
Перш чым рушыць далей, давайце звернемся да паняцця , якое ўсяго толькі разумее, што для забеспячэння зварачальнасці аперацыі ці лагічнага элемента неабходна вызначыць спіс значэнняў уваходных сігналаў на падставе выходных сігналаў і назоваў выкарыстоўваных аперацый. Такім чынам можна скласці, што тоеснае пераўтварэнне і адмаўленне з'яўляюцца зварачальнымі, а аперацыі па вылічэнні канстант "1" і "0" - не. Дзякуючы квантавай механікі квантавыя кампутары выкарыстоўваюць выключна зварачальныя аперацыі, таму на іх мы і засяродзімся. Далей мы пераўтворым незваротныя элементы ў зварачальныя, каб забяспечыць магчымасць іх выкарыстання квантавым кампутарам.
З дапамогай асобных бітаў можна ўявіць мноства бітаў:
Цяпер, калі ў нас ёсць амаль усе неабходныя матэматычныя ўяўленні, пяройдзем да нашага першага квантавага лагічнага элемента. Гэта аператар , або кантраляванае "Не" (NOT), які мае вялікае значэнне ў зварачальных і квантавых вылічэннях. Элемент CNOT прымяняецца да двух бітаў і вяртае два біты. Першы біт прызначаецца "кіравальным", а другі - "кантрольным". Калі кіраўнік біт усталяваны ў "1", кантрольны біт змяняе сваё значэнне; калі кіраўнік біт усталяваны ў "0", кантрольны біт не змяняецца.
Гэты аператар можа быць прадстаўлены ў выглядзе наступнага вектара пераўтварэнні:
Каб прадэманстраваць усё, з чым мы ўжо разабраліся, я пакажу варыянты ўжывання элемента CNOT у стаўленні мноства бітаў:
Рэзюмуем ужо сказанае: у першым прыкладзе мы раскладваем |10⟩ на часткі яго тэнзарнага твора і выкарыстаем матрыцу CNOT для атрымання новага які адпавядае стану твора; затым мы фактарызуем яго да |11⟩ у адпаведнасці з прыведзенай раней табліцай значэнняў CNOT.
Такім чынам, мы ўспомнілі ўсе матэматычныя правілы, якія дапамогуць разабрацца з традыцыйнымі вылічэннямі і звычайнымі бітамі, і нарэшце можам перайсці да сучасных квантавых вылічэнняў і кубітаў.
Калі вы дачыталі да гэтага месца, то ў мяне для вас добрая навіна: кубіты лёгка можна выказаць матэматычна. Увогуле, калі класічны біт (cbit) можа ўсталёўвацца ў | 1⟩ ці | 0⟩, кубіт проста знаходзіцца ў суперпазіцыі і да вымярэння можа адначасова быць роўны | 0⟩ і | 1⟩. Пасля вымярэння ён калапсуе ў | 0⟩ або | 1⟩. Іншымі словамі, кубіт можна прадставіць у выглядзе лінейнай камбінацыі |0⟩ і |1⟩ у адпаведнасці з прыведзенай ніжэй формулай:
дзе a₀ и а₁ уяўляюць, адпаведна, амплітуды |0⟩ і |1⟩. Іх можна разглядаць як «квантавыя верагоднасці», якія ўяўляюць верагоднасць калапсавання кубіта ў які-небудзь са станаў пасля яго вымярэння, паколькі ў квантавай механіцы аб'ект у суперпазіцыі калапсуе ў адзін са станаў пасля фіксацыі. Раскладзем гэты выраз і атрымаем наступнае:
Каб спрасціць сваё тлумачэнне, менавіта гэтым уяўленнем я буду карыстацца ў гэтым артыкуле.
Для гэтага кубіта шанец калапсавання ў значэнне a₀ пасля вымярэння роўны |a₀|², а шанец калапсавання ў значэнне a₁ роўны |a₁|². Напрыклад, для наступнага кубіта:
шанец калапсавання ў "1" роўны | 1/√2 | ², або ½, гэта значыць 50/50.
Паколькі ў класічнай сістэме ўсе верагоднасці ў суме павінны даваць адзінку (для паўнавартаснага размеркавання верагоднасцяў), можна зрабіць выснову аб тым, што квадраты абсалютных значэнняў амплітуд | 0⟩ і | 1⟩ павінны ў суме складаць адзінку. На падставе гэтай інфармацыі мы можам скласці наступнае раўнанне:
Калі вы знаёмыя з трыганаметрыяй, то заўважыце, што гэтае раўнанне адпавядае тэарэме Піфагора (a²+b²=c²), гэта значыць мы можам графічна прадставіць магчымыя станы кубіта ў выглядзе кропак на адзінкавай акружнасці, а менавіта:
Лагічныя аператары і элементы прымяняюцца ў дачыненні да кубітаў таксама, як і ў сітуацыі з класічнымі бітамі – на падставе матрычнай трансфармацыі. Усе зварачальныя матрычныя аператары, якія мы ўспомнілі да цяперашняга моманту, у прыватнасці, CNOT, могуць выкарыстоўвацца для працы з кубітамі. Такія матрычныя аператары дазваляюць выкарыстоўваць кожную з амплітуд кубіта без яго вымярэння і калапсавання. Дазвольце прывесці прыклад выкарыстання аператара адмаўлення да кубіту:
Перш чым мы працягнем, я нагадаю, што значэння амплітуд a₀ і a₁ на самой справе з'яўляюцца , таму стан кубіта найбольш дакладна можна адлюстраваць на трохмернай адзінкавай сферы, таксама вядомай як :
Тым не менш, каб спрасціць тлумачэнне, тут мы абмяжуемся сапраўднымі лікамі.
Здаецца, прыйшоў час абмеркаваць некаторыя лагічныя элементы, якія набываюць сэнс выключна ў кантэксце квантавых вылічэнняў.
Адным з найважнейшых аператараў з'яўляецца "элемент Адамара": ён бярэ біт у стане "0" ці "1" і ставіць яго ў адпаведную суперпазіцыю з 50%-шансам яго калапсавання ў "1" ці "0" пасля вымярэння.
Звярніце ўвагу, што ў ніжняй правай частцы аператара Адамара прысутнічае адмоўны лік. Гэта звязана з тым, што вынік прымянення аператара залежыць ад значэння ўваходнага сігналу: - | 1⟩ або | 0⟩, і таму вылічэнне з'яўляецца зварачальным.
Яшчэ адным важным момантам, злучаным з элементам Адамара, з'яўляецца яго зварачальнасць, гэта значыць ён можа прымаць кубіт у якая адпавядае суперпазіцыі і пераўтварыць яго ў |0⟩ або |1⟩.
Гэта вельмі важна, паколькі дае нам магчымасць пераўтварэння з квантавага стану без вызначэння стану кубіту - і, адпаведна, без яго калапсавання. Так, мы можам структураваць квантавыя вылічэнні на аснове дэтэрмінаванага, а не імавернаснага прынцыпу.
Квантавыя аператары, якія змяшчаюць выключна сапраўдныя лікі, з'яўляюцца ўласнай супрацьлегласцю, таму мы можам прадставіць вынік прымянення аператара да кубіту як пераўтварэнне ў межах адзінкавай акружнасці ў выглядзе машыны станаў:
Такім чынам, кубіт, стан якога прадстаўлена на схеме вышэй, пасля ўжывання аперацыі Адамара пераўтворыцца ў стан, пазначанае адпаведнай стрэлкай. Аналагічна, мы можам сканструяваць іншую машыну станаў, якая будзе ілюстраваць пераўтварэнне кубіта пры выкарыстанні аператара адмаўлення, як было паказана вышэй (таксама вядомага як аператар адмаўлення Паўлі, або інверсія бітаў), як паказана ніжэй:
Каб выконваць з нашым кубітам больш складаныя аперацыі, можна выкарыстоўваць ланцужок мноства аператараў або прымяніць элементы мноства разоў. Прыклад серыйнай трансфармацыі на аснове выглядае наступным чынам:
Гэта значыць, калі мы пачынаем з біта |0⟩, ужывальны інверсію біта, а затым - аперацыю Адамара, затым - яшчэ адну інверсію біта, і яшчэ раз - аперацыю Адамара, пасля чаго - фінальную інверсію біта, у выніку мы атрымліваем вектар, прыведзены у правай частцы ланцуга. Накладваючы розныя машыны станаў сябар на сябра, мы зможам пачынаць з |0⟩ і адсочваць рознакаляровыя стрэлкі, якія адпавядаюць кожнага з пераўтварэнняў, каб зразумець, як гэта ўсё працуе.
Раз ужо мы зайшлі так далёка, прыйшоў час разгледзець адзін з тыпаў квантавых алгарытмаў, а менавіта - , і паказаць яго перавага над класічнай вылічальнай машынай. Варта адзначыць, што алгарытм Дойча-Ёжы з'яўляецца цалкам дэтэрмінаваным, гэта значыць ён вяртае правільны адказ у 100% выпадкаў (у адрозненне ад шматлікіх іншых квантавых алгарытмаў, заснаваных на імавернасным вызначэнні кубітаў).
Давайце ўявім, што ў вас ёсць чорная скрыня, якая змяшчае функцыю/аператар над адным бітам (памятайце - пры выкарыстанні аднаго біта магчыма выкананне толькі чатырох аперацый: тоеснае пераўтварэнне, адмаўленне, вылічэнне канстанты "0" і вылічэнне канстанты "1"). Якая менавіта функцыя выконваецца ў скрыні? Вы не ведаеце, якая, аднак можаце перабраць колькі заўгодна варыянтаў уваходных значэнняў і ацаніць вынікі на выхадзе.
Колькі ўваходных і выходных сігналаў давядзецца прагнаць праз чорную скрыню, каб высветліць, якая функцыя прымяняецца? Задумайцеся аб гэтым на секундачку.
У выпадку з класічным кампутарам запатрабуецца зрабіць 2 запыту для вызначэння прымяняецца функцыі. Напрыклад, калі пры ўводзе "1" мы атрымліваем на выхадзе "0", становіцца зразумела, што выкарыстоўваецца альбо функцыя вылічэння канстанты "0", альбо функцыя адмаўлення, пасля чаго вам давядзецца змяніць значэнне ўваходнага сігналу на "0" і паглядзець, што атрымаецца на выхадзе.
У выпадку з квантавым кампутарам таксама запатрабуецца два запыту, паколькі вам па-ранейшаму патрабуецца два розных выходных значэння для дакладнага вызначэння функцыі, якая прымяняецца да ўваходнага значэння. Зрэшты, калі трохі перафармуляваць пытанне, апынецца, што квантавыя кампутары ўсё ж маюць сур'ёзную перавагу: калі б вы жадалі пазнаць, ці з'яўляецца ўжывальная функцыя сталай ці зменнай, перавага апынулася б на боку квантавых вылічальных машын.
Функцыя, якая ўжываецца ў скрыні, з'яўляецца зменнай, калі розныя значэнні ўваходнага сігналу даюць розныя вынікі на вынахадзе (напрыклад, тоеснае пераўтварэнне і інверсія біта), а калі выходнае значэнне не змяняецца па-за залежнасцю ад уваходнага значэння, то функцыя з'яўляецца сталай (напрыклад, вылічэнне канстанты "1" або вылічэнне канстанты "0").
Выкарыстоўваючы квантавы алгарытм, вы зможаце вызначыць, ці з'яўляецца функцыя ў чорнай скрыні сталай ці зменнай на падставе ўсяго толькі аднаго запыту. Але перш чым падрабязна разглядаць, як гэта зрабіць, нам трэба знайсці спосаб, які дазволіць структураваць кожную з такіх функцый на квантавым кампутары. Паколькі любыя квантавыя аператары павінны быць зварачальнымі, мы адразу сутыкаемся з праблемай: функцыі вылічэння канстант "1" і "0" такімі не з'яўляюцца.
У квантавых вылічэннях часта выкарыстоўваецца наступнае рашэнне: дадаецца дадатковы выходны кубіт, які вяртае любое значэнне ўваходнага сігналу, атрыманае функцыяй.
| да: | пасля: |
|
|
|
Такім чынам, мы можам вызначаць уваходныя значэнні выключна на падставе значэння, які атрымліваецца на выхадзе, а функцыя становіцца зварачальнай. Структура квантавых ланцугоў стварае неабходнасць у дадатковым уваходным біце. Дзеля распрацоўкі адпаведных аператараў прымем, што дадатковы ўваходны кубіт усталяваны ў |0⟩.
Ужыўшы тое ж уяўленне квантавай ланцугі, што мы выкарыстоўвалі раней, паглядзім, як можна рэалізаваць кожны з чатырох элементаў (тоеснае пераўтварэнне, адмаўленне, вылічэнне канстанты "0" і вылічэнне канстанты "1") з выкарыстаннем квантавых аператараў.
Напрыклад, так можна рэалізаваць функцыю вылічэння канстанты "0":
Вылічэнне канстанты «0»:
Тут нам увогуле не патрэбныя аператары. Першы ўваходны кубіт (які мы прынялі роўным |0⟩) вяртаецца з гэтым жа значэннем, а другое ўваходнае значэнне вяртае само сябе - як звычайна.
З функцыяй вылічэння канстанты «1» сітуацыя ідзе крыху інакш:
Вылічэнне канстанты «1»:
Паколькі мы прынялі, што першы ўваходны кубіт заўсёды ўсталяваны ў |0⟩, у выніку ўжыванні аператара інверсіі біта ён заўсёды дае на вынахадзе адзінку. І як звычайна, другі кубіт дае на выхадзе сваё ж значэнне.
Пры адлюстраванні аператара тоеснага пераўтварэння задача пачынае ўскладняцца. Вось як гэта можна зрабіць:
Тоеснае пераўтварэнне:
Выкарыстаны тут знак пазначае элемент CNOT: верхняя лінія пазначае кантрольны біт, а ніжняя - кіраўнік. Нагадаю, што пры выкарыстанні аператара CNOT значэнне кантрольнага біта мяняецца, калі кіраўнік біт роўны |1⟩, але застаецца нязменным, калі кіраўнік біт роўны |0⟩. Паколькі мы прынялі, што значэнне верхняй лініі заўжды роўна |0⟩, то яе значэнне заўсёды прысвойваецца ніжняй лініі.
Аналагічным чынам дзейнічаем з аператарам адмаўлення:
адмаўленне:
Мы проста інвертуем біт у канцы выходнай лініі.
Зараз, калі мы разабраліся з папярэднім уяўленнем, давайце разгледзім пэўныя перавагі квантавай вылічальнай машыны перад традыцыйным кампутарам, калі гаворка ідзе пра вызначэнне канстантнасці ці зменнасці функцыі, утоенай у чорнай скрыні, з выкарыстаннем толькі аднаго запыту.
Для рашэння гэтай задачы пры дапамозе квантавых вылічэнняў за адзін запыт неабходна перавесці ўваходныя кубіты ў суперпазіцыю да іх перадачы функцыі, як паказана ніжэй:
Элемент Адамара паўторна прымяняецца да выніку выкарыстання функцыі, каб вывесці кубіты з суперпазіцыі і зрабіць алгарытм дэтэрмінаваным. Мы запускаем сістэму ў стане |00⟩ і па прычынах, пра якія я зараз раскажу, атрымліваем вынік |11⟩, калі прымяняецца функцыя з'яўляецца пастаяннай. Калі ж функцыя ўнутры чорнай скрыні пераменная, то пасля вымярэння сістэма вяртае рэзультат |01⟩.
Каб разабрацца з пакінутай часткай артыкула, давайце звернемся да ілюстрацыі, якую я ўжо паказваў раней:
Выкарыстаўшы аператар інверсіі біта, а затым ужыўшы элемент Адамара да абодвух уваходных значэнняў, роўным |0⟩, мы забяспечым іх пераклад у аднолькавую суперпазіцыю |0⟩ і |1⟩, а менавіта:
На прыкладзе перадачы гэтага значэння функцыі ў чорнай скрыні лёгка прадэманстраваць, што абедзве функцыі сталага значэння даюць на вынахадзе |11⟩.
Вылічэнне канстанты «0»:
Аналагічна, мы бачым, што функцыя вылічэння канстанты "1" таксама дае на выхадзе |11⟩, гэта значыць:
Вылічэнне канстанты «1»:
Звярніце ўвагу: на выхадзе абодва значэнні будуць роўныя |1⟩, паколькі -1² = 1.
Па тым жа прынцыпу можна даказаць, што пры выкарыстанні абедзвюх зменных функцый мы заўсёды будзем атрымліваць на выхадзе |01⟩ (пры ўмове выкарыстання аднолькавага метаду), хоць тут усё крыху больш складана.
Тоеснае пераўтварэнне:
Паколькі CNOT з'яўляецца двухкубітным аператарам, яго нельга прадставіць у выглядзе простай машыны станаў, і таму неабходна вызначыць два выходных сігналу на падставе тэнзарнага твора абодвух уваходных кубітаў і множанні на матрыцу CNOT па апісаным раней прынцыпе:
З дапамогай гэтага метаду мы таксама можам пацвердзіць атрыманне на вынахадзе значэння |01⟩, калі ў чорнай скрыні ўтоена функцыя адмаўлення:
адмаўленне:
Такім чынам, мы толькі што прадэманстравалі сітуацыю, у якой квантавы кампутар адназначна больш эфектыўны, чым звычайная вылічальная машына.
Што ж далей?
Прапаную на гэтым скончыць. Мы і так добра папрацавалі. Калі вы зразумелі ўсё, пра што я распавёў, думаю, зараз вы нядрэнна разбіраецеся ў асновах квантавых вылічэнняў і квантавай логікі, а таксама разумееце, чаму ў вызначаных сітуацыях квантавыя алгарытмы могуць апынуцца эфектыўней традыцыйных сродкаў вылічэння.
Маё апісанне складана назваць паўнавартасным кіраўніцтвам па квантавых вылічэннях і алгарытмах - гэта, хутчэй, кароткае ўвядзенне ў матэматыку і сістэму пазначэнняў, закліканае развеяць у чытачоў ўяўленні аб прадмеце, якія навязваюцца навукова-папулярнымі крыніцамі (сур'ёзна, многія сапраўды не могуць разабрацца ў сітуацыі!). Я не паспеў закрануць многія важныя тэмы - напрыклад, такія як , комплекснасць значэнняў амплітуды |0⟩ і |1⟩ і функцыянаванне розных квантавых лагічных элементаў пры трансфармацыі сферай Блыха.
Калі вы жадаеце сістэматызаваць і структураваць свае веды аб квантавых кампутарах, настойліва рэкамендую вам прачытаць Эмы Штрубель: нягледзячы на багацце матэматычных формул, у гэтай кнізе квантавыя алгарытмы разглядаюцца куды больш падрабязна.
Крыніца: habr.com