Kvant ustunligi nima

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: P⊆BPP⊆BQP⊆PSPACE. 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 O~(n3) vaqt ichida ajratadi; eng yaxshi ma’lum klassik algoritmga 2O(n1/3) vaqt kerak bo‘ladi, bu masala murakkabligining eng yaxshi yuqori chegarasi esa O(2n/3+o(1)) 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 O(n2n+mn2) 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