Shor algoritmi — kvant algoritmi bo‘lib, u faktorizatsiya (sonni tub ko‘paytuvchilarga ajratish) masalasini yechadi; bunda sonini quyidagi vaqt ichida ko‘paytuvchilarga ajratadi: , bunda ta mantiqiy kubit ishlatiladi.
Shor algoritmi Piter Shor tomonidan 1994-yilda ishlab chiqilgan. Oradan yetti yil o‘tib, 2001-yildauning ishlashi mutaxassislar guruhi tomonidan namoyish etildi — IBM. 15 soni 3 va 5 ko‘paytuvchilariga kvant kompyuteri yordamida, 7 ta kubit ishtirokida ajratildi.
Algoritm haqida
Algoritmning ahamiyati shundaki, bir necha ming mantiqiy kubitli kvant kompyuteridan foydalanib, quyidagi tizimlarni buzish mumkin: ochiq kalitli kriptografik tizimlar. Masalan, RSA tizimi quyidagi ochiq kalitdan foydalanadi: , u ikkita katta tub sonning ko‘paytmasidir. RSA shifrini buzish usullaridan biri — quyidagi sonning ko‘paytuvchilarini topish: . Agar son yetarlicha katta bo‘lsa, uni ma’lum klassik algoritmlaryordamida faktorizatsiya qilish amalda deyarli imkonsiz. Ma’lum bo‘lgan eng yaxshi, isbotlangan deterministik klassik faktorizatsiya algoritmlari, masalan, Shenksning kvadratik shakllar usuli va Pollard–Shtrassen algoritmi, taxminan quyidagi tartibdagi vaqtni talab qiladi: . Shuningdek, Shenksning kvadratik shakllar usuli ham taxminan quyidagi vaqt ichida ishlashi mumkin: , bunda quyidagi faraz rost deb olinadi: Riman gipotezasi. Ehtimollik algoritmlari orasida faktorizatsiya bo‘yicha yetakchi usul — sonlar maydoni maxsus elagi usulibo‘lib, u 1/2 ehtimollik bilan tub bo‘luvchini subeksponensial vaqt ichida topa oladi: . Shor algoritmi kvant kompyuterlarining imkoniyatlaridan foydalanib, sonni nafaqat polinomial vaqt ichida, balki butun sonlarni ko‘paytirishga ketadigan vaqtdan uncha ko‘p bo‘lmagan vaqt ichida ham ko‘paytuvchilarga ajrata oladi (ya’ni deyarli shifrlash jarayonining o‘zi kabi tez ishlaydi). Shu sababli kengaytirish mumkin bo‘lgan kvant kompyuterining yaratilishi zamonaviy kriptografik himoyaning katta qismini samarasiz qilib qo‘yadi. Bu faqat faktorizatsiya murakkabligiga bevosita tayanuvchi RSA tizimiga emas, balki kvant kompyuteri xuddi shunday usulda buza oladigan boshqa o‘xshash tizimlarga ham tegishli.
Shor algoritmi ehtimollik xususiyatiga ega. Tasodifiylikning birinchi manbai ko‘paytuvchilarga ajratish masalasini muayyan funksiyaning davrini topish masalasiga keltirishning klassik ehtimollik usulida mavjud. Ikkinchi manba esa kvant xotirasini o‘lchash zaruratidan kelib chiqadi, chunki bu o‘lchash ham tasodifiy natijalar beradi.
Algoritmni takomillashtirish
2023-yilda Oded Regev yangi kvant algoritmini sonlarni faktorizatsiya qilish uchun e’lon qildi. U Shor algoritmidan samaraliroq. Regev yangi algoritmini Shor algoritmiga quyidagi sohaning usullarini qo‘shish orqali yaratdi: ko‘p o‘lchamli geometriyani o‘rganuvchi kriptografiya sohasi. U algoritmni faqat ikkita emas, balki istalgan sondagi o‘lchamlarga umumlashtirishga muvaffaq bo‘ldi. Natijada sonlarni faktorizatsiya qilish uchun kvant kompyuteriga ancha kam mantiqiy bosqich talab etiladi. Kvant hisoblashlari sohasi mutaxassislarining ta’kidlashicha, oradan 30 yil o‘tib kimdir Shor algoritmini sifat jihatidan yaxshilagani hayratlanarli va kutilmagan hodisadir.
Shor algoritmining ishlash prinsipi
Shor algoritmining asosi — kvant kompyuteridagi axborot birliklari, ya’ni kubitlarning bir vaqtning o‘zida bir nechta qiymatni qabul qila olishi va «kvant chirmashuvi» holatida bo‘la olishidir. Shu tufayli algoritm kubitlarni tejab hisoblash imkonini beradi. Shor algoritmining ishlash prinsipini 2 qismga ajratish mumkin: birinchisi — ko‘paytuvchilarga ajratish masalasini funksiyaning davrini topish masalasiga klassik usulda keltirish, ikkinchisi — shu funksiya davrini kvant usulida topish. Faraz qilaylik:
- — biz ko‘paytuvchilarga ajratmoqchi bo‘lgan son (u toq sonning butun darajasi bo‘lmasligi kerak);
- — foydalaniladigan xotira registrining hajmi (yordamchi xotiradan tashqari). Ushbu xotiraning bitlardagi hajmi son hajmidan taxminan 2 baravar katta: . Aniqrog‘i, ;
- — shunday tasodifiy parametrki, va (bu yerda — eng katta umumiy bo‘luvchi).
E’tibor bering, , , — o‘zgarmas qiymatlardir. Shor algoritmida ko‘paytuvchilarga ajratish masalasini quyidagi funksiya davrini topish masalasiga keltirishning standart usuli qo‘llanadi: ; bu funksiya tasodifan tanlangan songa bog‘liq: .
Algoritmning klassik qismi
Eng kichik shundayki, , — bu quyidagi sonning tartibi: modul bo‘yicha; modul .
Quyidagi tartib: funksiyaning davri hisoblanadi: , bu yerda .
Agar ni quyidagining funksiyasi sifatida: samarali hisoblash mumkin bo‘lsa, u holda ning o‘zidan boshqa bo‘luvchisini quyidagi songa nisbatan polinomial vaqt ichida topish mumkin: , quyidagi ehtimollik bilan: ehtimollik bilan, istalgan belgilangan parametr uchun: .
Faraz qilaylik, berilgan uchun davr juft bo‘lib, quyidagi shartni qanoatlantiradi:
- .
U holda
- — quyidagining o‘zidan boshqa bo‘luvchisi: . Funksiya polinomial vaqt ichida hisoblanadi.
Ushbu shartning bajarilish ehtimoli , bu yerda — quyidagi sonning turli toq tub bo‘luvchilari soni: ; demak, ushbu holatda. Shuning uchun yaxshi qiymati ehtimollik bilan ta urinishda topiladi. Bitta urinishdagi eng ko‘p vaqt oladigan hisoblash — .
Algoritmning kvant qismi
Algoritmning kvant qismini bajarish uchun hisoblash sxemasi ta kvant registridan iborat: va . Dastlab ularning har biri nol mantiqiy holatdagi kubitlar to‘plamidan tashkil topadi: .
Registr funksiyaga beriladigan argumentlarni saqlash uchun ishlatiladi: esa shu argumentga qo‘llanadigan funksiya: . Yordamchi registr (ikkinchi registr) quyidagi funksiya qiymatlarini saqlaydi: ; uning davri , uni hisoblash kerak.
Kvant hisoblash 4 bosqichdan iborat:
- Birinchi bosqich. Birinchi bosqichda Uolsh–Adamar amali, ya’ni kubitni o‘zgartiruvchi operatori yordamida boshlang‘ich holat quyidagi registrda: barcha mantiqiy holatlarning teng ehtimolli superpozitsiyasiga o‘tkaziladi; holatlar soni: . Ikkinchi registr quyidagi holatda qoladi: . Natijada ikki registrli tizimning quyidagi holati hosil bo‘ladi:
- Ikkinchi bosqich. Faraz qilaylik, — unitar o‘zgartirish, u quyidagi holatni o‘tkazadi: quyidagi holatga: . Ikkinchi bosqichda ikkala registrga unitar o‘zgartirish qo‘llanadi. Tizimning quyidagi holati hosil bo‘ladi:
- , ya’ni ikkala registrning holatlari o‘rtasida muayyan bog‘liqlik yuzaga keladi.
- Uchinchi bosqich. Kvant Furye almashtirishi — kvant registri holatining unitar almashtirilishi bo‘lib, u -o‘lchamli quyidagi holat vektori bilan ifodalanadi: ; natijada boshqa holatga o‘tiladi: :
- , bunda Furye almashtirishining amplitudasi quyidagicha aniqlanadi:
- .
- Ikki o‘lchamli -tekislikda Furye almashtirishi koordinata o‘qlarini 90° ga aylantirishga mos keladi, natijada shkalasi quyidagiga almashadi: . Uchinchi bosqichda birinchi registr holatiga Furye almashtirishi qo‘llanadi va quyidagi natija olinadi:
- .
- To‘rtinchi bosqich. To‘rtinchi bosqichda birinchi registr ortogonal proyeksiyaga nisbatan o‘lchanadi; proyeksiya quyidagicha:
- , bu yerda — birlik operatori quyidagi Hilbert fazosiga tegishli; bu ikkinchi registrdir: .
Natijada quyidagi ehtimollik bilan olinadi:
- .
Jarayonning qolgan qismida klassik kompyuter ishlaydi:
- Quyidagi ifodaning eng yaxshi quyi yaqinlashuvi topiladi: , uning maxraji
- .
- Quyidagi qiymatni sinab ko‘ramiz: ni quyidagi qiymat o‘rnida: :
- Agar bo‘lsa, quyidagini hisoblash kerak: .
- Agar toq bo‘lsa yoki juft bo‘lsa-yu, lekin quyidagi sonning o‘zidan boshqa bo‘luvchisi: topilmasa, jarayonni marta aynan shu bilan takrorlash kerak. Natija chiqmasa, qiymatini o‘zgartirib, algoritmni qaytadan boshlash kerak.
Ma’lum ma’noda funksiya davrini Furye almashtirishi orqali aniqlash kristall panjara doimiylarini rentgen yoki neytron difraksiyasi usulida o‘lchashga o‘xshaydi. Davrni aniqlash uchun funksiyaning barcha qiymatlarini hisoblash talab etilmaydi: . Shu ma’noda masala Doych masalasigao‘xshaydi: bu masalada funksiyaning barcha qiymatlarini emas, balki uning ayrim xossalarini bilish muhim.
Algoritmda funksiya davrini topish
Faraz qilaylik, — davri noma’lum bo‘lgan funksiya; davr
- .
Davrni aniqlash uchun , o‘lchamlari quyidagicha bo‘lgan ikkita registr kerak: va kubit. Dastlab ular quyidagi holatda bo‘lishi kerak: .
Birinchi bosqichda birinchi registrning barcha bazis vektorlari quyidagi operator yordamida bir tomonlama superpozitsiyaga o‘tkaziladi: , operator quyidagi ko‘rinishda:
- , bu yerda va .
Bu yerda psevdo-Adamar almashtirishi qo‘llanadi. Quyidagi amalni joriy holatga qo‘llasak, quyidagini olamiz:
- .
Ikkinchi registrni o‘lchash natijasi , bu yerda , holatni quyidagiga olib keladi:
- bu yerda .
Quyidagi holat o‘lchangandan keyin birinchi registr faqat quyidagi ko‘rinishdagi bazis vektorlardan iborat bo‘ladi: shundayki, barcha qiymatlar uchun . Shu sababli u diskret, bir jinsli spektrga ega. Birinchi registrni o‘lchash orqali davrni yoki uning karralisini bevosita aniqlash mumkin emas, chunki bu yerda — tasodifiy kattalik. Shu bois diskret Furye almashtirishi quyidagi ko‘rinishda
- registrga qo‘llanadi, chunki o‘zgartirilgan holat spektrining ehtimolligi siljishga nisbatan o‘zgarmaydi (faqat fazalar o‘zgaradi, amplitudalarning mutlaq qiymatlari esa o‘zgarmaydi).
- .
- ,
- bu yerda va .
Agar quyidagi songa karrali bo‘lsa: , u holda , agar quyidagi songa karrali bo‘lsa: va aks holda. Hatto 2 ning darajasi bo‘lmasa ham, spektr quyidagi davrga ega alohida cho‘qqilarni ko‘rsatadi: , chunki
Birinchi registr uchun ta kubit ishlatiladi, bunda , chunki bu keltirilgan yig‘indida kamida ta element bo‘lishini kafolatlaydi; shunday qilib, cho‘qqilarning kengligi taxminan .
Agar endi birinchi registr o‘lchansa, quyidagi qiymat olinadi: , u quyidagiga yaqin: , bu yerda . Uni quyidagicha yozish mumkin: . Bu quyidagi ifodaning approksimatsiyasini topishga keltiriladi: , bu yerda , ikkilik nuqtadan keyingi muayyan raqamlar soni uchun . Ushbu masalani yechish uchun uzluksiz kasrlar qo‘llanadi.
Ratsional sonni ifodalash shakli yagona bo‘lmagani sababli, va quyidagicha aniqlanadi: , agar . Quyidagi ikkita sonning: va tub bo‘lish ehtimoli dan katta. Shuning uchun muvaffaqiyat ehtimoli birga yaqin bo‘lishi uchun atigi ta urinish zarur.
Diskret logarifmlash
Yana bir matematik masala — diskret logarifmlashasimmetrik kriptografik tizimlarni yaratishda tez-tez qo‘llanadi. U ham Shor shu maqolada taklif qilgan kvant algoritmi oldida zaifdir.
Adabiyotlar
- Feynman R. Kompyuterlar yordamida fizikani modellashtirish (ingliz tilida) // Nazariy fizika xalqaro jurnali — Springer Science+Business Media, 1982. — jild 21, son 6 / 7. — bet 467–488. — ISSN 0020-7748; 1572-9575 — doi:10.1007/BF02650179
- Feynman R. Kvant-mexanik kompyuterlar (ingliz tilida) // Fizika asoslari / Gerard ’t Hoft — Springer Science+Business Media, 1986. — jild 16, son 6. — bet 507–531. — ISSN 0015-9018; 1572-9516 — doi:10.1007/BF01886518
- D B., AN C., S D., J P., Bekman D., Chari A. N., Devabhaktuni S., Preskill J. Kvant faktorizatsiyasi uchun samarali tarmoqlar (ingliz tilida) // Physical Review A: atom, molekula va optik fizika hamda kvant axborotini qamrab oladi — Kollej-Park: Amerika fizika jamiyati, 1996. — jild 54, son 2. — bet 1034—1063. — ISSN 2469-9926; 2469-9934; 2469-9942; 1050-2947 — doi:10.1103/PHYSREVA.54.1034 — PMID:9913575 — arXiv:quant-ph/9602016
- Shor P. Kvant hisoblashlari algoritmlari: diskret logarifmlar va faktorizatsiya (ingliz tilida) // Kompyuter fanlari asoslari bo‘yicha 1994-yilgi 35-yillik simpozium materiallari — IEEE, 1994. — bet 124–134. — ISBN 0-8186-6580-7 — doi:10.1109/SFCS.1994.365700
- Shor P. W. Kvant kompyuterida tub ko‘paytuvchilarga ajratish va diskret logarifmlash uchun polinomial vaqtli algoritmlar // Kompyuter fanlari asoslari : konferensiya nashrlari. — 1997. — bet 1484–1509.
- Valiyev K. A., Kokin A. A. Kvant kompyuterlari: umidlar va haqiqat. — Ijevsk: RXD, 2004. — 320 bet
- Fedotov I. Ye. Parallel dasturlash modellari. — M.: Solon-press, 2012. — 384 bet
Havolalar
- Shor P. W. Kvant hisoblashlari algoritmlari: diskret logarifmlar va faktorizatsiya // Kompyuter fanlari asoslari : konferensiya nashrlari. — 1994. — B. 124–134. — ISBN 0-8186-6580-7. — doi:10.1109/SFCS.1994.365700.
- Shor P. W. Kvant kompyuterida tub ko‘paytuvchilarga ajratish va diskret logarifmlash uchun polinomial vaqtli algoritmlar // Kompyuter fanlari asoslari : konferensiya nashrlari. — 1997. — B. 1484–1509.