А.В. Васильев - Квантовые вычисления для программистов, страница 2

ñîâîêóïíîñòè îòäåëü-íûõ êóáèò), êâàíòîâàÿ ìåõàíèêà ïîñòóëèðóåò, ÷òî ïðîñòðàíñòâî ñîñòîÿíèé òàêîé ñîñòàâíîéñèñòåìû áóäåò îïèñûâàòüñÿ òåíçîðíûì ïðîèçâåäåíèåì ïðîñòðàíñòâ ñîñòîÿíèé ïîäñèñòåì. Íàïðèìåð, åñëèn êóáèò íàõîäÿòñÿ â ñîñòîÿíèÿõ |ψ1 i, |ψ2 i, . . . , |ψn i, òî ñîñòîÿíèå |ψi êâàíòîâîãîðåãèñòðà, ñîñòîÿùåãî èç ýòèõ êóáèò, áóäåò âûðàæàòüñÿ ÷åðåç òåíçîðíîå ïðîèçâåäåíèå èõ ñîñòîÿíèé:|ψi = |ψ1 i ⊗ |ψ2 i ⊗ · · · ⊗ |ψn i .Òàêèå ñîñòîÿíèÿ íàçûâàþòñÿ ðàçëîæèìûìè. òî æå âðåìÿ ñóùåñòâóþò òàê íàçûâàåìûåíåðàçëîæèìûå èëè çàïóòàííûå ñîñòîÿíèÿêâàíòîâûõ ðåãèñòðîâ, êîòîðûå íå ìîãóò áûòü ïðåäñòàâëåíû òåíçîðíûì ïðîèçâåäåíèåì ñîñòîÿíèé îòäåëüíûõ êóáèò.

Òàêèìè ñîñòîÿíèÿìè ÿâëÿþòñÿ, íàïðèìåð, ÝÏÐ-ïàðû èëè ñîñòîÿíèÿÁåëëà, èãðàþùèå êëþ÷åâóþ ðîëü â êâàíòîâîé òåëåïîðòàöèè è ñâåðõïëîòíîì êîäèðîâàíèè.Òàêèì îáðàçîì, ïîñòóëèðóåòñÿ, ÷òî ðåãèñòð èç2nåäèíè÷íûì âåêòîðîì èç ïðîñòðàíñòâà H :n2Xn êóáèò â îáùåì ñëó÷àå ìîæåò áûòü îïèñàínαi |ii ,ãäåi=12X|αi |2 = 1.i=1Òàêèå ëèíåéíûå êîìáèíàöèè ïðèíÿòî íàçûâàòü ñóïåðïîçèöèÿìè áàçèñíûõ ñîñòîÿíèéàìïëèòóäàìèÈçìåðåíèå.|iiñαi .Íà êëàññè÷åñêîì êîìïüþòåðå ñ÷èòûâàíèå çíà÷åíèé ïåðåìåííûõ íå ïðåäñòàâ-ëÿåò ñëîæíîñòè.  êâàíòîâûõ ìîäåëÿõ âû÷èñëåíèé ñèòóàöèÿ ñëîæíåå. Êâàíòîâàÿ ñèñòåìàäîëæíà ôóíêöèîíèðîâàòü èçîëèðîâàííî ëþáîå âìåøàòåëüñòâî â åå ðàáîòó (â òîì ÷èñëåñ÷èòûâàíèå ðåçóëüòàòîâ âû÷èñëåíèÿ) ïðèâîäèò ê èçìåíåíèþ ñîñòîÿíèÿ.È, õîòÿ êóáèòû è ìîãóò îäíîâðåìåííî íàõîäèòüñÿ â ðàçëè÷íûõ ñîñòîÿíèÿõ, èíôîðìàöèÿ îáýòîì äîñòóïíà ëèøü îïîñðåäîâàííî ïóòåì èçìåðåíèÿ ñîñòîÿíèÿ.

