А.В. Васильев - Квантовые вычисления для программистов, страница 3
Описание файла
PDF-файл из архива "А.В. Васильев - Квантовые вычисления для программистов", который расположен в категории "". Всё это находится в предмете "квантовые вычисления" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 3 страницы из PDF
Òàêèì îáðàçîì, ðåçóëüòàò âû÷èñëåíèÿ ÿâëÿåòñÿ âåðîÿòíîñòíûì. Àíàëîãè÷íî âåðîÿòíîñòíîé ìîäåëèîïðåäåëÿþòñÿ êðèòåðèè ðàñïîçíàâàíèÿ ñ îãðàíè÷åííîé è íåîãðàíè÷åííîé îøèáêîé ÿçûêàLêâàíòîâîé ìàøèíîé Òüþðèíãà.Çàìåòèì, ÷òî ïðåäñòàâëåíèå êâàíòîâûõ àëãîðèòìîâ ìàøèíàìè Òüþðèíãà íå ÿâëÿþòñÿ óäîáî÷èòàåìûì, ïîýòîìó â îáëàñòè êâàíòîâûõ âû÷èñëåíèé ïðåîáëàäàåòñõåìíîåïðåäñòàâëåíèåàëãîðèòìîâ (â âèäå êâàíòîâûõ ñõåì èç ôóíêöèîíàëüíûõ ýëåìåíòîâ èëè êâàíòîâûõ âåòâÿùèõñÿ ïðîãðàìì) ââèäó åãî íàãëÿäíîñòè. Áîëåå òîãî, ïîäàâëÿþùåå áîëüøèíñòâî èçâåñòíûõêâàíòîâûõ àëãîðèòìîâ îïèñàíû â ñõåìíîì ïðåäñòàâëåíèè.Êâàíòîâûå êëàññû ñëîæíîñòè• BQP êëàññ ÿçûêîâ ðàñïîçíàâàåìûõ ñ îãðàíè÷åííîé îøèáêîé êâàíòîâîé ìàøèíîéÒüþðèíãà çà ïîëèíîìèàëüíîå âðåìÿ.• PrQP êëàññ ÿçûêîâ ðàñïîçíàâàåìûõ ñ íåîãðàíè÷åííîé îøèáêîé êâàíòîâîé ìàøèíîéÒüþðèíãà çà ïîëèíîìèàëüíîå âðåìÿ.Ïðåæäå âñåãî, ñëåäóåò îòìåòèòü, ÷òî êâàíòîâûå âû÷èñëèòåëè íå ìîãóò ðåøàòü ïðîáëåìû,íå ðàçðåøèìûå íà êëàññè÷åñêîé ìàøèíå Òüþðèíãà.
Ýòî ñëåäóåò èç òîãî, ÷òî âñå âû÷èñëèìîåâ êâàíòîâîé ìîäåëè ìîæåò áûòü ñìîäåëèðîâàíî íà êëàññè÷åñêîé ìàøèíå ïðîñòî âû÷èñëåíèåì àìïëèòóä ñóïåðïîçèöèè è çàïèñè èõ íà ðàáî÷óþ ëåíòó. Ðàçëè÷èå ìåæäó êëàññè÷åñêèìèè êâàíòîâûìè âû÷èñëåíèÿìè ëåæèò òîëüêî â âîïðîñå èõ ñëîæíîñòè. Òðèâèàëüíîå ìîäåëèðîâàíèå êâàíòîâûõ âû÷èñëåíèé êëàññè÷åñêèì ýêñïîíåíöèàëüíî ïî âðåìåíè è ïàìÿòè. Bernsteinè Vazirani [3] ïîêàçàëè, ÷òî ìîäåëèðîâàíèå ìîæåò áûòü ïîëèíîìèàëüíî ïî ïàìÿòè, õîòÿ âñååùå ýêñïîíåíöèàëüíî ïî âðåìåíè.Èçâåñòíû ñëåäóþùèå ñîîòíîøåíèÿ:• BQP ⊆ PSPACE•3.2[3]Ñîîòíîøåíèå ìåæäó êëàññàìèBQPèNPíåèçâåñòíî.Êâàíòîâûå ñõåìûÎäíîðîäíûå âû÷èñëèòåëüíûå ìîäåëè, òàêèå êàê ìàøèíà Òüþðèíãà, êîíå÷íûå àâòîìàòû, îðèåíòèðîâàíû íà ðåøåíèå âû÷èñëèòåëüíîé ïðîáëåìû ñ ïðîèçâîëüíîé äëèíîé âõîäà.
Äàëåå áóäóòðàññìîòðåíû íåîäíîðîäíûå ìîäåëè âû÷èñëåíèé, îáðàáàòûâàþùèå âõîäíûå ñëîâà ôèêñèðîâàííîé äëèíû.Íàèáîëåå ðàñïðîñòðàíåííîé êâàíòîâîé ìîäåëüþ âû÷èñëåíèé ÿâëÿþòñÿ êâàíòîâûå ñõåìû(quantumcircuits ).  îñíîâå îïðåäåëåíèÿ êâàíòîâûõ ñõåì ëåæèò ïîíÿòèå êâàíòîâîãî âåíòèëÿ(quantum gate ).Îïðåäåëåíèå 3.2. Êâàíòîâûì âåíòèëåìíà q êóáèòàõ íàçûâàåòñÿ óíèòàðíîå îòîáðàæåqíèå â ãèëüáåðòîâîì ïðîñòðàíñòâå H2 = H2 ⊗ . . . ⊗ H2 , âîçäåéñòâóþùåå íåòðèâèàëüíûìîáðàçîì íà ôèêñèðîâàííîå (íå çàâèñÿùåå îò q ) ÷èñëî êóáèò.10Îïðåäåëåíèå 3.3.Êâàíòîâàÿ ñõåìà íà q êóáèòàõ ýòî óíèòàðíîå îòîáðàæåíèå â ãèëüqáåðòîâîì ïðîñòðàíñòâå H2 = H2 ⊗ .
. . ⊗ H2 , êîòîðîå ìîæåò áûòü ïðåäñòàâëåíî â âèäåñîåäèíåíèÿ êîíå÷íîãî ÷èñëà êâàíòîâûõ âåíòèëåé.Êâàíòîâûå ñõåìû ïðèíÿòî èçîáðàæàòü ñëåäóþùèì îáðàçîì:|φ2 iU1...···U2UlNM···|φq iÑëîæíîñòüþNMNM···|φ1 iêâàíòîâûõ ñõåì íàçûâàþò ÷èñëî êâàíòîâûõ âåíòèëåé â íåé. Èçâåñòíî [12],÷òî ïîëèíîìèàëüíûå ïî ñëîæíîñòè êâàíòîâûå ñõåìû ðàâíîìîùíû ïîëèíîìèàëüíûì ïî âðåìåíè êâàíòîâûì ìàøèíàì Òüþðèíãà.3.3Ïðèìåðû êâàíòîâûõ àëãîðèòìîâÊâàíòîâûå àëãîðèòìû íà îñíîâå ngerprinting.àóÏóñòüg(σ) çíà÷åíèå õàðàêòåðèñòè÷åñêîé ôóíêöèè, ïðîâåðÿþùåéσ .
σ îáëàäàåò ñâîéñòâîì g ⇐⇒ g(σ) = 0 mod m.Ïîâåðíåì íà÷àëüíîå ñîñòîÿíèå |0i íà óãîëσ = σ1 . . . σn âõîäíîé íàáîð,íàëè÷èå íåêîòîðîãî ñâîéñòâàπg(σ)mθ=|0i → cos θ |0i + sin θ |1i → |0i ⇐⇒ g(σ) = 0 mod m|1〉|ψ〉θ|0〉Ïóñòük1 , . . . , kt ∈ {1, . . . , m − 1}.Ïîâåðíåìθi =têóáèò íà óãëûπki g(σ)m|0i → cos θi |0i + sin θi |1i → |0i ,Ïðèt = O(log m)ñóùåñòâóåò ìíîæåñòâîåñëèg(σ) = 0 mod mK = {k1 , . .
. , kt },11äëÿ êîòîðîãîP rerror < 1/m.|1〉|1〉|0〉|0〉|1〉|1〉|0〉|0〉Èñïîëüçóÿ êâàíòîâûé ïàðàëëåëèçì è èíòåðôåðåíöèþ, ìîæíî äîáèòüñÿ çíà÷èòåëüíîãî ñîêðàùåíèÿ ÷èñëà êóáèò.|0i ⊗ |0i ⊗ · · · ⊗ |0i ⊗ |0i|{z}log t↓t1 X √|ii cos θi |0i + sin θi |1it i=1θi =2πki g(σ)m|1〉|0〉Îïèñàííàÿ ñõåìà ïðîâåðêè ñâîéñòâàgó âõîäíîãî íàáîðàðèòìîì:12σðåàëèçóåòñÿ ñëåäóþùèì àëãî-|0i⊗ log t |0i↓tP1√|ji |0itj=11√t1t↓tP2πkj g(σ)2πkj g(σ)|0i + sin m|1i|ji cos mj=1↓tP2πkl g(σ)cos m|0i⊗ log t |0i + . .
.l=1↓g = 0 ⇐⇒ðåçóëüòàò èçìåðåíèé |0i⊗ log t |0iÂîçìîæíî òàêæå îáîáùåíèå äàííîãî ïîäõîäà äëÿ ïðîâåðêè îäíîâðåìåííîãî âûïîëíåíèÿðÿäà ñâîéñòâ, çàêîäèðîâàííûõ ôóíêöèÿìèg1 , g2 ,...,gl .Äëÿ ýòîãî ïî âõîäíîìó íàáîðóσñîçäàåòñÿ êâàíòîâàÿ ñóïåðïîçèöèÿ âèäàtX i hσ (j) = cos πki gj (σ) |0i + sin πki gj (σ) |1i |hσ i = √1|ii hiσ (1) hiσ (2) . . . hiσ (l) .mmt i=1Íåôîðìàëüíî, ýòî ìîæíî ïðîèëëþñòðèðîâàòü ñëåäóþùèì îáðàçîì:Äðóãèìè ñëîâàìè, çäåñü ðåàëèçóåòñÿ êîìáèíàöèÿ êëàññè÷åñêîãî è êâàíòîâîãî ïàðàëëåëèçìà:lêóáèò èñïîëüçóþòñÿ ïàðàëëåëüíî (â êëàññè÷åñêîì ñìûñëå), è êàæäûé èç íèõ ïàðàë-ëåëüíî (â êâàíòîâîì ñìûñëå) âðàùàåòñÿ íà4tðàçëè÷íûõ óãëîâ.Êâàíòîâûå âû÷èñëåíèÿ äëÿ ïðîãðàììèñòîâÐàçðàáîòêà êâàíòîâûõ êîìïüþòåðîâ ñòàâèò ìíîæåñòâî çàäà÷ êàê äëÿ ìàòåìàòèêîâ, òàê è äëÿèíæåíåðîâ.
Ïðè÷åì îáå êàòåãîðèè èññëåäîâàòåëåé äâèæóòñÿ íàâñòðå÷ó äðóã äðóãó: îäíè ðàçðàáàòûâàþò áûñòðûå è ýôôåêòèâíûå ïî ïàìÿòè êâàíòîâûå àëãîðèòìû, à âòîðûå ïðîäâèãàþòñÿ â ñîçäàíèè ïîëíîìàñøòàáíûõ êâàíòîâûõ âû÷èñëèòåëåé, ñïîñîáíûõ óñòîé÷èâî ðàáîòàòüäîñòàòî÷íî ïðîäîëæèòåëüíîå âðåìÿ.13Îäíàêî íà äàííûé ìîìåíò âû÷èñëèòåëè ñèëüíî îãðàíè÷åíû êàê ïî âðåìåíè æèçíè ñèñòåìû, òàê è ïî ÷èñëó îäíîâðåìåííî äîñòóïíûõ êóáèò.
Ïîýòîìó ðåàëèñòè÷íûì ïðåäñòàâëÿåòñÿâàðèàíò ãèáðèäíîãî êâàíòîâîãî êîìïüþòåðà, ñîñòîÿùåãî èç íåáîëüøîãî (ïî ïàìÿòè) êâàíòîâîãî óñòðîéñòâà, ðàáîòàþùåãî ïîä óïðàâëåíèåì êëàññè÷åñêîãî êîìïüþòåðà, êîòîðûé çàäàåòïîñëåäîâàòåëüíîñòü ïðèìåíåíèÿ óíèòàðíûõ îïåðàöèé, ïîëó÷àåò ðåçóëüòàòû èçìåðåíèÿ, à òàêæå ìîæåò ïðîèçâîäèòü âñïîìîãàòåëüíûå ðàñ÷åòû.4.1Çàäà÷è äëÿ ïðîãðàììèñòîâÕîòÿ ñîçäàíèå êâàíòîâûõ êîìïüþòåðîâ âñå åùå íàõîäèòñÿ â ýêñïåðèìåíòàëüíîé ñòàäèè, óæåñåé÷àñ ìîæíî ñôîðìóëèðîâàòü çàäà÷è â êëàññè÷åñêîì ïðîãðàììèðîâàíèè, ðåøåíèå êîòîðûõáóäåò ñïîñîáñòâîâàòü ðàçâèòèþ îáëàñòè êâàíòîâûõ âû÷èñëåíèé.•Ýìóëÿöèÿ êâàíòîâûõ âû÷èñëåíèé, â òîì ÷èñëå ýôôåêòèâíîå ìîäåëèðîâàíèå êâàíòîâîéçàïóòàííîñòè.
Ïîñëåäíåå ïîçâîëèò ðåøàòü çàäà÷è è ïðîâåðÿòü ãèïîòåçû â òåîðèè êâàíòîâîé èíôîðìàöèè.Îäíèì èç âàðèàíòîâ ýìóëÿöèè êâàíòîâîãî ñîïðîöåññîðà ìîãëà áûòü ñòàòü ðàçðàáîòêàâèðòóàëüíîãî äðàéâåðà äëÿ ïîïóëÿðíûõ îïåðàöèîííûõ ñèñòåì, êîòîðûé ïîçâîëèò òåñòèðîâàòü ðàçíîîáðàçíûå êâàíòîâûå àëãîðèòìû, à òàêæå äðóãèå ïðîãðàììíûå ðàçðàáîòêè,ñâÿçàííûå ñ ôóíêöèîíèðîâàíèåì êâàíòîâûõ âû÷èñëèòåëåé.•Ðàçðàáîòêà ñèñòåìû ïðîãðàììèðîâàíèÿ êâàíòîâîãî ñîïðîöåññîðà.Äàííàÿ çàäà÷à òåñíî ñâÿçàíà ñ ïðåäûäóùåé è ìîæåò îñíîâûâàòüñÿ íà ïðåäïîëîæåíèè,÷òî êâàíòîâûé ñîïðîöåññîð ïðåäîñòàâëÿåò íåêîòîðûé èíòåðôåéñ (÷åðåç äðàéâåð, óñòàíîâëåííûé â îïåðàöèîííîé ñèñòåìå), äëÿ âçàèìîäåéñòâèÿ ñ êîòîðûì ñîçäàåòñÿ áèáëèîòåêà êëàññîâ, ñêàæåì íà C#.Òàêîé íàáîð êëàññîâ îñíîâûâàåòñÿ íà âîçìîæíîñòè ñîçäàíèÿ (èíèöèàëèçàöèè) ðåãèñòðàêâàíòîâûõ áèòîâ â íóëåâîì ñîñòîÿíèè, ïðèìåíåíèÿ áàçèñíûõ îïåðàöèé ê ïðîèçâîëüíûì êóáèòàì ðåãèñòðà, à òàêæå èçìåðåíèå êâàíòîâîãî ðåãèñòðà (ïîëó÷åíèå ðåçóëüòàòàâû÷èñëåíèé).Äëÿ óäîáñòâà â áèáëèîòåêå äîëæíû áûòü òàêæå ðåàëèçîâàíû îáùåóïîòðåáèòåëüíûåêâàíòîâûå îïåðàòîðû, ïîñêîëüêó èõ âñåãäà ìîæíî âûðàçèòü ÷åðåç áàçèñ.
Íà îñíîâåäàííîé áèáëèîòåêè ìîæíî áóäåò ðåàëèçîâûâàòü èçâåñòíûå ýôôåêòèâíûå êâàíòîâûå àëãîðèòìû â âèäå îáû÷íîé ôóíêöèè íà ÿçûêå âðîäå C#.•Ðàçðàáîòêà âèçóàëüíîé ñðåäû äëÿ êîíñòðóèðîâàíèÿ è àíàëèçà êâàíòîâûõ àëãîðèòìîâ.Äàííàÿ çàäà÷à ïîäðàçóìåâàåò ñîçäàíèå èíñòðóìåíòàëüíûõ ñðåäñòâ, ïîçâîëÿþùèõ íàãëÿäíî ïðåäñòàâëÿòü êâàíòîâûå àëãîðèòìû â ìîäåëè êâàíòîâûõ ñõåì èç ôóíêöèîíàëüíûõ ýëåìåíòîâ.
Ðàçðàáàòûâàåìàÿ ñðåäà äîëæíà ïðåäîñòàâëÿòü ñðåäñòâà äëÿ ðàçëîæåíèÿ îòäåëüíûõ êâàíòîâûõ ïðåîáðàçîâàíèé ïî âû÷èñëèòåëüíîìó áàçèñó, à òàêæå îáúåäèíåíèÿ îòäåëüíûõ ÷àñòåé àëãîðèòìà â ñîñòàâíûå îïåðàòîðû. Êðîìå òîãî, ïðåäïîëàãàåòñÿðåàëèçàöèè îïòèìèçàöèîííûõ ïðîöåäóð äëÿ ñîêðàùåíèÿ ÷èñëà ýëåìåíòàðíûõ îïåðàòîðîâ, à òàêæå äëÿ ñîêðàùåíèÿ ÷èñëà øàãîâ çà ñ÷åò ïàðàëëåëüíîãî âûïîëíåíèÿ íåêîòîðûõîïåðàòîðîâ.14Îñíîâíûå îáîçíà÷åíèÿdae íàèìåíüøåå öåëîå ÷èñëî, íå ìåíüøååbac íàèáîëüøåå öåëîå ÷èñëî, íå ïðåâîñõîäÿùååa.a.log a = log2 a.|K|Bn ìîùíîñòü êîíå÷íîãî ìíîæåñòâà ìíîæåñòâî áóëåâûõ ôóíêöèé îòK.nïåðåìåííûõ.Íîðìû âåêòîðà a = (a1 , .
. . , ad ):P||a||1 = q di=1 ai ,Pd2||a||2 =i=1 |ai | .Hdd-ìåðíîå||.||2 .êîìïëåêñíî-çíà÷íîå âåêòîðíîå (Ãèëüáåðòîâî) ïðîñòðàíñòâî ñ íîðìîéU∗ ìàòðèöà, êîìïëåêñíî-ñîïðÿæåííàÿ êUT òðàíñïîíèðîâàííàÿ ìàòðèöàU † = (U T )∗|aihb| = (|biT )∗ha | biU. ýðìèòîâî ñîïðÿæåíèå ê âåêòîð-ñòîëáåö (êåò-âåêòîð)U.a.
âåêòîð-ñòðîêà (áðà-âåêòîð) ñêàëÿðíîå ïðîèçâåäåíèåU.|aièb∗ .|bi.òåíçîðíîå (ïðàâîå êðîíåêåðîâî) ïðîèçâåäåíèå|ai = (a1 , . . . , ad )T è |bi = (b1 , . . . , bl )T|ai ⊗ |bi = (a1 b1 , a1 b2 , . . . , a1 bl , a2 b1 , . . . , ad bl )T .|ai ⊗ |biâåêòîðîâa, b.Äëÿ|ai |bi = |abi = |ai ⊗ |bi|ai hb| = |ai ⊗ hb|òåíçîðíîå(ïðàâîå êðîíåêåðîâî)ïðîèçâåäåíèå ìàòðèöA, Ba11 · · · a1nb11 · · · b1k .....
...Äëÿ A = è B = .. . . . .. ...a· · · amnbl1 · · · blk m1a11 B · · · a1n B ......A⊗B = ...am1 B · · · amn BA⊗BA⊗d = A{z· · · ⊗ A}.| ⊗A⊗d(A ⊗ B)(|φi ⊗ |ψi) = A |φi ⊗ B |ψi.15||.|| =|φ1 i ⊗ |ψ1 i , |φ2 i ⊗ |ψ2 i= hφ1 | φ2 ihψ1 | ψ2 i.1 02I= òîæäåñòâåííîå ïðåîáðàçîâàíèå â H .0 1111H = √2 ïðåîáðàçîâàíèå Àäàìàðà (Óîëøà-Àäàìàðà).1 −1cos 2θ − sin 2θRŷ (θ) = âðàùåíèå íà óãîë θ âîêðóã îñè ŷ ñôåðûsin 2θ cos 2θ1 000 0 100 êîíòðîëèðóåìîå âðàùåíèå.C(Rŷ (θ)) = θθ 0 0 cos−sin22θθ0 0 sin 2 cos 2f (n) = O(g(n)) ñóùåñòâóþòäëÿ âñåõ n ≥ n0 .ïîëîæèòåëüíûå êîíñòàíòûcèn0 ,Áëîõà.òàêèå, ÷òî0 ≤ f (n) ≤ cg(n)f (n) = Ω(g(n)) ñóùåñòâóþò ïîëîæèòåëüíûå êîíñòàíòû c è n0 , òàêèå, ÷òî 0 ≤ cg(n) ≤ f (n))äëÿ âñåõ n ≥ n0 .f (n) = Θ(g(n)),åñëèf (n) = O(g(n))èf (n) = Ω(g(n)).Ñïèñîê ëèòåðàòóðû[1] Bennett, C.H.
Logical reversibility of computations / C.H. Bennett // IBM Jounal of Res.Develop. 1973. V. 17. P. 525-532.[2] Benio, P.A. Quantum mechanical hamiltonian models of turing machines / P.A. Benio //Journal of Statistical Physics. 1982. V. 29, N 3. P. 515-546.[3] Bernstein, E. Quantum complexity theory / E. Bernstein, U. Vazirani // SIAM J.
Comput. 1997. V. 26, N 5. P. 1411-1473.[4] Deutsch D. Quantum theory, the Church-Turing principle and the universal quantumcomputer // Proceedings of the Royal Society of London. Series A, Mathematical andPhysical Sciences. 1985. PP. 97117.[5] Deutsch D. Quantum computational networks // Proceedings of the Royal Society of London.Series A, Mathematical and Physical Sciences. 1989.