Лекция. Квантовый компьютер (Ожигов) (Электронные лекции)

Êâàíòîâûé êîìïüþòåðÞ.È.Îæèãîâ1,21 Ìîñêîâñêèé Ãîñóäàðñòâåííûé Óíèâåðñèòåò èì. Ì.Â.ËîìîíîñîâàÔàêóëüòåò ÂÌÊ, Êàôåäðà ñóïåðêîìïüþòåðîâ è êâàíòîâîé èíôîðìàòèêè2 Ôèçèêî-Òåõíîëîãè÷åñêñèé èíñòèòóò ÐÀÍozhigov@cs.msu.su1 / 25ÑîäåðæàíèåÂâåäåíèåÊðàòêîå îïèñàíèå êâàíòîâîé ìåõàíèêèÁûñòðûå êâàíòîâûå àëãîðèòìûÐåàëèçàöèÿ êâàíòîâûõ ãåéòîâÄåêîãåðåíòíîñòü2 / 25ÂâåäåíèåÊâàíòîâàÿ òåîðèÿ äîëæíà îáúÿñíÿòü âñå.1900 - 1960 ãã.: àíàëèç ìèêðîìèðà ñ òî÷êè çðåíèÿ òî÷íîãî îïèñàíèÿ îòäåëüíûõ ÷àñòèö,ïîãðóæåíèå "âãëóáü" ìèêðîêîñìà.1970 - í.â. : ñèíòåç ñëîæíûõ ñèñòåì íà ìèêðîóðîâíå, êîíäåñèðîâàííûå ñîñòîÿíèÿ ,êâàíòîâûé êîìïüþòåð, ñóïåðêîìïüþòåðíîå ìîäåëèðîâàíèå äèíàìèêè íà êâàíòîâîìóðîâíå.Äàëåå: êâàíòîâàÿ áèîëîãèÿ (ìíîãî-÷àñòè÷íàÿ ÊÌ íåîáõîäèìà äëÿ îáúÿñíåíèÿ îòäåëüíûõýôôåêòîâ), êâàíòîâàÿ ýêîíîìèêà, êâàíòîâàÿ ïîëèòèêà, êâàíòîâîå ïðèíÿòèå ðåøåíèé(îòäåëüíûå ðåçóëüòàòû).3 / 254 / 25Figure: Í.Áîð, À.Ýéíøòåéí, Ì.Ïëàíê, Â.Ãåéçåíáåðã, Ý.Øðåäèíãåð, Ë.äå ÁðîéëüFigure: Ï.Äèðàê, Ð.Ôåéíìàí, Ë.Ëàíäàó, Í.Áîãîëþáîâ5 / 25Êâàíòîâûå ñîñòîÿíèÿ êàê ëèíåéíûå êîìáèíàöèè êëàññè÷åñêèõÏðîöåäóðà êâàíòîâàíèÿP - ïåðåõîä ê ëèíåéíîé îáîëî÷êå.

L(K ) ñîñòîèò èç ëèíåéíûõêîìáèíàöèé |Ψi = j λj |ji, ãäå âñå |ji ∈ K ñ÷èòàþòñÿ âçàèìíî îðòîãîíàëüíûìè ñåäèíè÷íîé íîðìîé. Îáúåäèíåíèå ðåàëüíûõ ñèñòåì ïðèâîäèò ê òåíçîðíîìó ïðîèçâåäåíèþ- ÷òî âåäåò ê ýêñïîíåíöèàëüíîìó ðîñòó ðàçìåðíîñòè ïðîñòðàíñòâà êâàíòîâûõ ñîñòîÿíèé.Îñíîâíàÿ ïðîáëåìà: Ñêîëüêî ýëåìåíòîâ ìîæåò áûòüâ ìíîæåñòâå êëàññè÷åñêèõ ñîñòîÿíèé K ?(K)(K2)(K1)QXK6 / 25K1K2Ïðèíöèï èíòåðôåðåíöèèÀìïëèòóäà âäîëü îäíîãî ïóòè óìíîæàåòñÿ íà êîìïëåêñíîå ÷èñëî,ïðîïîðöèîíàëüíîå ïðîéäåííîìó ïóòè.Àìïëèòóäû âäîëü ðàçíûõ ïóòåé, ïðèõîäÿùèõ â îäíó òî÷êó,ñêëàäûâàþòñÿ.