Ïðè÷åì ýòî âåðîÿòíîñòíûéïðîöåññ, ò.å., èçìåðÿÿ ñóïåðïîçèöèþ (ñîñòîÿíèå ñèñòåìû)2èç ñîñòîÿíèé |ii ñ âåðîÿòíîñòüþ |αi | .5|ψi =Piαi |ii,ìû ïîëó÷èì ëþáîåiφÏðè ýòîì ñîñòîÿíèÿ, îòëè÷àþùèåñÿ ëèøü ôàçîâûì ìíîæèòåëåì eñ÷èòàþòñÿ íåîòëè÷èiφìûìè, ïîñêîëüêó ïðè èçìåðåíèè |ψi è e |ψi èìåþò îäèíàêîâîå ðàñïðåäåëåíèå âåðîÿòíîñòåéïîëó÷åíèÿ áàçèñíûõ ñîñòîÿíèé.Òàêèì îáðàçîì, èç áåñêîíå÷íîãî îáúåìà èíôîðìàöèè, êîòîðûé ìîæíî ñîõðàíèòü â àìïëèòóäàõ êâàíòîâîãî áèòà, äîñòóïåí ëèøü åäèíñòâåííûé áèò, ñîîòâåòñòâóþùèé áàçèñíîìóñîñòîÿíèþ.Äðóãîé âàðèàíò èçâëå÷åíèÿ áîëüøîãî îáúåìà èíôîðìàöèè èç îäíîãî êóáèòà ñîñòîèò âìíîãîêðàòíîì êîïèðîâàíèè ðåçóëüòàòîâ âû÷èñëåíèé è ñòàòèñòè÷åñêîì àíàëèçå ðåçóëüòàòîââû÷èñëåíèé.

Îäíàêî è ýòîò âàðèàíò íåâîçìîæåí ââèäó òîãî, ÷òî â îáùåì ñëó÷àå íåëüçÿêëîíèðîâàòü íåèçâåñòíîå êâàíòîâîå ñîñòîÿíèå.Âïðî÷åì, ýòî íå îçíà÷àåò áåñïîëåçíîñòü êâàíòîâûõ ñóïåðïîçèöèé, à ëèøü óêàçûâàåò íàíåâîçìîæíîñòü èõ êëàññè÷åñêîãî èñïîëüçîâàíèÿ.Ìû áóäåì èñïîëüçîâàòü âàðèàíò êâàíòîâîãî èçìåðåíèÿ, íàçûâàåìûé ïðîåêòèâíûì èçìåðåíèåì. Äëÿ çàäàíèÿ òàêîãî èçìåðåíèÿ äîñòàòî÷íî ïåðå÷èñëèòü ïîëíûé íàáîð îðòîãîíàëüíûõïðîåêòîðîâPm ,óäîâëåòâîðÿþùèõ ñîîòíîøåíèÿìPm Pm 0 =Âåðîÿòíîñòü èñõîäàmPmPm = IèPm , åñëè m = m0.I, èíà÷åâ òàêîì ñëó÷àå ìîæíî âûðàçèòü êàêP r(m) = ||Pm |ψi ||22 = hψ| Pm† Pm |ψi ,à ñîñòîÿíèåì|ψ 0 iñèñòåìû ïîñëå èçìåðåíèÿ áóäåòPm |ψi.|ψ 0 i = pP r(m)Äèíàìèêà èçìåíåíèÿ.Ñëåäóþùèé ïîñòóëàò ãëàñèò, ÷òî äèíàìèêà èçìåíåíèÿ ñîñòîÿíèÿçàìêíóòîé êâàíòîâîé ñèñòåìû îïèñûâàåòñÿ óíèòàðíûìè ïðåîáðàçîâàíèÿìè.

