Fazani baholash va Shor algoritmining asoslari

"Deutsch-Jozsa algoritmi" va "Grover algoritmi" ni yoritib bo'lgach, bugun biz Kvant Furye o'zgarishiga e'tibor qaratamiz. Bu erda biz ishlab chiqadigan asosiy kontseptsiya - bu diskret Furye transformatsiyasining (DFT) analogini ishlab chiqish uchun kvant kompyuteridan foydalanish. DFT raqamli signalni qayta ishlashda muhim ahamiyatga ega va vaqt o'tishi bilan tarqaladigan kirish signalini ma'lum amplitudali chastotalar soniga va fazalarga bo'lish imkonini beradi, shunda barcha chastotalar asl signalni hosil qilishi mumkin.Keling. DFT ning kvant analogini qanday qurishimiz mumkinligini ko'ring va bu "Shor algoritmi" va kvant fazasini baholashning asosini tashkil qiladi. Bu post matematika uchun biroz og'ir bo'ladi, lekin oldingi postlarni tekshirib ko'nikishingiz mumkin.

Klassikdan kvantga: DFT

Klassik DFT bilan boshlaylik. Transformatsiya qoidasini quyidagicha yozishimiz mumkin:

Formula biroz qo'rqinchli ko'rinishi mumkin, ammo bu juda oddiy. Keling, buni amalda qo'yaylik. xⱼ= 2, 1 ni hisoblang, yni hisoblang

Qubitlar uchun holat vektorlari murakkab sonlar vektorlari bo'lganligi sababli, DFT ularga ham tegishli degan fikrni olishimiz mumkin. Keling, |ps⟩ = ∑ aⱼ |j⟩ ni ko'rib chiqaylik. Bu holatning DFT ni quyidagicha hisoblash mumkin:

QFTniDFT kvant holatining amplitudalariga qo'llanilishi deb o'ylashning eng yaxshi usuli. Bundan tashqari, biz Fning chiziqli ekanligini ko'rishimiz mumkin. Yuqoridagi transformatsiyani ikkita holat vektorlari orasidagi xarita sifatida ham tasavvur qilishimiz mumkin:

Bunday o'zgartirishlarni jismoniy jihatdan amalga oshirish imkoniyati F operatori unitar yoki yo'qligiga bog'liq va F haqiqatan ham unitar ekanligini osongina ko'rsatish mumkin (boshqacha sinab ko'ring). daftarimni tekshiring, xabar oxiridagi havola).

Keling, bitta kubit holatini |ps⟩=a|0⟩+b|1⟩ sifatida ko'rib chiqaylik. Ushbu holatga QFTni qo'llashdan keyin qanday natija bo'ladi? Biz allaqachon QFT ning holatga qo'llanilishi faqat davlatningamplitudasiga ta'sir qilishini ko'rdik. (2) tenglama yordamida amplitudaning o'zgarishini hisoblaymiz. Bu yerda N=2¹, shunday qilib -

Shunday qilib, F|ps⟩=b₀|0⟩+b₁|1⟩= (1/√) 2)(a+b)|0⟩+(1/√2)(a−b) |1⟩. Shunday qilib, biz amplitudalar a→(1/√2)(a+b) va b→(1/√2)(a−b). Biz bu transformatsiyani allaqachon bilamiz, bu bitta kubit holatiga qo'llaniladigan Hadamard (H) transformatsiyasi. Bu erda ikkita muhim jihatga e'tibor qaratish kerak, birinchidan, biz ko'rib turibmizki, bizning boshlang'ich asosimiz Z asosi X asosiga o'zgargan va ikkinchidan, H darvozasi qurilish uchun muhim komponent bo'ladi. QFT sxemasi. Ammo H gate QFT sxemasini qurishimiz kerak bo'lgan yagona komponentmi? Keling, yuqoridagi kabi shunga o'xshash misolni ko'rib chiqaylik, lekin biz 2 kubitdan foydalanamiz.

|ps⟩=a_{00}|00⟩+a_{01}|01⟩+a_{ 10}|10⟩+a_{11}|11⟩, bu yerda N=2² . Keling, faqat o'zgartirilgan amplitudalarni hisoblaylik

Agar ō=exp(ip/2) deb hisoblasak, ō⁴=1 va hokazo... Ushbu 2 kubitli holat uchun transformatsiya matritsasini quyidagicha yozishimiz mumkin -

Agar biz 1 kubit holatiga qo'llaniladigan transformatsiyani ushbu 2 kubit holatiga taqqoslasak, 1 kubitlik transformatsiyalar uchun amplitudalar haqiqiy bo'lsa-da (biz buni Hadamard transformatsiyasidan ham bilamiz), bu erda bizda haqiqiy va murakkab amplitudalar borligini ko'ramiz. Bundan tashqari, Hadamard darvozasi o'zining teskarisi, bu transformatsiya matritsasi emas. Ushbu nuqtada bₖni diqqat bilan tekshirib ko'ramiz, biz superpozitsiyadan tashqari ba'zi fazali eshiklarni ham kiritishimiz kerakligini ko'ramiz. Quyidagi shaklning fazali eshigi vazifani bajaradi -