Ïðè ýòîì íàäî ó÷åñòü âñåâîçìîæíûå ïóòè,âåäóùèå â äàííóþ òî÷êó.Âåðîÿòíîñòü åñòü êâàäðàò ìîäóëÿ àìïëèòóäû.Ýòî ïðàâèëî òî÷íî ôîðìàëèçóåòñÿ â âèäå ìàòðè÷íîé ýâîëþöèè7 / 25Ôåéíìàíîâñêèå äèàãðàììû8 / 25Çåðíî ðàçðåøåíèÿ - ôóíäàìåíòàëüíîå ÷èñëî, òðåáóåìîå äëÿìàòåìàòè÷åñêîé êîððåêòíîñòè êâàíòîâîé ìåõàíèêèÇàðÿä ýëåêòðîíà - àìïëèòóäû âçàèìîäåéñòâèÿ åãî ñ ôîòîíîì.Çàðÿä ýëåêòðîíà òî÷íî íå èçâåñòåí.Ôèêñèðóåòñÿ çåðíî ðàçðåøåíèÿ ïî ïðîñòðàíñòâó è âðåìåíè dx è dt .Óñòàíàâëèâàåòñÿ ïðîáíîå çíà÷åíèå çàðÿäà ýëåêòðîíà è åãî ìàññû.Îïðåäåëÿåòñÿ àìïëèòóäà îñíîâíîãî ïðîöåññà: âçàèìîäåé ñòâèÿ ýëåêòðîíà ñ ôîòîíîì, òàê÷òî âåðîÿòíîñòü, ðàññ÷èòàííàÿ ïî ýòèîé àìïëèòóäå, äàåò ñîãëàñèå ñ ýêñïåðèìåíòàìè.Ïðè óìåíüøåíèè çåðíà ðàçðåøèìîñòè dx, dt ïðîáíûå çàðÿäû è ìàññû èçìåíÿòñÿ, íîâåðîÿòíîñòü áóäåò òîëüêî òî÷íåå ñîâïàäàòü ñ ýêñïåðèìåíòàìè.

Ïðè ýòîì çíà÷åíèÿ çàðÿäàè ìàññû, ïîäîáðàííûå äëÿ îäíîãî ýêñïåðèìåíòà, äàþò ñòîëü æå òî÷íîå ïðåäñêàçàíèå äëÿâñåõ äðóãèõ ýêñïåðèìåíòîâ.Ñõîäèìîñòü ïðîöåññà íàçíà÷åíèÿ çàðÿäîâ è ìàññ íàçûâàåòñÿ òåîðåìîé è ïåðåíîðìèðîâêàõêâàíòîâîé ýëåêòðîäèíàìèêè. Îíà áûëà ñòðîãî äîêàçàíà Í.Áîãîëþáîâûì â 1955 ã.9 / 25Îáû÷íàÿ êâàíòîâàÿ ìåõàíèêà. Ýâîëþöèÿ êâàíòîâîãî ñîñòîÿíèÿâî âðåìåíè1. Ýâîëþöèÿ â ïðèñóòñòâèè íàáëþäàòåëÿ, Pêîòîðûé èçìåðÿåò ñèñòåìó.

Èçìåðåíèåñèñòåìû, íàõîäÿùåéñÿ â ñîñòîÿíèè |Ψi = λj |ji åñòü ñëó÷àéíàÿ âåëè÷èíà, ïðèíèìàþùàÿjçíà÷åíèÿ |ji ñ âåðîÿòíîñòÿìè pj = |λj |2 .˙ = H|Ψi2. Ýâîëþöèÿ â îòñóòñòâèè íàáëþäàòåëÿ: ðåøåíèå óðàâíåíèÿ Øðåäèíãåðà ih|Ψii|Ψ(t)i = Ut |Ψ(0)i, Ut = e − h HtUt : |Ψ(0)i → |Ψ(t)i - îïåðàòîð ýâîëþöèè, H = Ekin + Epot - ýðìèòîâ îïåðàòîð ýíåðãèè;2äëÿ îäíîé ÷àñòèöû â ïîòåíöèàëå V ãàìèëüòîíèàí H = 2pm + V (r ), p = −ih∇.

