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

Êâàíòîâûå âû÷èñëåíèÿ äëÿ ïðîãðàììèñòîâÂàñèëüåâ À.Â.1ÂâåäåíèåÍà÷àëî ðàáîò â îáëàñòè êâàíòîâûõ âû÷èñëåíèé ñâÿçûâàåòñÿ ñî ñòàòüåé [6], îïóáëèêîâàííîéÐè÷àðäîì Ôåéíìàíîì â 1982 ãîäó è ïîñâÿùåííîé êîìïüþòåðíîìó ìîäåëèðîâàíèþ êâàíòîâîìåõàíè÷åñêèõ ïðîöåññîâ íà âû÷èñëèòåëüíûõ ìàøèíàõ. Îí çàìåòèë, ÷òî ñ ðîñòîì ðàçìåðíîñòèôèçè÷åñêîé çàäà÷è ïðîñòðàíñòâî ñîñòîÿíèé âîçðàñòàåò ýêñïîíåíöèàëüíî, ïîýòîìó ýôôåêòèâíîå ìîäåëèðîâàíèå ìíîãî÷àñòè÷íîé êâàíòîâîé ìåõàíèêè íà êëàññè÷åñêîì êîìïüþòåðå íåâîçìîæíî. Èñõîäÿ èç ýòîãî, Ôåéíìàí âûäâèíóë èäåþ êâàíòîâîãî êîìïüþòåðà êîìïüþòåðà,èñïîëüçóþùåãî â ñâîåé îñíîâå êâàíòîâûå ýôôåêòû, òàêèå, êàê ñóïåðïîçèöèÿ è, ãëàâíîå, çàïóòàííîñòü. Ñ ýòîé ðàáîòû íà÷àëèñü ñîâðåìåííûå èññëåäîâàíèÿ ïðîáëåìû èñïîëüçîâàíèÿêâàíòîâî ìåõàíè÷åñêèõ ýôôåêòîâ ïðè ðåøåíèè çàäà÷, òðåáóþùèõ áîëüøèõ âû÷èñëèòåëüíûõðåñóðñîâ.Âïåðâûå ôîðìàëüíàÿ ìîäåëü óíèâåðñàëüíîãî êâàíòîâîãî êîìïüþòåðà (êâàíòîâàÿ ìàøèíàÒüþðèíãà) áûëà ïðåäëîæåíà Ï.

Áåíèîôôîì ãîäó è ðàçâèòà Ä. Äîé÷åì [4]. Áîëåå íàãëÿäíàÿìîäåëü êâàíòîâûõ âû÷èñëåíèé (ýêâèâàëåíòíàÿ êâàíòîâîé ìàøèíå Òüþðèíãà) êâàíòîâûåñõåìû, áûëà ïðåäëîæåíà Ä. Äîé÷åì [5].Îòìåòèì, ÷òî êâàíòîâûå ìîäåëè âû÷èñëåíèé íå íàðóøàþò òåçèñ Òüþðèíãà-×åð÷à, ò.ê. ìîãóò áûòü ïðîìîäåëèðîâàíû íà äåòåðìèíèðîâàííûõ àíàëîãàõ. Ðàçëè÷èå ìåæäó êëàññè÷åñêèìèè êâàíòîâûìè ìîäåëÿìè ïðîÿâëÿþòñÿ ëèøü â ýôôåêòèâíîñòè âû÷èñëåíèé. ÷åì æå ïðåèìóùåñòâà êâàíòîâûõ âû÷èñëåíèé è êàêèå ó íèõ ñëàáîñòè?Íàèáîëüøèå íàäåæäû âîçëàãàþòñÿ íàêâàíòîâûé ïàðàëëåëèçì âîçìîæíîñòü êâàíòî-âîãî ðåãèñòðà íàõîäèòüñÿ îäíîâðåìåííî âî âñåõ ñâîèõ ñîñòîÿíèÿõ. Òàê, åñëè êëàññè÷åñêèén-áèòíûéðåãèñòð íàõîäèòñÿ ðîâíî â îäíîì èç ñâîèõ ñîñòîÿíèé, òî n-áèòíûé êâàíòîâûé ðånãèñòð ñðàçó âî âñåõ 2 áàçèñíûõ ñîñòîÿíèÿõ.