Äðóãèìè ñëîâàìè, ñîñòîÿíèåt2|ψ1 it1ñèñòåìû â ìîìåíò âðåìåíèñâÿçàíî ñ ñîñòîÿíèåì|ψ2 iâ ìîìåíò âðåìåíèñëåäóþùèì îáðàçîì:|ψ1 i = U |ψ2 i ,ãäåU ýòî óíèòàðíûé îïåðàòîð.Óíèòàðíûå îïåðàòîðû.Ìíîæåñòâî óíèòàðíûõ îïåðàòîðîâ êîíòèíóàëüíî, íî èõ ìîæíîñêîëü óãîäíî òî÷íî ïðåäñòàâèòü â âèäå ïðîèçâåäåíèÿ óíèòàðíûõ îïåðàöèé èç íåêîòîðîãîêîíå÷íîãî óíèâåðñàëüíîãî íàáîðà [8].Òàêîâûì íàáîðîì ÿâëÿåòñÿ, íàïðèìåð, ñîâîêóïíîñòü ñëåäóþùèõ îïåðàòîðîâ:H=√121 11 −1; S=1 00 i; T = π/8 = eiπ/81 0CNOT =  0060100000100 .1 0e−iπ/80iπ/80e;Èçâåñòíî [8], ÷òî ëþáîå îäíîêóáèòíîå óíèòàðíîå ïðåîáðàçîâàíèå ìîæíî ñ ïðîèçâîëüíîé ïðåäñòàâèòü â âèäå ïðîèçâåäåíèÿ O(logc 1/) îïåðàòîðîâ H è π/8 (êîíñòàíòà còî÷íîñòüþïðèáëèçèòåëüíî ðàâíà 2), à ïðîèçâîëüíîå óíèòàðíîå ïðåîáðàçîâàíèå, äåéñòâóþùåå íà q êóáèO(q 2 4q ) îäíîêóáèòíûõ è CNOT îïåðàòî-òàõ ìîæåò áûòü ïðåäñòàâëåíî â âèäå ïðîèçâåäåíèÿðîâ.

Ôàçîâûé îïåðàòîðSâêëþ÷àåòñÿ â ñòàíäàðòíûé íàáîð äëÿ ðåàëèçàöèè êîíòðîëèðóåìûõîïåðàòîðîâ è äëÿ îðãàíèçàöèè ïîìåõîóñòîé÷èâûõ âû÷èñëåíèé.îïåðàòîðàìè âðàùåíèÿ,θ âîêðóã îñåé x̂, ŷ è ẑ ñôåðû Áëîõà:−i sin 2θcos 2θ;Rx̂ (θ) =−i sin 2θcos 2θcos 2θ − sin 2θRŷ (θ) =;sin 2θ cos 2θ!iθe− 2 0.Rẑ (θ) =iθ0 e2Ñëåäóþùèå óíèòàðíûå îïåðàòîðû íàçûâàþòñÿâåòñòâóþò âðàùåíèÿì íà óãîëïîòîìó ÷òî ñîîò-Âîîáùå, ò.ê. ëþáîé óíèòàðíûé îïåðàòîð ñîõðàíÿåò íîðìó âåêòîðà, îí ìîæåò èíòåðïðåòèðîâàòüñÿ íà ñôåðå Áëîõà êàê âðàùåíèå âîêðóã íåêîòîðîé îñè [8].

Çàìåòèì, ÷òîRn̂ (α + β)äëÿ ëþáîé ôèêñèðîâàííîé îñèRn̂ (α)·Rn̂ (β) =n̂.Êðîìå òîãî, èçâåñòíî, ÷òî ëþáîé óíèòàðíûé îïåðàòîðUïðåäñòàâèì â âèäå:U = eiα Rẑ (β)Rŷ (γ)Rẑ (δ)äëÿ íåêîòîðûõ âåùåñòâåííûõ ÷èñåëα, β , γèδ.Ýòî ñîîòâåòñòâóåò òîìó ôàêòó, ÷òî ëþáîåâðàùåíèå òî÷êè íà òðåõìåðíîé ñôåðå ìîæíî ñêîíñòðóèðîâàòü èç îðòîãîíàëüíûõ âðàùåíèé.Çàìåòèì, ÷òî âðàùåíèÿ íà óãîëýòîãî òðåáóåòñÿ ïîâîðîò íà óãîë2πíå ïðèâîäÿò ê òîæäåñòâåííîìó ïðåîáðàçîâàíèþ äëÿ4π :Rẑ (2π) = −I,Rẑ (4π) = I.Ïîëó÷àåìûå â ðåçóëüòàòå ïðèìåíåíèÿ òàêèõ îïåðàòîðîâ ñîñòîÿíèÿ îòëè÷àþòñÿ ëèøü íàìíîæèòåëü−1,íå ïðîÿâëÿþùèéñÿ ïðè èçìåðåíèè, è ïîýòîìó ñîîòâåòñòâóþò îäíîé è òîé æåòî÷êå íà ñôåðå Áëîõà.Òàêèì îáðàçîì, êàæäîìó âðàùåíèþ íà ñôåðå Áëîõà ñîîòâåòñòâóþò äâà ðàçëè÷íûõ óíèòàðíûõ ïðåîáðàçîâàíèÿ, ÷òî ôîðìàëèçóåòñÿ â òåîðèè ãðóïï êàêSO(3)ãðóïïîéäâîéíîå ïîêðûòèåãðóïïûSU (2).Êîíòðîëèðóåìûå îïåðàòîðû, ðåàëèçóþùèå íåêîòîðîå ïðåîáðàçîâàíèå ïðè âûïîëíåíèèîïðåäåëåííîãî óñëîâèÿ, ÿâëÿþòñÿ îñíîâîé äëÿ êâàíòîâîãî ïàðàëëåëèçìà.

