Kvant ustunligi — bu kvant hisoblash qurilmalarining klassik kompyuterlar amalda yecha olmaydigan masalalarni hal qila olish qobiliyatidir. Kvant afzalligi esa masalalarni tezroq hal qilish imkoniyatidir. Hisoblash murakkabligi nazariyasi nuqtayi nazaridan bu odatda superpolinom tezlashuvni, ya’ni eng yaxshi ma’lum yoki mavjud bo‘lishi mumkin bo‘lgan klassik algoritmga nisbatan shunday darajadagi tezlashuvni ta’minlashni anglatadi. Bu atamani Jon Preskill, ammo kvant hisoblash afzalligi tushunchasi, ayniqsa kvant tizimlarini modellashtirish sohasida, kvant hisoblash g‘oyasini ilgari surgan quyidagi olimlarning ishlariga borib taqaladi: Yuriy Manin (1980) va Richard Feynman (1981).
Shor algoritmi butun sonlarni ko‘paytuvchilarga ajratishda kvant kompyuterida polinom vaqt ichida ishlaydi va eng yaxshi ma’lum klassik algoritmga nisbatan shunday superpolinom tezlashuvni ta’minlaydi. Garchi bu hali qat’iy isbotlanmagan bo‘lsa-da, ko‘paytuvchilarga ajratish klassik hisoblash resurslari uchun murakkab masala deb hisoblanadi. Klassik hisoblash yordamida nimalarni bajarib bo‘lmasligini isbotlash qiyinligi kvant ustunligini hech qanday shartsiz namoyish etishdagi umumiy muammodir. Bu holat bozonlardan tanlama olish bo‘yicha Aaronson va Arxipovning taklifiga, D-Wave kompaniyasining frustratsiyalangan klaster halqasi (frustrated cluster loop) turidagi maxsus masalalariga va tasodifiy kvant sxemalaridan chiqish natijalarini tanlab olishga.
Butun sonlarni ko‘paytuvchilarga ajratish kabi, tasodifiy kvant sxemalarining chiqish taqsimotlaridan tanlama olish ham hisoblash murakkabligi haqidagi asosli farazlarga ko‘ra klassik kompyuterlar uchun qiyin masala hisoblanadi.
Tarix
Google ilgari 2017-yil oxirigacha 49 ta o‘ta o‘tkazuvchan kubitdan iborat massiv yordamida kvant ustunligini namoyish etish rejasini e’lon qilgan edi. Biroq 2018-yil yanvar oyi boshida bunday uskunani faqat Intel taqdim etishini e’lon qilgan edi.
2017-yil oktabrda IBM oddiy superkompyuterda 56 ta kubitni modellashtirishni namoyish etdi va shu orqali kvant ustunligi uchun talab qilinadigan kubitlar soni haqidagi bahoni oshirdi.
2018-yil noyabrda Google NASA bilan hamkorlikni e’lon qildi. Unga ko‘ra, NASA «Google kvant protsessorlarida ishlatilgan kvant sxemalari natijalarini tahlil qiladi va ... Google uskunalarini tekshirishga yordam berish hamda kvant ustunligi uchun boshlang‘ich taqqoslash ko‘rsatkichlarini belgilash maqsadida ularni klassik modellashtirish bilan solishtiradi».
2018-yilgi nazariy tadqiqotga ko‘ra, xatolik darajasi yetarlicha past bo‘lsa, «7 × 7 kubitli ikki o‘lchamli panjara va taxminan 40 ta takt sikli» yordamida kvant ustunligiga erishish mumkin.
21-iyun, 2019-yilda Scientific American jurnali Neven qonuniga asoslanib, kvant ustunligiga 2019-yilda erishilishi mumkinligini taxmin qildi.
20-sentabr, 2019-yilda Financial Times «Google 54 ta kubitdan iborat massiv yordamida kvant ustunligiga erishganini da’vo qilmoqda. Ulardan 53 tasi ishlashga yaroqli bo‘lib, hisoblashni 200 soniyada bajargan; oddiy superkompyuterga esa buning uchun taxminan 10 000 yil kerak bo‘lardi», deb xabar berdi. Bu haqdagi hisobot dastlab NASA saytida e’lon qilindi, biroq ko‘p o‘tmay olib tashlandi. Keyinchalik, 23-oktabrda kvant ustunligiga erishilgani rasman e’lon qilindi. Biroq IBM mutaxassislari taqdim etilgan ma’lumotlarni tahlil qilib, ayrim jihatlar optimal emasligini va bunday hisoblash klassik superkompyuterda atigi 2,5 kun davom etishini, da’vo qilingan 10 000 yil kerak bo‘lmasligini ta’kidladilar.
3-dekabr, 2020-yilda xitoylik olimlar o‘zlarining Szyuchjan nomli, chigallashgan fotonlar bilan ishlaydigan kvant kompyuteri kvant ustunligiga erishganini ma’lum qildilar. Ular 200 soniyada shunday hisoblashni bajardilarki, bu vazifani hal qilish uchun dunyodagi eng tezkor klassik kompyuterga yarim milliard yildan ortiq vaqt kerak bo‘lardi.
Hisoblash murakkabligi
Masalaning murakkabligi uni yechish uchun zarur resurslar hajmining kirish ma’lumotlari o‘lchami oshishi bilan qanday o‘zgarishini bildiradi. Klassik hisoblash murakkabligi nazariyasini olsak, kvant murakkabligi nazariyasi uning kengaytmasi sifatida quyidagi tizimning ishini tavsiflaydi: universal kvant kompyuteri. Bunda qurilmani yaratish yoki dekoherensiya va shovqinni bartaraf etish qiyinligi inobatga olinmaydi. Kvant axboroti — klassik axborotning umumlashmasi bo‘lganligi sababli, kvant kompyuteri har qanday klassik algoritmni modellashtira oladi.
Murakkablik sinflaridan biri — chegaralangan xatoli kvant polinom vaqti (BQP) — bu polinom vaqt ichida universal kvant kompyuterida yechiladigan qaror masalalari sinfi. BPQ sinfi klassik murakkablik sinflari bilan quyidagi iyerarxiya orqali bog‘langan: . Ushbu kiritilishlardan birortasi qat’iy ekanligi hali ham ochiq masala bo‘lib qolmoqda.
«Ha» yoki «yo‘q» javobini talab qiladigan qaror masalalaridan farqli ravishda, tanlama olish masalalarida ehtimollik taqsimotlaridan namunalar olinadi. Agar klassik algoritm ixtiyoriy kvant sxemasi chiqishidan tanlama olishga qodir bo‘lsa, polinom iyerarxiyasi uchinchi darajagacha qisqaradi, bu esa nihoyatda ehtimoldan yiroq deb hisoblanadi. BosonSampling — aniqroq taklif bo‘lib, uning klassik hisoblashdagi murakkabligi permanentni, ya’ni kompleks elementli katta matritsa permanentini hisoblash masalasining yechilmasligiga bog‘liq; bu masala #P-to‘liq hisoblanadi. Ushbu xulosani olishda ishlatilgan dalillar IQP usulida tanlama olishga ham tatbiq etilgan. Bunda o‘rtacha va eng yomon holatlardagi murakkablik bir xil degan farazning o‘zi yetarlidir.
Superpolinom tezlashuv
Quyidagi algoritmlar eng yaxshi ma’lum klassik algoritmlarga nisbatan superpolinom tezlashuvni ta’minlaydi:
Butun sonlarni ko‘paytuvchilarga ajratish uchun Shor algoritmi
Ushbu algoritm n-bitli butun sonni tub ko‘paytuvchilarga vaqt ichida ajratadi; eng yaxshi ma’lum klassik algoritmga vaqt kerak bo‘ladi, bu masala murakkabligining eng yaxshi yuqori chegarasi esa ga teng. Algoritm butun sonlarni ko‘paytuvchilarga ajratishga keltiriladigan istalgan masalani, jumladan, matritsalar guruhlarining toq tartibli maydonlarga tegishliligini aniqlash masalasini ham tezlashtirishi mumkin.
Kvant hisoblashlari uchun bu algoritm amaliy hamda tarixiy jihatdan muhimdir. U klassik kompyuterlar uchun murakkab deb hisoblanadigan masalaga taklif etilgan birinchi polinom vaqtli kvant algoritmi bo‘ldi. Ushbu masalaning murakkabligiga ishonch shu qadar yuqoriki, bugungi kunda eng keng qo‘llanadigan RSA shifrlash protokolining xavfsizligi ham ko‘paytuvchilarga ajratish qiyinligiga asoslanadi. Bu xavf «Y2Q muammosi» deb ataladi va «Y2K» — 2000-yil muammosiga qiyosan nomlangan.
Bozonlardan tanlama olish
Bu hisoblash modeli bir xil fotonlarni chiziqli optik tarmoq orqali yuborishga asoslanadi. U bir qancha farazlar qabul qilinganda klassik kompyuterlar yecha olmaydigan ayrim tanlama olish va qidirish masalalarini hal qilishi mumkin. Biroq yetarlicha katta yo‘qotish va shovqinga ega tizimda bozonlardan tanlama olishni samarali modellashtirish mumkinligi ko‘rsatilgan.
Hozirgacha bozonlardan tanlama olishning eng yirik tajribaviy amalga oshirilishi 6 ta modani o‘z ichiga oladi va shu sabab bir vaqtning o‘zida 6 tagacha foton bilan ishlay oladi. Bozonlardan tanlama olishni modellashtirish uchun eng yaxshi klassik algoritmning ishlash vaqti ga mutanosib bo‘lib, bu n fotonli va m ta chiqish modasiga ega tizim uchun o‘rinlidir. BosonSampling — R tilida yozilgan ochiq kodli algoritm dasturidir. Ushbu algoritm bozonlardan tanlama olish orqali kvant ustunligini namoyish etish uchun 50 ta foton kerak bo‘lishini taxmin qiladi.
Tasodifiy kvant sxemalarining chiqish taqsimotidan tanlama olish
Ixtiyoriy tasodifiy kvant sxemasini modellashtiruvchi eng yaxshi ma’lum algoritmning ishlash vaqti kubitlar soniga nisbatan eksponensial oshadi. Shunga asoslanib, tadqiqotchilar guruhi kvant ustunligini namoyish etish uchun taxminan 50 ta kubit yetarli bo‘lishini baholagan. Google 2017-yil oxirigacha 49 kubitli chip yaratib, ishga tushirish orqali kvant ustunligini namoyish etish niyatini e’lon qilgan. Bu chip istalgan zamonaviy klassik kompyuter uchun erishib bo‘lmaydigan taqsimotlardan maqbul vaqt ichida tanlama olishi kerak edi. Biroq superkompyuterda muvaffaqiyatli amalga oshirilgan eng yirik kvant sxemasi modellashtirishida 56 ta kubit bo‘lgan. Shuning uchun kvant ustunligini namoyish etish uchun zarur kubitlar sonini ko‘paytirish talab qilinishi mumkin.
Tanqid
Kvant kompyuterlari klassik kompyuterlarga qaraganda dekoherensiya va shovqin tufayli xatolarga ancha moyildir. Chegaraviy teoremaga ko‘ra, shovqinli kvant kompyuteri, agar har bir hisoblash siklida yuzaga keladigan xatolik ma’lum chegaradan past bo‘lsa, kvant xatolarini tuzatish kodlari yordamida shovqinsiz kvant kompyuterining ishini modellashtirishi mumkin. Sonli modellashtirish bu chegara 3 % ga yetishi mumkinligini ko‘rsatadi.
Biroq xatolarni tuzatish uchun zarur resurslar kubitlar soniga bog‘liq ravishda qanday o‘zgarishi noma’lum. Skeptiklar[qaysilari?] miqyosi kengaytiriladigan kvant tizimlarida shovqin xususiyatlari noma’lumligini kvant hisoblashlarni muvaffaqiyatli amalga oshirish va kvant ustunligini namoyish etish yo‘lidagi ehtimoliy to‘siq sifatida ko‘rsatadilar.
Adabiyotlar
- Mitio Kaku. Kvant ustunligi. Hamma narsani o‘zgartiradigan hisoblash inqilobi = Michio Kaku. Kvant ustunligi: kvant kompyuterlari inqilobi hamma narsani qanday o‘zgartiradi. — M.: Alpina non-fikshn, 2024. — B. 412. — ISBN 978-5-00139-728-1.
- Manin Yu. I. Hisoblanadigan va hisoblanmaydigan. — M.: Sovetskoye radio, 1980. — B. 13—15. — 128 bet, rasmlar bilan. — (Kibernetika). — 25 000 nusxa. — [Arxivlangan 13 noyabr 2024 yil.]
- Fedichkin L. Ye.. Kvant ustunligi ostonasida // Fan va hayot : jurnal. — 2023. — № 7. — B. 14—20. — ISSN 0028-1263. Arxivlangan 8 iyul 2023 yil.
- Aaronson S., Arkhipov A. Chiziqli optikaning hisoblash murakkabligi (inglizcha). — 2010. — 14-noyabr. — doi:10.48550/arXiv.1011.3245. — arXiv:1011.3245.
- Arute F., Arya K., Babbush R. va boshq. Dasturlanadigan o‘ta o‘tkazuvchan protsessor yordamida kvant ustunligiga erishish (inglizcha) // Nature : jurnal. — 2019. — oktabr (7779-son, 574-son). — 505—510-betlar. — ISSN 1476-4687. — doi:10.1038/s41586-019-1666-5. Arxivlangan 23 oktabr 2019 yil.
- Boixo S., Isakov S. V., Smelyanskiy V. N. va boshq. Yaqin muddatli qurilmalarda kvant ustunligini tavsiflash (inglizcha) // Nature Physics : jurnal. — 2018. — 23-aprel (14-jild, 6-son). — 595—600-betlar. — doi:10.1038/s41567-018-0124-x. — arXiv:1608.00263.
- Bremner M. J., Montanaro A., Shepherd D. J. Kommutativ kvant hisoblashlarda o‘rtacha holat murakkabligi va taxminiy modellashtirishni taqqoslash (inglizcha) // Physical Review Letters : jurnal. — 2016. — 18-avgust (117-jild, 8-son). — ISSN 0031-9007. — doi:10.1103/PhysRevLett.117.080501. — Bibcode:2016PhRvL.117h0501B. — arXiv:1504.07999. — PMID 27588839.
- Carolan J., Harrold C., Sparrow C. va boshq. Universal chiziqli optika (inglizcha) // Science. — 2015. — 14-avgust (349-jild, 6249-son). — 711—716-betlar. — ISSN 0036-8075. — doi:10.1126/science.aab3642. — arXiv:1505.01182. — PMID 26160375. Arxivlangan 16 dekabr 2020 yil.
- Feynman R. P. Fizikani kompyuterlar yordamida modellashtirish (inglizcha) // International Journal of Theoretical Physics[inglizcha] : jurnal. — 1982. — 1-iyun (21-jild, 6—7-son). — 467—488-betlar. — ISSN 0020-7748. — doi:10.1007/BF02650179. — Bibcode:1982IJTP...21..467F.
- Knill E. Haqiqiy shovqinli qurilmalarda kvant hisoblash (inglizcha) // Nature. — 2005. — 3-mart (434-jild, 7029-son). — 39—44-betlar. — ISSN 0028-0836. — doi:10.1038/nature03350. — Bibcode:2005Natur.434...39K. — arXiv:quant-ph/0410199. — PMID 15744292. Arxivlangan 28 iyun 2009 yil.
- Lund A. P., Bremner M. J., Ralph T. C. Kvant tanlama olish masalalari, BosonSampling va kvant ustunligi (inglizcha) // Npj Quantum Information[inglizcha] : jurnal. — 2017. — 13-aprel (3-jild, 1-son). — ISSN 2056-6387. — doi:10.1038/s41534-017-0018-2. — Bibcode:2017npjQI...3...15L. — arXiv:1702.03061. Arxivlangan 8 mart 2021 yil.
- Neville, A., Sparrow C., Clifford R. va boshq. Bozonlardan tanlama olish orqali kvant ustunligiga yaqin orada erishib bo‘lmaydi (inglizcha) // Nature Physics : jurnal. — 2017. — 2-oktabr (13-jild, 12-son). — 1153—1157-betlar. — ISSN 1745-2473. — doi:10.1038/nphys4270. — arXiv:1705.00686. Arxivlangan 6 avgust 2020 yil.
- Papageorgiou A., Traub J. F. Kvant hisoblash tezlashuvini o‘lchash ko‘rsatkichlari (inglizcha) // Physical Review A : jurnal. — 2013. — 12-avgust (88-jild, 2-son). — 022316-betlar. — ISSN 1050-2947. — doi:10.1103/PhysRevA.88.022316. — Bibcode:2013PhRvA..88b2316P. — arXiv:1307.7488.
- Rahimi-Keshari S., Ralph T. C. Kvant optikasini samarali klassik modellashtirish uchun yetarli shartlar (inglizcha) // Physical Review X : jurnal. — 2016. — 20-iyun (6-jild, 2-son). — 021039—1—021039-13-betlar. — doi:10.1103/PhysRevX.6.021039. — Bibcode:2016PhRvX...6b1039R. — arXiv:1511.06526.
- Rivest R. L., Shamir A., Adleman L. Raqamli imzolar va ochiq kalitli kriptotizimlarni yaratish usuli (inglizcha) // Communications of the ACM : jurnal. — 1978. — fevral (21-jild, 2-son). — 120—126-betlar. — ISSN 0001-0782. — doi:10.1145/359340.359342.
- Shor P. Kvant kompyuterida tub ko‘paytuvchilarga ajratish va diskret logarifmlar uchun polinom vaqtli algoritmlar (inglizcha) // SIAM Review : jurnal. — 1999. — 1-yanvar (41-jild, 2-son). — 303—332-betlar. — ISSN 0036-1445. — doi:10.1137/S0036144598347011. — Bibcode:1999SIAMR..41..303S. — arXiv:quant-ph/9508027.
- Shor P. W. Kvant kompyuteri xotirasida dekoherensiyani kamaytirish sxemasi (inglizcha) // Physical Review A : jurnal. — 1995. — 1-oktabr (52-jild, 4-son). — R2493—R2496-betlar. — doi:10.1103/PhysRevA.52.R2493. — Bibcode:1995PhRvA..52.2493S.
- Steane A. M. Kvant nazariyasida xatolarni tuzatuvchi kodlar (inglizcha) // Physical Review Letters : jurnal. — 1996. — 29-iyul (77-jild, 5-son). — 793—797-betlar. — doi:10.1103/PhysRevLett.77.793. — Bibcode:1996PhRvL..77..793S. — PMID 10062908.
- Vazirani U. Kvant murakkabligi nazariyasiga sharh (inglizcha) // Amaliy matematika simpoziumlari materiallari. — 2000. Arxivlangan 7 may 2021 yil.
- Watrous J. Kvant hisoblash murakkabligi (inglizcha) // Murakkablik va tizimlar fani ensiklopediyasi : ensiklopediya. — Nyu-York: Springer, 2009. — 7174—7201-betlar. — ISBN 9780387758886. — doi:10.1007/978-0-387-30440-3_428. — arXiv:0804.3401.