Ñ îäíîé ñòîðîíû, ýòî ïîçâîëÿåò ïðîèçâîäèòüâû÷èñëåíèÿ ñðàçó íà ìíîæåñòâå íàáîðîâ, â òîì ÷èñëå íà âñåõ íàáîðàõ ñðàçó. Îäíàêî íåïîñðåäñòâåííîå ïðèìåíåíèå ýòîãî ïðèåìà íè÷åãî íå äàåò, ïîñêîëüêó äîñòîâåðíî èçâëå÷ü íóæíûéîòâåò íå óäàñòñÿ. Ïîòðåáóåòñÿ ïðåîáðàçîâàíèå ñîñòîÿíèÿ òàêèì îáðàçîì, ÷òîáû íóæíûé îòâåòïîëó÷èë áû áîëüøóþ àìïëèòóäó, à çíà÷èò ïðîÿâèëñÿ ïðè èçìåðåíèè ñ áîëüøîé âåðîÿòíîñòüþ. ðåøåíèè óêàçàííîé ïðîáëåìû ìîæåò ïîìî÷ü äðóãàÿ îñîáåííîñòü êâàíòîâûõ âû÷èñëèòåëåé íàëè÷èå èíòåðôåðåíöèè ìåæäó ñîñòîÿíèÿìè, âîçíèêàþùåé èç-çà òîãî, ÷òî íîâûå àìïëèòóäûáàçèñíûõ ñîñòîÿíèé îêàçûâàþòñÿ ëèíåéíûìè êîìáèíàöèÿìè ñòàðûõ àìïëèòóä.

Ýòî ïîçâîëÿåòñòðîèòü àëãîðèòìû òàêèì îáðàçîì, ÷òîáû íåâåðíûå ðåøåíèÿ èñ÷åçàëè çà ñ÷åò äåñòðóêòèâíîéèíòåðôåðåíöèè (óìåíüøàþùåé àìïëèòóäó), â òî âðåìÿ êàê æåëàåìûå ñîñòîÿíèÿ óñèëèâàëèñüïðè êîíñòðóêòèâíîé èíòåðôåðåíöèè (óâåëè÷èâàþùåé àìïëèòóäó).Âàæíîé îñîáåííîñòüþ òàêæå ÿâëÿåòñÿ âîçìîæíîñòü ñîçäàâàòü(entangled states)çàïóòàííûå ñîñòîÿíèÿñîâîêóïíîñòè êóáèò, êîãäà íåâîçìîæíî ïðèïèñàòü îïðåäåëåííîå ñîñòîÿíèåêàæäîìó èç íèõ. Çàïóòàííûå ñîñòîÿíèÿ ìîæíî çàäàòü ýêñïîíåíöèàëüíûì ÷èñëîì êîìïëåêñíîçíà÷íûõ àìïëèòóä, à äëÿ íå çàïóòàííîãî ñîñòîÿíèÿ äîñòàòî÷íî èõ ëèíåéíîãî ÷èñëà. Ïðè1ýòîì êâàíòîâàÿ çàïóòàííîñòü ÿâëÿåòñÿ íåîáõîäèìûì óñëîâèåì äëÿ ýêñïîíåíöèàëüíîãî óñêîðåíèÿ â êâàíòîâûõ âû÷èñëåíèÿõ. Äæîçñà è Ëèíäåí ïîêàçàëè [7], ÷òî åñëè ìàêñèìàëüíûé ðàíãØìèäòà (äèñêðåòíàÿ ìåðà äâóõ÷àñòè÷íîé çàïóòàííîñòè) ïðè êâàíòîâûõ âû÷èñëåíèÿõ ÿâëÿåòñÿ êîíñòàíòîé (íå çàâèñèò îò ÷èñëà êóáèò), òî òàêîå âû÷èñëåíèå ìîæíî çà ïîëèíîìèàëüíîåâðåìÿ ñìîäåëèðîâàòü íà êâàíòîâîì êîìïüþòåðå.