Ïóñòü êóáèòû |c1 i,q. . . , |cq i íàõîäÿòñÿ â íåêîòîðîì áàçèñíîì ñîñòîÿíèè. Îïåðàòîð C (U ), óïðàâëÿåìûé êó-|c2 i,áèòàìè|c1 i, |c2 i,...,|cq i,ìîæíî çàäàòü óðàâíåíèåì âèäàC q (U ) |c1 i |c2 i . . . |cq i |ψi = |c1 i |c2 i . . . |cq i U c1 ·c2 ···cq |ψi ,ò.å. óíèòàðíîå ïðåîáðàçîâàíèåêóáèòû|c1 i , |c2 i , . . . , |cq iUïðèìåíÿåòñÿ êöåëåâîìóíàõîäÿòñÿ â áàçèñíîì ñîñòîÿíèèåòñÿ òîæäåñòâåííîå ïðåîáðàçîâàíèåI.êóáèòó|1i,|ψi,åñëè âñåóïðàâëÿþùèåâ ïðîòèâíîì ñëó÷àå ïðèìåíÿ- êâàíòîâûõ ñõåìàõ èç ôóíêöèîíàëüíûõ ýëåìåíòîâ7òàêèå îïåðàòîðû ïðèíÿòî îáîçíà÷àòü ñëåäóþùèì îáðàçîì:|c1 i|c2 i|cq i••...•|ψiUC q (U ), ãäå U îäíîêóáèòíîå óíè2òàðíîå ïðåîáðàçîâàíèå, ìîæíî ðåàëèçîâàòü ïðè ïîìîùè O(q ) îäíîêóáèòíûõ è CNOT îïåðàÈçâåñòíî, ÷òî ïðîèçâîëüíûé êîíòðîëèðóåìûé îïåðàòîðòîðîâ.Êîíòðîëèðóåìûå îïåðàòîðû ìîæíî îáîáùèòü íà ñëó÷àé, êîãäà äëÿ ñðàáàòûâàíèÿ óïðàâëÿþùèå êóáèòû äîëæíû íàõîäèòüñÿ â ñîñòîÿíèè|0i, à íå |1i.

Äëÿ ýòîãî äî è ïîñëå ïðèìåíåíèÿêîíòðîëèðóåìîãî îïåðàòîðà ñîîòâåòñòâóþùèé êóáèò èíâåðòèðóåòñÿ ïðè ïîìîùè îïåðàòîðàîòðèöàíèÿX.Êðîìå òîãî, ââîäèòñÿ ñïåöèàëüíîå îáîçíà÷åíèå:|c1 i|c2 i•|cq i...|ψiÏóñòüd = 2q ,à|1i, |2i,...,|c1 i|c2 i=X|ψi...,|di•X•...|cq iU|ii,X•XU ýòî îðòîíîðìèðîâàííûé áàçèñ âd-ìåðíîìãèëü-áåðòîâîì ïðîñòðàíñòâå.qÎáîçíà÷èì ÷åðåç Ci (U ) (èëè Ci (U )) êîíòðîëèðóåìûé îïåðàòîð ñ q óïðàâëÿþùèìè êóáèòàìè, åñëè ïðåîáðàçîâàíèå U ïðèìåíÿåòñÿ ê öåëåâîìó ðåãèñòðó, òîëüêî êîãäà óïðàâëÿþùèéðåãèñòð íàõîäèëñÿ â ñîñòîÿíèè|ii.Íà ñõåìàõ áóäåì îáîçíà÷àòü òàêîé îïåðàòîð ñëåäóþùèìîáðàçîì:•|c1 i|c2 i|cq i...|ψi3|iiUÊâàíòîâûå ìîäåëè âû÷èñëåíèéÍåôîðìàëüíî, êâàíòîâûå àëãîðèòìû ñîñòîÿò â ïðèìåíåíèè ïîñëåäîâàòåëüíîñòè óíèòàðíûõîïåðàòîðîâ ê íà÷àëüíîìó ñîñòîÿíèþ êóáèòîâ, ò.å. ïîñëåäîâàòåëüíîñòü óìíîæåíèé óíèòàðíûõìàòðèö íà êîìïëåêñíûé âåêòîð.

