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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Êâàíòîâûå âû÷èñëåíèÿ äëÿ ïðîãðàììèñòîâÂàñèëüåâ À.Â.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π).Ñîñòàâíûå ñèñòåìû.Ïðè ðàññìîòðåíèè êâàíòîâîãî ðåãèñòðà (ò.å.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов книги