Д.А. Кронберг, Ю.И. Ожигов, А.Ю. Чернявский - Квантовая информатика и квантовый компьютер (1156791), страница 8
Текст из файла (страница 8)
Êâàíòîâàÿ ñèñòåìàäàåòðåçóëüòàò,ÿâëÿþùèéñÿóâåëè÷åíèÿòîëüêîñíåêîòîðîéïðàâèëüíûì.îïåðàöèéâÍîçàâåðîÿòíîñòüþñ÷åòàëãîðèòìåíåáîëüøîãîìîæíîñêîëüóãîäíî ïðèáëèçèòü âåðîÿòíîñòü ïîëó÷åíèÿ ïðàâèëüíîãîðåçóëüòàòà ê åäèíèöå.Ñïîìîùüþáàçîâûõêâàíòîâûõîïåðàöèéìîæíîñèìóëèðîâàòü ðàáîòó îáû÷íûõ ëîãè÷åñêèõ ýëåìåíòîâ, èçêîòîðûõ ñäåëàíû îáû÷íûå êîìïüþòåðû. Ïîýòîìó ëþáóþçàäà÷ó,êîòîðàÿðåøåíàñåé÷àñ,êâàíòîâûéêîìïüþòåððåøèò, è çà òàêîå æå âðåìÿ. Ñëåäîâàòåëüíî, íîâàÿ ñõåìàâû÷èñëåíèé áóäåò íå ñëàáåå íûíåøíåé.×åì æå êâàíòîâûé êîìïüþòåð ëó÷øå êëàññè÷åñêîãî?Êâàíòîâûéêîìïüþòåðñïîñîáåíïîëó÷àòüðåøåíèÿíåêîòîðûõ òèïîâ çàäà÷ (ïåðåáîðíîãî òèïà) çíà÷èòåëüíî49áûñòðåå,÷åìëþáîéêëàññè÷åñêèéêîìïüþòåð.Ýòîèíàçûâàåòñÿ êâàíòîâûì óñêîðåíèåì.42).Îòðàæåíèåìâäîëü|aiâåêòîðàíàçûâàåòñÿîòîáðàæåíèå, äåéñòâèå êîòîðîãî íà áàçèñíûõ âåêòîðàõçàäàåòñÿ ôîðìóëîé|bi,−|ai,Ia : |bi −→if hb|ai = 0,if |bi = |ai.Äîêàçàòü, ÷òî ýòî îòîáðàæåíèå óíèòàðíî.
Ïîñòðîèòüåãî ìàòðèöó. ×òî îíî îçíà÷àåò ãåîìåòðè÷åñêè?|0̄i43). ÏóñòüW |0̄i.- áàçèñíûé âåêòîð âèäà|0̃iW?Íàïèñàòü ðàçëîæåíèå|00 . . . 0i, |0̃i =ïî ñòàíäàðòíîìó áàçèñó.I0̃ ÷åðåç I0̄ è44)**. Ðåàëèçîâàòü íà êâàíòîâîì êîìïüþòåðå îïåðàòîðÊàê âûðàçèòüI0̄.(Óêàçàíèå:ñêàíèðîâàòüêóáèòûàðãóìåíòàñëåâàíàïðàâî, îäíîâðåìåííî ñ íóëåâîé àíöèëëîé, íóæíîé äëÿñáîðàìóñîðà,åäèíèöûàðåçóëüòàòíàêàïëèâàòüââûÿâëåíèÿñïåöèàëüíîìõîòÿáûêóáèòå,îäíîéêîòîðûéïîñëå ñêàíèðîâàíèÿ èñïîëüçîâàòü äëÿ èçìåíåíèÿ çíàêà.Ïîñëå ýòîãî ñäåëàòü âñå îïåðàòîðû â ñêàíèðîâàíèè âîáðàòíîì ïîðÿäêå.)45).
Ïóñòüôóíêöèÿ.f : {0, 1}n −→ {0, 1} - n-Êâàíòîâûéîðàêóë,ñîîòâåòñòâóþùèéäåéñòâóåò íà áàçèñíûå âåêòîðû òàê:|x, yLf (x)iåé,Quf : |x, yi −→(ÿâíî óêàçàíû òîëüêî ðàçðÿäû àðãóìåíòà èçíà÷åíèÿ ôóíêöèè. Ïóñòüñõåìûìåñòíàÿ áóëåâñêàÿèçfçàäàíà â âèäå êëàññè÷åñêîéôóíêöèîíàëüíûõýëåìåíòîâ.êâàíòîâûé àëãîðèòì, ðåàëèçóþùèéÑêîëüêî âûçîâîâfQuf ,Ïîñòðîèòüà òàêæåIxtar .íåîáõîäèìî äëÿ ýòîãî? Ìîæíî ëèîáîéòèñü îäíèì?46). Ïóñòüxtar - åäèíñòâåííûé êîðåíü óðàâíåíèÿ f (x) =1, LR2- âåùåñòâåííàÿ ëèíåéíàÿ îáîëî÷êà (÷òî ýòî òàêîå?)Râåêòîðîâ |0̃i è |xtar i. Äîêàçàòü, ÷òî L2 åñòü èíâàðèàíòîòðàæåíèé Ixtar è I0̃ .5047).
Êàêîâ ãåîìåòðè÷åñêèé ñìûñë îïåðàòîðà ÃðîâåðàG = −Ixtar I0̃ ? (Óêàçàíèå: ðàññìîòðåòü äåéñòâèå G íà LR2 èåãî îðòîãîíàëüíîì äîïîëíåíèè (÷òî ýòî?).48). Ïóñòü óðàâíåíèåf (x) = 1èìååò íå îäèí, àlêîðíåé. Êàêîé ãåîìåòðè÷åñêèé ñìûñë òîãäà áóäåò èìåòüRîãðàíè÷åíèå G íà L2 ?t49). Íàéòè íàòóðàëüíîå t, òàêîå ÷òî G |0̃i ìàêñèìàëüíîáëèçêî|xtar i.Gt |0̃i,êñîñòîÿíèåÅñëèäëÿýòîãîçíà÷åíèÿtèçìåðèòüñ êàêîé âåðîÿòíîñòüþ ïîëó÷èòñÿ|xtar i?Êàê îòâåò çàâèñèò îò ÷èñëà êîðíåé l ?50). Ïîñòðîèòü àëãîðèòì äëÿ íàõîæäåíèÿ êàêîãî-ëèáîêîðíÿ óðàâíåíèÿf (x) = 1íà êâàíòîâîì êîìïüþòåðå.Åñëè èçâåñòíî îáùåå ÷èñëî êîðíåé, òî êàêîâà áóäåò åãîñëîæíîñòü?51). Ðåøèòü çàäà÷ó 50) â ñëó÷àå íåèçâåñòíîãî ÷èñëàâñåõ êîðíåé.52)***.íèæåÄîêàçàòü,êâàíòîâàÿ÷òîñõåìà51ïîìåùåííàÿðåàëèçóåòQF T −1 .ra0ra1ra2a3ra4i rirrirrriirrrb2rrb1rÐèñóíîê 1.
Êâàíòîâàÿ ñõåìà äëÿb4b3rrrrb0QFT−1 .Êðóæêè îáîçíà÷àþò îïåðàòîð Àäàìàðà, äâóõêóáèòíûåîïåðàòîðû èìåþò âèä:Uk,j = Óêàçàíèå:10000000 , k > j.10iπ/2k−j0 e(2.1)Çàôèêñèðîâàòü äâà ïðîèçâîëüíûõ áàçèñíûõPPaj 2j è b =bk 2k è ðàññìîòðåòü,jkñîñòîÿíèÿa =ñàìïëèòóäîéêàêîé0100aïåðåõîäèòâb(ýòîåñòüñîîòâåòñòâóþùèé ýëåìåíò ìàòðèöû îïåðàòîðà, î êîòîðîì−1íàäî äîêàçàòü, ÷òî îí ðàâåí QF T- ñì. îïðåäåëåíèå52îáðàòíîãî êâàíòîâîãî ïðåîáðàçîâàíèÿ Ôóðüå èç çàäà÷è17).) Àìïëèòóäà åñòü êîìïëåêñíîå ÷èñëî, ó êîòðîãî åñòüìîäóëü è ôàçà. Ïðîñëåäèòü ïðîöåññ èçìåíåíèÿ òåêóùåãîâåêòîðà ñîñòîÿíèÿ êâàíòîâîãî âû÷èñëåíèÿ - ñëåâà íàïðàâîâ ïîêàçàííîé ñõåìå.
Ïðè âñòðå÷å ñ îïåðàòîðîì Àäàìàðàìåíÿåòñÿ ìîäóëü àìïëèòóäû (à ïðè äâóõêóáèòíûõ?) âûïèñàòüåãîðåçóëüòèðóþùååèçìåíåíèåèóáåäèòüñÿ,÷òî îíî òàêîå, êàêîå íàäî. Ïîñëå ýòîãî ïîñ÷èòàòü ôàçój>kìåæäó jàìïëèòóäû. Äëÿ ýòîãî çàôèêñèðîâàòü äâà çíà÷åíèÿè îïðåäåëèòü âêëàä äâóõêóáèòíîãî îïåðàòîðàèkajêóáèòàìè. Îáðàòèòü âíèìàíèå íà îáðàòíûé ïîðÿäîêèbkíà âõîäå è âûõîäå. Èñïîëüçîâàòü, òî, ÷òîïåðåõîäèò âbn−j+1ajòîëüêî â ðåçóëüòàòå îïðåäåëåííîãîîïåðàòîðà Àäàìàðà.
Ïðîñóììèðîâàòü âñå âêëàäû â ôàçóè óáåäèòüñÿ, ÷òî îíè äàþò òî, ÷òî òðåáóåòñÿ îïåðàòîðîìQF T −1 . Ïðè íåîáõîäèìîñòè èñïîëüçîâàòü ïîñîáèå ([65]) àòàêæå ïåðâîèñòî÷íèê ([40]).53). Äàíà ñõåìà êâàíòîâûõ âåíòèëåé, ðåàëèçóþùàÿóíèòàðíûé îïåðàòîðîïåðàòîðUseq |Ψ, aiU . Ïîñòðîèòü= (U a |ψi|ai,ñõåìó, ðåàëèçóþùóþãäåa-îäèíêóáèò(îïåðàòîð óñëîâíîãî ïðèìåíåíèÿ, òèïà CNOT). Óêàçàíèå:ðàñøèðèòü íàáîð ýëåìåíòàðíûé âåíòèëåé, âêëþ÷èâ â íåãîóñëîâíûå âåíòèëè òèïà CNOT äëÿ âñåõ èñïîëüçóþùèõñÿâåíòèëåé.54)**.  óñëîâèÿõ çàäà÷è 53) ðåàëèçîâàòüa-Useqäëÿïðîèçâîëüíîå ÷èñëî êóáèòîâ.
Êàêîâà ñëîæíîñòü ýòîãîêâàíòîâîãî àëãîðèòìà?a- n-êóáèòíûé ðåãèñòð, à ñîáñòâåííûå ÷èñëànâèä exp(2πiwk ) ãäå wk èìåþò âèä k/2 , k -55). ÏóñòüUèìåþòíàòóðàëüíîå. Ïîêàçàòü, ÷òî ïðèìåíåíèå îïåðàòîðàRevU = QF T2 Useqãäåïîñëåäíèéíà÷àëüíîìóîïåðàòîðñîñòîÿíèþïðèìåíÿåòñÿâèäà53|ψ, 0̃iêèàíöèëëå,êïîñëåäóþùååèçìåðåíèå àíöèëëû äàñò îäíî èç ÷èñåëâû÷èñëèòüðåçóëüòàòïðèìåíåíèÿwk .(Óêàçàíèå:îïåðàòîðà.)Ýòîòàëãîðèòì ïðèíàäëåæèò Àáðàìñó è Ëëîéäó.  ÷àñòíîìñëó÷àå, êîãäàUåñòü óìíîæåíèå íà íàòóðàëüíîå ÷èñëî,åãî èñïîëüçîâàë Øîð.56)***.çàäà÷è 55)nñïîñîáíà äàòü ïðèáëèæåíèå ñ òî÷íîñòüþ äî s/2 îäíîãîwkèçÏîêàçàòü,ñ÷òîïðîöåäóðà1 − 1/s,âåðîÿòíîñòüþèçäàæååñëèwkíåèìåþò óêàçàííîãî â çàäà÷å 55) âèäà.
(Óêàçàíèå: îöåíèòüâåðîÿòíîñòüîøèáêè,ïðèáëèæåíèÿñåñëèòî÷íîñòüþöåëünñîñòîèòs/2äëÿâïîëó÷åíèèíàòóðàëüíîãîs.Ìîæíî âîñïîëüçîâàòüñÿ ïîñîáèåì ([?]). )qxn−157)***. Ïóñòü q - íàòóðàëüíîå ÷èñëî, òàêîå ÷òî 2<nr< 2 , x = 1 (mod(q)) (r - ìóëüòèïëèêàòèâíûé ïåðèîäUx äåéñòâóåò íà n êóáèòíîåáàçèñíîå ñîñòîÿíèå êàê Ux |yi = |yx mod(q)i åñëè y < qnè Ux |yi = |yi åñëè y = q, q + 1, .
. . , 2 − 1. Äîêàçàòü,÷òî ïðèìåíåíèå RevUx ê ñîñòîÿíèþ èç çàäà÷è 55) èïî ìîäóëþq ),îïåðàòîðïîñëåäóþùåå èçìåðåíèå àíöèëëû ïîçâîëÿåò âû÷èñëèòür.(Óêàçàíèå: èñïîëüçîâàòü ðåçóëüòàò çàäà÷è 56). Êàêîâàñëîæíîñòü äàííîãî àëãîðèòìà?58)***. Ïîêàçàòü, ÷òî ñëîæîñòü àëãîðèòìà èç çàäà÷è57)ìîæíîðàäèêàëüíîUxðåàëèçàöèþóìåíüøèòü,ýêîíîìíûìseqðåçóëüòàòîâàëãîðèòìöåëîãîçàäà÷Ï.Øîðà÷èñëàq.56)-58)ýòîãîìóëüòèïëèêàòèâíûåïåðèîäû÷èñåëq;ïî2ìîäóëþ3âûòåêàåòêâàíòîâûéôàêòîðèçàöèèÄëÿñäåëàòüèñïîëüçóÿx , d = 0, 1, 2, .
. ..ïîñëåäîâàòåëüíîå óìíîæåíèå âèäàÈçåñëèîáðàçîì,2díàäîïðîèçâîëüíîãîóìåòüñëó÷àéíîñëîæíîñòüýòîãîíàõîäèòüâûáðàííûõàëãîðèòìàO(log q) log (log q)ïðîñòîãîíå íàìíîãî ïðåâûøàåò ñëîæíîñòü2óìíîæåíèÿ öåëûõ ÷èñåë (logq ). ÀëãîðèòìØîðà ÿâëÿåòñÿ ñàìûì áûñòðûì èç èçâåñòíûõ êâàíòîâûõàëãîðèòìîâ. Ê ñîæàëåíèþ, äî ñèõ ïîð íå äîêàçàíî, ÷òî íå54ñóùåñòâóåò ñòîëü æå áûñòðîãî êëàññè÷åñêîãî àëãîðèòìà.Ñàìûé áûñòðûé èç èçâåñòíûõ êëàññè÷åñêèõ àëãîðèòìîâ1/3).òðåáóåò âðåìåíè O(q59). Èñïîëüçóÿ ðåçóëüòàò çàäà÷è 52), äîêàçàòü, ÷òîïðèáëèæåííîå ïðåîáðàçîâàíèå Ôóðüå ìîæíî ðåàëèçîâàòüO(n) ãäå n - ÷èñëî êóáèòîâ.
(Óêàçàíèå: îòáðîñèòüäâóõêóáèòíûå âåíòèëè ñ áîëüøèì çíà÷åíèåì |j − k| èçà âðåìÿîöåíèòü âîçíèêàþùóþ ïðè ýòîì îøèáêó.)60). Äîêàçàòü ôîðìóëó Òðîòòåðà exp(A + B)≈11m(exp( m A)exp( m B)) äëÿ ýðìèòîâûõ ìàòðèö A è B (âàæíàëè çäåñü ýðìèòîâîñòü?). Îöåíèòü îøèáêó ýòîé ôîðìóëû.(Óêàçàíèå: ïðèìåíèòü ðàçëîæåíèå â ðÿä ýêñïîíåíòû).exp(A + B)61).
Âûâåñòè áîëåå òî÷íîå âûðàæåíå äëÿ÷åì ôîðìóëà Òðîòòåðà.62)***.ìîæíîÄîêàçàòü,ïîëó÷èòüêóáèòîâûìíàñîñòîÿíèåØðåäèíãåðà÷àñòèöïîòåíöèàëûçàêâàíòîâîìèçïðèáëèæåíèåìóðàâíåíèÿðåàëüíûõ÷òîO(n)êóáèò,òî÷íîãîäëÿâçàèìîäåéñòâèÿñëóæàùååΨ(t, r)ñèñòåìû èç nðåøåíèÿêâàíòîâîéO(t2 ), ïðèâðåìÿêîìïüþòåðåìåæäóóñëîâèè,÷àñòèöàìè÷òîèìåþòïðîñòîé àëãîðèòì âû÷èñëåíèÿ (ñõåìó èç ôóíêöèîíàëüíûõýëåìåíòîâ). Óêàçàíèå: èñïîëüçóÿ ðåçóëüòàòû çàäà÷ 18),20)è52),ïðåäñòàâèòüãàìèëüòîíèàíââèäåñóììûêèíåòè÷åñêîé è ïîòåíöèàëüíîé ýíåðãèé è ïðèìåíèòü êâîçíèêàþùèìïðèìåðèòüýêñïîíåíòûìðåçóëüòàòûôîðìóëóçàäà÷18)èÒðîòòåðà.20)êÇàòåìèìïóëüñíîé÷àñòè.
Èñïîëüçîâàòü òàêæå èìåþùèåñÿ ñõåìû âû÷èñëåíèÿïîòåíöèàëîâ.Áûëîïîêàçàíî,âîçìîæíî÷òî¾êâàíòîâîåâîçìîæíîñòüïðîèçâîëüíîãîïîëó÷åíèÿíåäëÿâñÿêîãîàëãîðèòìàóñêîðåíèå¿.Áîëååêâàíòîâîãîóñêîðåíèÿêëàññè÷åñêîãîàëãîðèòìàòîãî,äëÿÿâëÿåòñÿáîëüøîé ðåäêîñòüþ ([30])Ïðèìåíåíèå èäåé êâàíòîâîé ìåõàíèêè óæå îòêðûëè55íîâóþ ýïîõó â îáëàñòè êðèïòîãðàôèè, òàê êàê ìåòîäûÊâàíòîâàÿêðèïòîãðàôèÿ|êâàíòîâîéîòêðûâàþòíîâûåâîçìîæíîñòèâêðèïòîãðàôèèîáëàñòèïåðåäà÷èñîîáùåíèé. Ïðîòîòèïû ñèñòåì ïîäîáíîãî ðîäà íàõîäÿòñÿíà ñòàäèè ðàçðàáîòêè2.1Ôèçè÷åñêèåðåàëèçàöèèêâàíòîâûõ êîìïüþòåðîâÏîñòðîåíèåêâàíòîâîãîêîìïüþòåðàââèäåðåàëüíîãîôèçè÷åñêîãî ïðèáîðà ÿâëÿåòñÿ ôóíäàìåíòàëüíîé çàäà÷åéôèçèêè 21 âåêà.  íàñòîÿùåå âðåìÿ ïîñòðîåíû òîëüêîîãðàíè÷åííûå åãî âàðèàíòû (â ïðåäåëàõ 10 êóáèò).
Âîïðîñîòîì,äîêàêîéñòåïåíèâîçìîæíîìàñøòàáèðîâàíèåòàêîãî óñòðîéñòâà, ÿâëÿåòñÿ ïðåäìåòîì íîâîé èíòåíñèâíîðàçâèâàþùåéñÿîáëàñòè-ìíîãî÷àñòè÷íîéêâàíòîâîéìåõàíèêè. Öåíòðàëüíûì çäåñü ÿâëÿåòñÿ âîïðîñ î ïðèðîäåäåêîãåðåíòíîñòè (òî÷íåå, î êîëëàïñå âîëíîâîé ôóíêöèè),êîòîðûé ïîêà îñòàåòñÿ îòêðûòûì. Ðàçëè÷íûå òðàêòîâêèýòîãîïðîöåññàÏðèâåäåììîæíîïðèìåðíàéòèðåàëèçàöèèâñïèñêåîïåðàöèèëèòåðàòóðû.CNOTíàçàðÿäîâûõ ñîñòîÿíèÿõ ýëåêòðîíà â êâàíòîâûõ òî÷êàõ.Îäèí êóáèò ìîæíî ïðåäñòàâèòü â âèäå ýëåêòðîíà âäâóõ ÿìíîì ïîòåíöèàëå, òàê ÷òîåãî â ëåâîé ÿìå, à|1i|0iîçíà÷àåò íàõîæäåíèå- â ïðàâîé. Ýòî íàçûâàåòñÿ êóáèò íàçàðÿäîâûõ ñîñòîÿíèÿõ. Îáùèé âèä êâàíòîâîãî ñîñòîÿíèÿòàêîãî ýëåêòðîíà:|Ψi = λ0 |0i + λ1 |1i.Çàâèñèìîñòü åãî îò âðåìåíè åñòü çàâèñèìîñòü îò âðåìåíèàìïëèòóäλ0 , λ1 ;îíà çàäàåòñÿ óðàâíåíèåì Øðåäèíãåðàâèäàih∂ΨΨ = HΨ,∂t56ãäå ãàìèëüòîíèàíHèìååò â ñèëó îäèíàêîâîãî âèäà ÿì èýðìèòîâîñòè âèääëÿ íåêîòîðîé êîíñòàíòû−aaa−aa,òàê ÷òî âåêòîð1|0̃i = √ (|0i + |1i)2åñòüñîáñòâåííûéñîáñòâåííûìâåêòîðçíà÷åíèåìýòîãî0(òàêãàìèëüòîíèàíàíàçûâàåìîåñîñíîâíîåñîñòîÿíèå), à1|1̃i = √ (|0i − |1i)2-ñîáñòâåííûéâåêòîðñîçíà÷åíèåì2a(ïåðâîåâîçáóæäåííîå ñîñòîÿíèå).
Íèêàêèõ äðóãèõ ñîáñòâåííûõñîñòîÿíèé(ñîïðåäåëåííûìçíà÷åíèåìýíåðãèè)çäåñüíåò, òàê êàê íàøà çàäà÷à äâóìåðíàÿ. Ïîñêîëüêó êàæäîåñîñòîÿíèå|Ψiïåðåõîäèò çà âðåìÿtâ ñîñòîÿíèåλ0 exp(0t)|0̃i + λ1 exp(−2at/h)|1̃i,òî äëÿ ðåàëèçàöèè îïåðàöèè NOT (ïåðåõîäàè íàîáîðîò) äîñòàòî÷íî ïðîñòî ïîäîæäàòüπh/2a.|0i− > |1iâðåìÿ t =Òî åñòü ãåéò NOT äàåòñÿ ïðîñòî åñòåñòâåííîéêâàíòîâîé ýâîëþöèåé íàøåãî êóáèòà ïðè óñëîâèè, ÷òîâíåøíèé ïîòåíöèàë çàäàåò äâóõ ÿìíóþ ñòðóêòóðó; ýòîäåëàåòñÿ ñ ïîìîùüþ òåõíîëîãèè êâàíòîâûõ òî÷åê.Äëÿ ðåàëèçàöèè CNOT íàäî ðàñïîëîæèòü äâà êóáèòà(òî åñòü äâå ïàðû ÿì) ïåðïåíäèêóëÿðíî äðóã äðóãó, è âêàæäîé èç íèõ ðàñïîëîæèòü ïî îòäåëüíîìó ýëåêòðîíó.Òîãäà êîíñòàíòàáóäåòçàâèñåòüaîòäëÿ ïåðâîé (óïðàâëÿåìîé) ïàðû ÿìòîãî,âêàêîìñîñòîÿíèèíàõîäèòñÿýëåêòðîí âî âòîðîé (óïðàâëÿþùåé) ïàðå ÿì: åñëè áëèæåê ïåðâîé,aáóäåò áîëüøå, åñëè äàëüøå - ìåíüøå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
