Kvant algoritmi nima

Kvant algoritmi — algoritm bo‘lib, u kvant kompyuterida bajarish uchun mo‘ljallangan.

Asosiy tamoyillar

Kvant algoritmi — unitar amallar (geytlar yoki kvant mantiqiy elementlari) ketma-ketligini va bu amallar aynan qaysi kubitlar ustida bajarilishi kerakligini belgilovchi klassik algoritmdir. Kvant algoritmi bunday ko‘rsatmalarning so‘z bilan ifodalangan tavsifi yoki geytlar tizimi (quantum gate array) ko‘rinishidagi grafik tasviri orqali beriladi.

Kvant algoritmi natijasi ehtimollik xususiyatiga ega. Algoritmdagi amallar sonini biroz oshirish orqali to‘g‘ri natija olish ehtimolini birga, ya’ni 100 foizga yaqinlashtirish mumkin.

Kvant va klassik kompyuterlarda yechilishi mumkin bo‘lgan masalalar to‘plami bir xil. Demak, kvant kompyuteri algoritmik jihatdan yechiladigan masalalar sonini ko‘paytirmaydi. Kvant kompyuteridan foydalanishning asosiy ma’nosi shundaki, u ayrim masalalarni istalgan klassik kompyuterga qaraganda ancha tezroq yecha oladi. Buning uchun kvant algoritmi hisoblash davomida o‘zaro chigallashgan kvant holatlarini hosil qilishi va ulardan foydalanishi kerak (Kvant superpozitsiyasi va Kvant chigallashuvi).

Kvant algoritmi yordamida yechiladigan har qanday masalani klassik kompyuterda ham eksponensial o‘lchamdagi unitar matritsalarni bevosita hisoblash va kvant holatlarini oshkor ko‘rinishda ifodalash orqali yechish mumkin. Xususan, klassik kompyuterlarda yechib bo‘lmaydigan masalalar (masalan, to‘xtash muammosi) kvant kompyuterlarida ham yechib bo‘lmaydiganligicha qoladi. Biroq bunday bevosita modellashtirish eksponensial vaqt talab qiladi. Shu sababli kvant parallelligidan foydalanib, ayrim klassik algoritmlarning kvant kompyuterida bajarilishini tezlashtirish imkoniyati yuzaga keladi.

Kvant kompyuteridagi tezlashuv protsessorning takt chastotasiga bog‘liq emas. U kvant parallelligiga asoslanadi. Kvant hisoblashning bir qadami klassik hisoblashning bir qadamiga nisbatan ancha ko‘p ish bajaradi. Ammo kvant hisoblashni parallel bajariladigan klassik hisoblash bilan tenglashtirish xato bo‘ladi. Masalan, kvant kompyuteri barcha variantlarni ko‘rib chiqish masalasini vaqtdan tezroq yecha olmaydi, bunda — deterministik klassik qidiruv algoritmining ishlash vaqti, nodeterministik klassik algoritm esa bu masalani vaqt ichida yechadi. Biroq nodeterministik klassik algoritm eksponensial hajmdagi xotira resursini talab qiladi, ya’ni uni jismonan amalga oshirib bo‘lmaydi. Kvant algoritmi esa tabiatning ma’lum qonunlariga zid emas.

Kvant hisoblash o‘ziga xos jarayondir. Unda maxsus fizik resurs — kvant chigallashgan holatlar ishlatiladi. Bu ayrim hollarda hisoblash vaqtini hayratlanarli darajada qisqartirish imkonini beradi. Bunday holatlar klassik hisoblashlarni kvant yordamida tezlashtirish deb ataladi.

Klassik algoritmlarning umumiy soni bilan solishtirganda, kvant yordamida tezlashuvga erishiladigan holatlar juda kam uchraydi. Shunga qaramay, bu kvant hisoblashning fundamental ahamiyatini kamaytirmaydi, chunki u variantlarni tekshirishga asoslangan masalalarni sezilarli darajada tezlashtira oladi.

Kvant tezlashuvining asosiy sxemalari

Kvant algoritmlari yordamida tezlashtiriladigan masalalarning asosiy turi variantlarni ko‘rib chiqishga asoslangan masalalardir. Ularni 2 ta asosiy guruhga ajratish mumkin:

  1. Murakkab tizimlar dinamikasini modellashtirish masalalari (Feynmanning dastlabki g‘oyasi)
  2. Variantlarni ko‘rib chiqishga keltiriladigan matematik masalalar:
    1. Variantlarni ko‘rib chiqishning umumiy holati: Grover sxemasi va uning variantlari
    2. Yashirin davrlarni qidirish masalalari: tezkor kvant Furye almashtirishidan foydalanishga asoslangan Shor sxemasi va uning o‘xshashlari.

1-tur Zalka — Vizner algoritmi orqali kvant tizimlarining ta zarrachadan iborat unitar dinamikasi deyarli real vaqt rejimida, xotiraning ga chiziqli bog‘liq sarfi bilan modellashtiriladi. Bu algoritm Shorning kvant Furye almashtirish sxemasidan foydalanadi.

2-turga quyidagilar kiradi:

  • umumiy qidiruv masalasi uchun Grover algoritmi va uning uzluksiz hamda adiabatik variantlari, shuningdek, Grover sxemasidan foydalanuvchi algoritmlar: tuzilmaviy qidiruv (Fari, Gutman), ekstremumni qidirish (Hoyer va boshqalar) hamda ma’lumotlar bazasidagi bir xil satrlarni qidirish (Ambaynis) algoritmlari
  • Shor algoritmi yordamida butun sonlarni ko‘paytuvchilarga ajratish, Abrams — Lloyd algoritmi yordamida davrni aniqlash, Kitayev algoritmi yordamida yashirin kichik guruhlarni topish va boshqalar

Kvant kompyuterining kelajakdagi qo‘llanilish imkoniyatlari nuqtayi nazaridan 1-tur eng katta qiziqish uyg‘otadi.

Tasniflash

Kvant algoritmlarini ularda ishlatiladigan kvant almashtirishlari turiga ko‘ra tasniflash mumkin. Keng qo‘llaniladigan almashtirishlar qatoriga quyidagilar kiradi: fazaning qaytuvchi ta’siri (phase kick-back), fazani baholash (phase estimation), kvant Furye almashtirishi (quantum Fourier transform), kvant yurishi (quantum walk), amplitudani kuchaytirish (amplitude amplification), topologik kvant maydon nazariyasi (topological quantum field theory). Kvant algoritmlarini ular yechadigan masalalar turiga qarab ham guruhlash mumkin.

Keng tanilgan algoritmlar

Havolalar