Áîëåå ñèëüíûé ðåçóëüòàò áûë ïîëó÷åí Âèäàëîì [11]. Ðåçóëüòàò ñîñòîèò â òîì, ÷òî ýôôåêòèâíîå (çà ïîëèíîìèàëüíîå âðåìÿ) êëàññè÷åñêîåìîäåëèðîâàíèå âîçìîæíî, äàæå åñëè ìàêñèìàëüíîå ÷èñëî Øìèäòà ïîëèíîìèàëüíî çàâèñèòîò ÷èñëà êóáèò.Ñëàáîñòè êâàíòîâûõ âû÷èñëåíèé ÿâëÿþòñÿ ïðîäîëæåíèåì èõ ñèëüíûõ ñòîðîí.

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

Ïîýòîìó ðàçðàáîòêà êâàíòîâûõ àëãîðèòìîâ òðåáóåò îñîáîé èíòóèöèè êëàññè÷åñêèå ïîäõîäû ñðàáàòûâàþò äàëåêî íå âñåãäà.Åùå îäíà îñîáåííîñòü êâàíòîâûõ âû÷èñëåíèé îáðàòèìîñòü èñïîëüçóåìûõ ïðåîáðàçîâàíèé íå ïðåäñòàâëÿåò ïðîáëåìû, åñëè íåò îãðàíè÷åíèé íà ðàçìåð êâàíòîâîãî ðåãèñòðà. Îäíàêî ïðè äîâîëüíî óìåðåííûõ îãðàíè÷åíèÿõ (ïîðÿäêàO(log n) êóáèò, ãäå n äëèíà âõîäíîãîíàáîðà) âû÷èñëåíèå ìíîãèõ ôóíêöèé îêàçûâàåòñÿ çàòðóäíåíî, à ñîîòâåòñòâóþùèå çàäà÷è âòàêèõ ìîäåëÿõ ñ îãðàíè÷åíèÿìè ìîãóò èìåòü ýêñïîíåíöèàëüíóþ ñëîæíîñòü [9].Îòìåòèì òàêæå, ÷òî ìíîãî÷àñòè÷íàÿ çàïóòàííîñòü, áóäó÷è íåîáõîäèìûì óñëîâèåì êâàíòîâîãî óñêîðåíèÿ, ÿâëÿåòñÿ è ãëàâíûì îñòàíàâëèâàþùèì ôàêòîðîì íà ïóòè ê ñîçäàíèþ êâàíòîâîãî êîìïüþòåðà. Äëÿ ýôôåêòèâíûõ âû÷èñëåíèé íåîáõîäèìî íå òîëüêî óïðàâëÿòü, íî èñîõðàíÿòü êâàíòîâóþ çàïóòàííîñòü, ÷åìó ìåøàåò ïðîöåññ äåêîãåðåíòíîñòè.

 ñîâðåìåííîéòðàêòîâêå äåêîãåðåíòíîñòü ðàçðóøåíèå êâàíòîâîãî ñîñòîÿíèÿ (è, ãëàâíîå, åãî çàïóòàííîñòè) ïîä äåéñòâèåì âíåøíåé ñðåäû.2Ìàòåìàòè÷åñêèé àïïàðàò êâàíòîâûõ âû÷èñëåíèé Ëèíåéíàÿ àëãåáðàÊâàíòîâûå âû÷èñëåíèÿ îñíîâûâàþòñÿ íà òîì, ÷òî íîñèòåëÿìè èíôîðìàöèè ÿâëÿþòñÿ êâàíòîâîìåõàíè÷åñêèå ñèñòåìû èç ìèêðîìèðà, à, ñëåäîâàòåëüíî, èõ ñîñòîÿíèÿ è ïðåîáðàçîâàíèÿ îïèñûâàþòñÿ ïîñòóëàòàìè êâàíòîâîé ìåõàíèêè. Ïðèâåäåì íåîáõîäèìûå îáîçíà÷åíèÿ è ñâåäåíèÿèç êíèãè [8].dÏóñòü H d-ìåðíîåãèëüáåðòîâî ïðîñòðàíñòâî (êîìïëåêñíîå ëèíåéíîå âåêòîðíîå ïðî-ñòðàíñòâî ñ îïðåäåëåííûì â íåì ñêàëÿðíûì ïðîèçâåäåíèåì).