Ïðè ýòîì, ïîñëåäîâàòåëüíîñòü ìàòðèö ìîæíî çàìåíèòü îäíîé (èõ ïðîèçâåäåíèåì), èç ÷åãî ñëåäóåò, ÷òî êâàíòîâûé àëãîðèòì ïðè îòñóòñòâèè âíåøíåãîâîçäåéñòâèÿ, ïî ñóòè, çàäàåòñÿ óíèòàðíîé ìàòðèöåé.  îáùåì ñëó÷àå, ýòî ñïðàâåäëèâî ëèøüäëÿ ó÷àñòêîâ êâàíòîâîãî àëãîðèòìà ìåæäó âçàèìîäåéñòâèÿìè ñ âíåøíåé ñðåäîé.3.1Êâàíòîâàÿ ìàøèíà ÒüþðèíãàÊâàíòîâàÿ ìàøèíà Òþðèíãà (QTM), îñíîâàííàÿ íà èñïîëüçîâàíèè êâàíòîâîé ñóïåðïîçèöèè êâàíòîâûé àíàëîã âåðîÿòíîñòíîé ìàøèíû Òüþðèíãà âïåðâûå áûëà îïðåäåëåíà Äîé÷åì [4].8Äîé÷ ïðåäïîëîæèë, ÷òî ýòà ìîäåëü ìîæåò áûòü ýôôåêòèâíåå, ÷åì êëàññè÷åñêàÿ, äëÿ íåêîòîðûõ çàäà÷. Îí òàêæå ïîêàçàë ñóùåñòâîâàíèå óíèâåðñàëüíîé êâàíòîâîé ìàøèíû Òüþðèíãà (àòàêæå ìîäåëè êâàíòîâûõ ñåòåé êâàíòîâûé àíàëîã êëàññè÷åñêèõ ñõåì). Îäíàêî åãî ìîäåëüóíèâåðñàëüíîé êâàíòîâîé ìàøèíû Òüþðèíãà èìåëà îäèí íåäîñòàòîê ìîäåëèðîâàíèå äðóãèõêâàíòîâûõ ìàøèí Òüþðèíãà ìîãëî èìåòü ýêñïîíåíöèàëüíóþ ñëîæíîñòü.

