Лекция. Квантовый компьютер (Ожигов) (1186109)
Текст из файла
Êâàíòîâûé êîìïüþòåðÞ.È.Îæèãîâ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: À.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