Äëÿ îáîçíà÷åíèÿ ýëåìåíòîâdïðîñòðàíñòâà H ïðèíÿòî èñïîëüçîâàòü bra-ket íîòàöèþ Äèðàêà: |ψi è hψ| äëÿ âåêòîðàñòîëáöà è âåêòîðà-ñòðîêè, ñîîòâåòñòâåííî. Òàêæå áóäåì èñïîëüçîâàòühψ1 | ψ2 i äëÿ ñêàëÿðíîãîïðîèçâåäåíèÿ.Òåíçîðíîå ïðîèçâåäåíèå.ïðîèçâåäåíèåìàòðèöÂâåäåì îáîçíà÷åíèåA, B .2A⊗Bòåíçîðíîå (ïðàâîå êðîíåêåðîâî)ÄëÿA=a11···a1n.........am1 · · ·A⊗B =|a1 i , . . .

, |aq i ∈ H2èb11 · · ·...B=a11 B···........bl1 · · ·a1n B...amn BamnÄëÿ âåêòîðîâ.am1 B · · ·b1k...blkáóäåì òàêæå èñïîëüçîâàòü îáîçíà÷åíèÿq|a1 i ⊗ · · · ⊗ |aq i = |a1 . . . aq i ∈ H2 .Ñòàíäàðòíûé âû÷èñëèòåëüíûé áàçèñ â H2q êà÷åñòâå ñòàíäàðòíîãî áàçèñà âH2ðàñ-ñìàòðèâàåòñÿ ñëåäóþùèé:|0i =Äëÿ ïðîñòðàíñòâHd10|1i =,01áîëüøåé ðàçìåðíîñòè ââîäÿòñÿ äîïîëíèòåëüíûå îáîçíà÷åíèÿ:= (100 .

. . 0 . . . 0)T= (010 . . . 0 . . . 0)T|1i = |00 . . . 0i|2i = |00 . . . 1i...|ii= |bin(i − 1)i = (000 . . . 1 . . . 0)T...= (000 . . . 0 . . . 1)T .|di = |11 . . . 1iÇäåñü ó âåêòîðà|iiíài-éïîçèöèè1,à âñå îñòàëüíûå êîìïîíåíòû íóëåâûå.Óêàçàííûå ðàâåíñòâà ëåãêî ïðîâåðèòü. Íàïðèìåð, ðàññìîòðèì âåêòîð-ñòîëáåö, ñîîòâåòñòâóþùèé|010i = |3i:  10  0· 0  001 =|10i = |1i ⊗ |0i =⊗=  11011·00    00 0    0  1·     1    1     0   =  0  = |3i .|010i = |0i ⊗ |10i =   0 0   0    0  0·     1    0 00Î÷åâèäíî, ÷òî ñèñòåìà âåêòîðîâ |1i, |2i, .