Shuningdek, biz aylanish boshqa bitlarga ham bog'liqligini ko'ramiz, shuning uchun oddiy fazali eshik o'rniga biz quyidagi tarzda boshqariladigan faza (CP) eshigini kiritishimiz mumkin -

CP ning ikki kubitli holatdagi harakati |x₀x₁⟩ bunda birinchi kubit boshqaruv, ikkinchisi esa maqsad hisoblanadi tomonidan beriladi -

Shu nuqtada, aylanish nuqtai nazaridan H eshigini yozish juda muhimdir -

Kvant Furye o'zgarishining umumiy qoidasi:

n kubitli kvant holatini hisobga olsak, umumlashtirilgan Kvant Furye o'zgarishi qoidasi quyidagicha:

bu erda ko'rsatkichlar ichidagi atamalar quyidagi tarzda kengaytirilishi mumkin -

Ushbu umumlashtirilgan ibora bilan, ehtimol, nima uchun bizga superpozitsiya eshigi (H) va boshqariladigan faza eshigi kerakligi aniqroq bo'ladi.

Keling, Hadamard va boshqariladigan fazali eshiklar yordamida qanday qilib bunday transformatsiyani yaratishimiz mumkinligini ko'rib chiqamiz va buning uchun biz 3 ta eshikni ko'rib chiqamiz.

  1. H darvozasini 1-qubitga qo'llang

2. Faza eshigini |x₀⟩ ga |x₁⟩ ga, ya'ni boshqariladigan faza eshigiga qarab qo'llang.

3. Nazorat biti sifatida |x₀⟩ ga |x₂⟩ bilan ikkinchi boshqariladigan fazali eshikni qo'llang.

4. Endi biz jarayonni ikkinchi kubit uchun takrorlaymiz, shuning uchun ikkinchi kubitga H eshigini qo'llang

5. Endi biz boshqariladigan faza eshigini 3-kubitga qarab 2-kubitda qo'llaymiz

6. Nihoyat, biz H eshigini oxirgi kubitga qo'llaymiz

Biz 8-tenglama bilan osongina solishtirishimiz mumkin va natijamiz n=3 kubit uchun o'xshashligini ko'rishimiz mumkin, faqat kubitlar tartibi bundan mustasno; Shunday qilib, biz |x₂⟩ va |x₀⟩ kubitlarini almashtirishimiz kerak, xayriyatki, biz uchun ishni bajarish uchun almashtirish eshiklari mavjud! Keling, Qiskit yordamida sxemani quramiz.

Kvant-Furye o'zgartirish sxemasini qurish:

Biz 3 kubit uchun Quantum Furier Transform sxemasini qurish bosqichlarini muhokama qildik va bu erda biz bosqichma-bosqich sxemani qurish uchun Qiskit kutubxonasidan foydalanamiz.

Quyida biz 3 kubit uchun QFT sxemasini qurish uchun foydalanadigan kod bloki mavjud.

Biz sxemani biroz "uslub" qo'shish orqali chizishimiz mumkin va u quyidagicha ko'rinadi -

Ushbu sxemadan foydalanib, |110⟩ holatini kodlashga harakat qilaylik. Shunday qilib, biz yuqoridagi sxemani quyidagi tarzda biroz o'zgartirish bilan ishlatamiz -

QFT natijasini tushunishning eng yaxshi usuli bu holat vektorlarini quyidagi tarzda tuzishdir:

circ1.save_statevector()

qasm_sim = q.Aer.get_backend('qasm_simulator')


statevector = qasm_sim.run(circ1).result().get_statevector()
q.visualization.plot_bloch_multivector(statevector)

Dastlab, 0 kubit |0⟩ holatida, 1 va 2 kubitlar esa |1⟩ holatida edi. Biz |110⟩ 6 (2² +2¹+0) holatini kodlashga harakat qilyapmiz. Shunday qilib, birinchi kubit aynan 6/2³ ×2p=270∘ aylanadi. Ikkinchi kubit 6/2²×2p=540∘=2p+p aylanadi va uchinchi kubit 6/2¹×2p=3×2p. Shuni ham ta'kidlash kerakki, bu burchaklar |˜0⟩ boshlang'ich bosqichidan boshlab hisoblangan, bu erda barcha kubitlar |+⟩ holatda bo'ladi va biz |˜6⟩ holatiga yetdik. ~ (tilda) - Furye fazosidagi holatlarga murojaat qilishning keng tarqalgan usuli.

Kvant Furye o'zgarishi keyinchalik Shor algoritmiga chuqur kirib borganimizda juda foydali bo'ladi, bu ham kvant hisoblashning kuchi va ahamiyatini ko'rsatadigan algoritmdir. Biz bu haqda keyingi postda qaytamiz!

Kuchli va quvnoq bo'ling !!

Adabiyotlar:

[1] “Kvant hisoblash va kvant maʼlumotlari”, Nielsen, M. va Chuang, I. 217–220-betlar.

[2] Qiskit darsligi: Kvant-Furye transformatsiyasi

[3] Mening daftarim: GitHub Link