Äëÿêîíå÷íîìåðíîãî ïðèáëèæåíèÿ H è Ut - ìàòðèöû, |Ψi - ñòîëáåö, çàâèñÿùèé îò âðåìåíè.10 / 25Èíòåãðàë Ôåéíìàíà ïî ïóòÿì - íåïðåðûâíûé àíàëîã ìàòðè÷íîéìåõàíèêèÅñëè åñòü k øàãîâ ïðîäîëæèòåëüíîñòè dt : Ut = Uk Uk−1 . . . U0 , ìàòðè÷íûé ýëåìåíòïåðåõîäà áóäåòXudt (q1 , j)udt (q2 , q1 ) . . . udt (i, qk )ut (i, j) =q1 ,q2 ,...,qk÷òî â íåïðåðûâíîì ñëó÷àå äàåò îïåðàòîð ýâîëþöèè â âèäå ôåéíìàíîâñêîãî ÿäðàZK (2, 1) =γ:1iexp( S[γ])Dγh→2ãäå äåéñòâèå S âäîëü òðàåêòîðèè γ åñòüS[γ] =Rt1L(ẋ, x, t)dt, L = Ekin − Epot , γ : x = x(t), t0 ≤ t ≤ t1 .

Ýâîëþöèÿ èìååò âèät0Ψ(2) =11 / 25ZK (2, 1)Ψ(1)d 1,1 = x1 , 2 = x2Êëàññè÷åñêàÿ ìåõàíèêà êàê ñëåäñòâèå èíòåðôåðåíöèè àìïëèòóäÊëàññè÷åñêàÿ òðàåêòîðèÿ γcl îòëè÷àåòñÿ îò ïðî÷èõ òåì, ÷òî íà íåéèíòåãðàëåZiK (2, 1) =exp( S[γ])DγδS[γcl ]δγ= 0. Ïîýòîìó âhγ:1→2îêðåñòíîñòè êëàññè÷åñêîé òðàåêòîðèè ñêëàäûâàþòñÿ êîíñòðóêòèâíî, à îêðåñòíîñòè ïðî÷èõ- äåñòðóêòèâíî, åñëè ñðåäíåå äåéñòâèå íà ýëåìåíòàðíîì øàãå ïðåâîñõîäèò ïîñòîÿííóþÏëàíêà h ≈ 10−27 erg sec . Åñëè æå ñðåäíåå äåéñòâèå ìàëî, íåêëàññè÷åñêèå òðàåêòîðèèìîãóò äàòü ñåðüåçíûé âêëàä.Íåîáõîäèìîñòü ïðèìåíÿòü êâàíòîâóþ ìåõàíèêó çàâèñèò îò ïðîäîëæèòåëüíîñòè dtýëåìåíòàðíîãî øàãà ìîäåëèðîâàíèÿ ïðîöåññà, òî åñòü îò ñöåíàðèÿ ïðîöåññà.Íàïðèìåð, â çàäà÷å âû÷èñëåíèÿ âîçìîæíûõ ñîñòîÿíèé àññîöèàöèè ìîëåêóë ìîæíîñ÷èòàòü ÿäðà êëàññè÷åñêèìè, à ýëåêòðîíû íóæíî ñ÷èòàòü - êâàíòîâûìè (ìîäåëüÁîðíà-Îïïåðãåéìåðà).12 / 25Ð.Ô.Ôåéíìàí (1918-1988)13 / 25Êâàíòîâûé êîìïüþòåð êàê âûçîâ êâàíòîâîé òåîðèè1. Êâàíòîâûé àëãîðèòì åñòü ðåöåïò ñïåöèàëüíî îãðàíèçîâàííîãî êëàññè÷åñêîãîóïðàâëåíèÿ Ãàìèëüòîíèàíîì H = H(t).

Êâàíòîâîå âû÷èñëåíèå - ñîîòâåòñòâóþùàÿ ýòîìóãàìèëüòîíèàíó ýâîëþöèÿ âîëíîâîé ôóíêöèè êâàíòîâîãî ñîñòîÿíèÿ îïðåäåëåííîé ñèñòåìû÷àñòèö.Ïðåäïîëîæèì, ÷òî íåò íèêàêèõ îãðàíè÷åíèé íà ðàçìåð ìíîæåñòâàKÒîãäà ýâîëþöèÿ âîëíîâîéôóíêöèè |Ψi ïðè ýòîì ìîæåò ïðèâåñòè ê íåïðåäñêàçóåìîìó ðåçóëüòàòó, êîòîðûéíåâîçìîæíî ïîëó÷èòü íèêàêèì êëàññè÷åñêèì àëãîðèòìîì â îáîçðèìîå âðåìÿ. Òàêèåñïîñîáû óïðàâëåíèÿ íàçûâàþòñÿ áûñòðûìè êâàíòîâûìè àëãîðèòìàìè.2. Âñåì ìàòåìàòè÷åñêèì ìåòîäàì êâàíòîâîé òåîðèè ìîæíî ïðèäàòü ôîðìó ýôôåêòèâíûõêëàññè÷åñêèõ àëãîðèòìîâ.3.