. . , |ii, . . . , |di îáðàçóåò îðòîíîðìèðîâàííûé áàHd . Áóäåì òàêæå îáîçíà÷àòü óêàçàííûå âåêòîðû ÷åðåç |00 . . . 0i, |00 . . . 1i,çèñ â ïðîñòðàíñòâå...,|bin(i − 1)i,...,|11 . . . 1i,ãäåbin(i) ýòî äâîè÷íîå ïðåäñòàâëåíèå ÷èñëà i. Òàêàÿ ñèñòåìàâåêòîðîâ íàçûâàåòñÿ ñòàíäàðòíûì âû÷èñëèòåëüíûì áàçèñîì.  äàëüíåéøåì áóäåì ðàññìàòðèâàòü âû÷èñëåíèÿ òîëüêî â ýòîì áàçèñå.3Ïðîñòðàíñòâî ñîñòîÿíèé.Ñîãëàñíî ïåðâîìó ïîñòóëàòó, ñ ëþáîé èçîëèðîâàííîé ôèçè÷å-ñêîé ñèñòåìîé ìîæíî ñâÿçàòü ãèëüáåðòîâî ïðîñòðàíñòâî, íàçûâàåìîå ïðîñòðàíñòâîì ñîñòîÿíèé ñèñòåìû. Ñîñòîÿíèå ñèñòåìû ïîëíîñòüþ îïèñûâàåòñÿ åäèíè÷íûì âåêòîðîì èç ïðîñòðàíñòâà ñîñòîÿíèé, íàçûâàåìûì âåêòîðîì ñîñòîÿíèÿ (èëè, ñîêðàùåííî, ñîñòîÿíèåì).Êâàíòîâûé áèò (êóáèò ) ÿâëÿåòñÿ êëþ÷åâûì ïîíÿòèåì òåîðèè êâàíòîâûõ âû÷èñëåíèé.

Îíðàññìàòðèâàåòñÿ êàê êâàíòîâî-ìåõàíè÷åñêàÿ ñèñòåìà, ñîñòîÿíèå êîòîðîé îïèñûâàåòñÿ êîì2ïëåêñíîçíà÷íûì âåêòîðîì äâóìåðíîãî ãèëüáåðòîâà ïðîñòðàíñòâà H , ò.å.|ψi = α |0i + β |1i ,2îáðàçóþò îðòîíîðìèðîâàííûé áàçèñ â H , à êîìïëåêñíûå ÷èñëà α è22óäîâëåòâîðÿþò óñëîâèþ |α| + |β| = 1. Òàêèì îáðàçîì, â îòëè÷èå îò êëàññè÷åñêîãî áèòàãäå âåêòîðû|0iVCPC'βè|1iêóáèò ìîæåò îäíîâðåìåííî íàõîäèòüñÿ âñóïåðïîçèöèèñâîèõ áàçèñíûõ ñîñòîÿíèé|0iè|1iñEUROPEANCENTREαFORPARALLELCOMPUTING AT VIENNAàìïëèòóäàìèè βñîîòâåòñòâåííî.Êàæäîå ñîñòîÿíèå êóáèòà|ψi = α |0i + β |1i|ψi = cosãäåìîæíî ïðåäñòàâèòü â âèäåθθ|0i + eiφ sin |1i ,220 ≤ φ < 2π , 0 ≤ θ ≤ π .iφ θÏóñòü e= x + iy è îáîçíà÷èì z = cos 2θ .2The Bloch Spherex +y +z = 1Òîãäà222, ò.å.

êàæäîå ñîñòîÿíèåêóáèòà ñîîòâåòñòâóåò òî÷êå íà åäèíè÷íîé ñôåðå, çàäàâàåìîé ïîëÿðíûìè êîîðäèíàòàìèè íàçûâàåìîé&θèφñôåðîé Áëîõà.Îïèñàííîå ïðåäñòàâëåíèå èëëþñòðèðóåò ñîñòîÿíèå êóáèòà â îáùåì ñëó÷àå. Îäíàêî â ñëó22÷àå âåùåñòâåííûõ àìïëèòóä óñëîâèå íîðìèðîâêè α + β= 1 åñòü óðàâíåíèå åäèíè÷íîéîêðóæíîñòè, è, ñëåäîâàòåëüíî, êóáèò ìîæåò áûòü ïðåäñòàâëåí òî÷êîé íà íåé:QIA Meeting, TechGate5Ian Glendinning / February 16, 20054|1〉|ψ〉θ|0〉Òàêèì îáðàçîì, ñîñòîÿíèå êóáèòà â âåùåñòâåííîì ñëó÷àå âûðîæäàåòñÿ â|ψi = cos θ |0i + sin θ |1iäëÿ íåêîòîðîãîθ ∈ [0, 2π).Ñîñòàâíûå ñèñòåìû.Ïðè ðàññìîòðåíèè êâàíòîâîãî ðåãèñòðà (ò.å.