Ýòà ïðîáëåìà áûëà ðåøåíà Áåðíøòåéíîì è Âàçèðàíè (1993) [3]. Îíè ïîêàçàëè ñóùåñòâîâàíèå óíèâåðñàëüíîéQTM, ñïîñîáíîé ìîäåëèðîâàòü äðóãèå QTM â ïîëèíîìèàëüíîå âðåìÿ.Êâàíòîâàÿ ìàøèíà Òüþðèíãà.Êàê è â ñëó÷àå íåäåðìèíèðîâàííûõ ìàøèí Òüþðèíãà âêâàíòîâûõ ìàøèíàõ ìîæåò áûòü íåñêîëüêî êîìàíä ñ çàäàííîé ëåâîé ÷àñòüþ:δ1qa −→q (1) a(1) {L, S, R}δ2−→ q (2) a(2) {L, S, R}···δr−→q (r) a(r) {L, S, R},ïðè÷åì êàæäàÿ èç íèõ ïîìå÷åíà íåêîòîðûì êîìïëåêñíûì ÷èñëîì. Ñåìàíòèêà âûïîëíåíèÿòàêèõ êîìàíä çàêëþ÷àåòñÿ â ïàðàëëåëüíîì èõ âûïîëíåíèè ñ àìïëèòóäîé, çàäàííîé ÷èñëîìδi .Ñîîòâåòñòâåííî, ìîæíî çàäàòü ôóíêöèþ ïåðåõîäîâδ : Q × Σ × Q × Σ × {L, S, R} → C,ãäåC ýòî ìíîæåñòâî êîìïëåêñíûõ ÷èñåë, àíàõîäÿñü â ñîñòîÿíèèqè ñ÷èòûâàÿè ñäâèíåòñÿ â íàïðàâëåíèèdaδ(q, a, q 0 , a0 , d) àìïëèòóäà, ñ êîòîðîé ìàøèíà,00íà ëåíòå, ïåðåéäåò â ñîñòîÿíèå q , çàïèøåò a íà ëåíòóíà âõîäíîé ëåíòå.Îïðåäåëåíèå 3.1. Êâàíòîâàÿ Ìàøèíà Òüþðèíãà (Quantum Turing Machine) ýòî ïÿòåðêàM = hΣ, Q, δ, q1 , q0 i, ñîñòîÿùàÿ èç êîíå÷íîãî ìíîæåñòâà ñîñòîÿíèé Q, íà÷àëüíîãî ñîñòîÿíèÿ q1 ∈ Q, çàêëþ÷èòåëüíîãî ñîñòîÿíèÿ q0 ∈ Q, êîíå÷íîãî âõîäíîãî àëôàâèòà Σ, è ôóíêöèèïåðåõîäîâ δ , óäîâëåòâîðÿþùåé óñëîâèþX|δ(q, a, q 0 , a0 , d)|2 = 1(q 0 ,a0 ,d)∈Q×Σ×{L,S,R}äëÿ ëþáûõ (q, a) ∈ Q × Σ.Àíàëîãè÷íî äåòåðìèíèðîâàííîé ìîäåëè îïðåäåëÿþòñÿ ïîíÿòèå êîíôèãóðàöèè, íà÷àëüíîéè çàêëþ÷èòåëüíîé êîíôèãóðàöèé.

 îáùåì ñëó÷àå êîíôèãóðàöèÿ ìîæåò ðàññìàòðèâàòüñÿ êàêêîìáèíàöèÿα1 c1 + . . . + αm cm + . . .áàçèñíûõ êîíôèãóðàöèé. Àññîöèèðóÿ áàçèñíûå êîíôèãóðàöèè ñ ýëåìåíòàìè îðòîíîðìèðîâàííîãî áàçèñà â ãèëüáåðòîâîì ïðîñòðàíñòâå, çàìå÷àåì, ÷òî êîíôèãóðàöèè êâàíòîâîé ìàøèíûÒüþðèíãà ÿâëÿþòñÿ åäèíè÷íûìè âåêòîðàìè â ñîîòâåòñòâóþùåì âåêòîðíîì ïðîñòðàíñòâå, àôóíêöèÿ ïåðåõîäîâ çàäàåò â íåì ëèíåéíîå îòîáðàæåíèåUδ .Uδ äîëæíî áûòü óíèòàðíûì. Ãîâîðÿò, ÷òî êâàíòîâàÿ ìàøèíà Òüþðèíãà ÿâëÿåòñÿ õîðîøî ñôîðìèðîâàííîé (well-formed), åñëèëèíåéíûé îïåðàòîð Uδ ÿâëÿåòñÿ óíèòàðíûì.Ñîãëàñíî ïîñòóëàòàì êâàíòîâîé ìåõàíèêè îòîáðàæåíèå9Píàõîäÿùàÿñÿ â ñóïåðïîçèöèè ñâîèõ êîíôèãóðàöèé ψ =2ðÿåòñÿ, òî ñ âåðîÿòíîñòüþ |αi | ðåçóëüòàòîì èçìåðåíèÿ ÿâëÿåòñÿ êîíôèãóðàöèÿÊîãäà ìàøèíàM,αi ci èçìåci . Âõîäíîåñëîâî ïðèíèìàåòñÿ, åñëè ðåçóëüòàòîì èçìåðåíèÿ ÿâëÿåòñÿ ïðèíèìàþùàÿ êîíôèãóðàöèÿ, èîòâåðãàåòñÿ, åñëè ðåçóëüòàòîì èçìåðåíèÿ ÿâëÿåòñÿ îòâåðãàþùàÿ êîíôèãóðàöèÿ.