Ôèçèêà êâàíòîâûõ êîìïüþòåðîâ òðåáóåò íîâûõ ìåòîäîâ è áîëåå îáùåãîêëàññè÷åñêèõ ñîñòîÿíèé, ïîäëåæàùèõ êâàíòîâàíèþ.âçãëÿäà íà îáëàñòü ïðèëîæåíèé êâàíòîâîé ìåõàíèêè.4. Êðèòåðèé êà÷åñòâà ìàòåìàòè÷åñêîé ìîäåëè: íåèçáåæíàÿ ðåäóêöèÿ âîëíîâîé ôóíêöèèîò óíèòàðíîé ýâîëþöèè â õîäå âû÷èñëåíèÿ äîëæíà ñîâïàäàòü ñ íàáëþäàåìîé âýêñïåðèìåíòàõ äåêîãåðåíòíîñòüþ - ñïîíòàííûì îòêëîíåíèåì íàáëþäàåìûîé äèíàìèêè îò14 / 25óíèòàðíîãîçàêîíà.Ï.Ñ.Øîð15 / 25Ë.Ê.Ãðîâåð16 / 25Àëãîðèòì Ãðîâåðà: êâàäðàòè÷íîå êâàíòîâîå óñêîðåíèåÇàäà÷à íà ïåðåáîð: íàéòè ðåøåíèå xtar óðàâíåíèÿ f (x) = 1, ãäå f - áóëåâñêàÿ ôóíêöèÿ îò nïåðåìåííûõ, çàäàííàÿ â âèäå ñõåì èç ôóíêöèîíàëüíûõ ýëåìåíòîâ.1 /2Îïåðàòîð Ãðîâåðà G - ïîâîðîò íà óãîë arcsin(N −P).

Ðåàëèçóåòñÿ ñ ïîìîùüþ äâóõ1çåðêàëüíûõ îòðàæåíèé: âäîëü âåêòîðà |0̃i = √N j |ji è âäîëü íåèçâåñòíîãî âåêòîðà |xtar i.Ïîñëåäíåå ìîæíî ïðåäñòàâèòü êàê |x, y i → |x, y ⊕ f (x)i - ðåàëèçóåòñÿ, èñõîäÿ èçêëàññè÷åñêîé ñõåìû äëÿ ôóíêöèè f .Àëãîðèòì Ãðîâåðà:ïîâòîðåíèåîïåðàòîðà Gh √ iπ Nðàç4Grover L.K., Proceedings,28th Annual ACM Symposiumon the Theory of Computing,199617 / 25Àëãîðèòì Çàëêè-ÂèçíåðàÍà êâàíòîâîì êîìïüþòåðå ìîæíî ìîäåëèðîâàòü ðåøåíèå óðàâíåíèå Øðåäèíãåðà â ñëó÷àåïðîñòîãî ïîòåíöèàëà çà âðåìÿ O(t 2 ), ãäå t - âðåìÿ ðåàëüíîãî ïðîöåññà, ñ ïàìÿòüþ O(n),ãäå n- ÷èñëî ÷àñòèö â ðåàëüíîé ñèñòåìå.iiiexp(− (Hkin + V (r ))t ≈ (exp(− Hkin dt)exp(− V (r )dt))t/dthhh(Ôîðìóëà Òðîòòåðà, îøèáêà O(dt 2 )).

Îïåðàòîð exp(− hi V (r )dt)) äèàãîíàëåí, è åãî ìîæíîâûïîëíèòü ñ ïîìîùüþ êâàíòîâîãî àëãîðèòìà ñ ïàìÿòüþ ïîðÿäêà ðàçìåðà ðåàëüíîéñèñòåìû. Îïåðàòîð exp(− hi Hkin dt) ïðèâîäèòñÿ ê äèàãîíàëüíîìó ïåðåõîäîì ê èìïóëüñíîìóáàçèñó. Êâàíòîâîå ïðåîáðàçîâàíèå Ôóðüå òðåáóåò ðåñóðñà O(n) ïî âðåìåíè è ïî ïàìÿòè(Øîð); äîñòèæåíèå ìàëîé ðåçóëüòèðóþùåé îøèáêè ïîòðåáóåò dt = O(1/t), ÷òî äàñòêâàäðàòè÷íîå çàìåäëåíèå ïî âðåìåíè ïî ñðàâíåíèþ ñ ðåàëüíûì ïðîöåññîì.C.Zalka, Proc.Roy.Soc.Lond. A454 (1998) 313-322, S.Wiesner, arXiv:quant-ph/960302818 / 25Òåîðåòè÷åñêèå ïðåäåëû âîçìîæíîñòåé êâàíòîâîãî êîìïüþòåðàGeneric Machine Simulation Problem (GMSP): Íàõîæäåíèå ðåçóëüòàòà t - êðàòíîãîïðèìåíåíèÿ çàäàííîé ôóíêöèè F ê äàííîìó àðãóìåíòó x .

GMSP- P-ïîëíàÿ ïðîáëåìà, íåäîïóñêàþùàÿ ðàñïàðàëëåëèâàíèÿ (Limits to Parallel Computation: P-Completeness Theory,R.Greenlaw et al., University of New Hampshire, 1995).Íà êâàíòîâîì êîìïüþòåðå â ìîäåëè F êàê "÷åðíîãî ÿùèêà" ïðè t = O(N 1/7 ) (N - ÷èñëîâñåõ ñîñòîÿíèé ìàøèíû) ñ âåðîÿòíîñòüþ 1 GSMP íå äîïóñêàåò êâàíòîâîãî óñêîðåíèÿ äàæåíà 1 øàã. Áåç îãðàíè÷åíèÿ íà t êâàíòîâîå√âðåìÿ ðåøåíèÿ GSMP ïðîáëåìû ñâåðîÿòíîñòüþ 1 íå ìîæåò áûòü áîëüøå Ω( t) (Ozhigov Y.I., Chaos, Solitons and Fractals, 1999,10 and Proc.R.Soc.Lond.

A 1999, 455).Êâàíòîâûé ïàðàëëåëèçì îêàçûâàåòñÿ òåñíî ñâÿçàí ñ êëàññè÷åñêèì. Áûñòðûå êâàíòîâûåàëãîðèòìû åñòü ðåäêèé ôåíîìåí, èìåþùèé ìåñòî ëèøü äëÿ êëàññè÷åñêèõ àëãîðèòìîâ,äîïóñêàþùèõ ðàñïàðàëëåëèâàíèå (FNC êëàññ ñëîæíîñòè).Ãðîâåðîâñêîå óñêîðåíèå ÿâëÿåòñÿ òèïè÷íûì âåðõíèì ïðåäåëîì äëÿ áîëüøèíñòâà çàäà÷.Ýòîò ïðåäåë ìîæåò ïðåâûøàòüñÿ òîëüêî äëÿ îòäåëüíûõ ÷àñòíûõ ñëó÷àåâ, íàïðèìåð,ôàêòîðèçàöèÿ öåëûõ ÷èñåë (àëãîðèòì Øîðà P. W. Shor, Algorithms for quantum computation:Discrete logarithms and factoring, Proc.

35nd Annual Symposium on Foundations of ComputerScience, IEEE Computer Society Press , 1994 ).19 / 25CNOT ãåéò:|x, y i → |x, x ⊕ y i.íà çàðÿäîâûõ ñîñòîÿíèÿõÊ.À.Âàëèåâ, Ë.Å.Ôåäè÷êèí, Êâàíòîâûå êîìïüþòåðû è êâàíòîâûå âû÷èñëåíèÿ, ò.9, 1, 2009Äëÿ ðåàëèçàöèè ïðîèçâîëüíîãî óíèòàðíîãî îïåðàòîðà äîñòàòî÷íî ðåàëèçîâàòü âñåîäíîêóáèòíûå è êàêóþ-ëèáî çàïóòûâàþùóþ äâóõ-êóáèòíóþ îïåðàöèþ, íàïðèìåð, CNOT.Figure: À.