
Grover algoritmi (shuningdek, GSA — ingl. Grover search algorithm) — kvant algoritmi bo‘lib, variantlarni birma-bir tekshirish masalasini, ya’ni quyidagi tenglamaning yechimini topish masalasini hal qiladi
bu yerda — Bul funksiyasi bo‘lib, n ta o‘zgaruvchiga bog‘liq. Algoritmni amerikalik matematik Lov Grover 1996-yilda taklif qilgan.
Faraz qilinishicha, funksiyasi qora quti yoki orakul sifatida berilgan. Ya’ni yechimni izlashda orakulga faqat quyidagi turdagi savolni berish mumkin: « funksiyasining ushbu argumentdagi qiymati nechaga teng: ?», va olingan javobdan keyingi hisoblashlarda foydalanish mumkin. Demak, (1) tenglamani yechish masalasi variantlarni birma-bir tekshirish masalasining umumiy shaklidir: bunda «qurilmaning paroli », buning uchun klassik usulda to‘liq qidirish orqali barcha variantni tekshirish kerak bo‘ladi.
Grover algoritmi tenglamaning biror ildizini topish uchun marta funksiyasiga murojaat qiladi va buning uchun kubitdan foydalanadi.
Grover algoritmining mohiyati boshqa barcha holatlar amplitudasini kamaytirish hisobiga maqsadli holat amplitudasini «kuchaytirish[ingl.]»dan iborat. Geometrik nuqtayi nazardan, Grover algoritmi kvant kompyuterining joriy holat vektorini aynan maqsadli holat yo‘nalishida buradi (eng qisqa yo‘l bo‘ylab harakatlanish algoritmning optimalligini ta’minlaydi). Har bir qadamda vektor burchakka buriladi; bunda va orasidagi burchak ga teng. G operatori iteratsiyalarini davom ettirish ushbu vektorlar hosil qilgan haqiqiy tekislikdagi aylana bo‘ylab harakatni davom ettiradi.
Grover algoritmidagi «amplitudani kuchaytirish» ko‘p jismli kvant nazariyasida, aftidan, fundamental fizik hodisadir. Masalan, «kam uchraydigan» deb hisoblangan hodisalarning ehtimollarini baholashda uni hisobga olish zarur. Grover algoritmi sxemasini amalga oshiruvchi jarayon dastlab nihoyatda kichik bo‘lgan amplitudani keskin oshiradi va uni qisqa vaqt ichida amalda kuzatish mumkin bo‘lgan qiymatlarga yetkazishi mumkin.
Grover algoritmidan sonlar ketma-ketligining medianasi va o‘rtacha arifmetik qiymatini topishda ham foydalanish mumkin. Bundan tashqari, u ehtimoliy yechimlar to‘plamini to‘liq ko‘rib chiqish orqali NP-to‘liq masalalarni yechishda qo‘llanishi mumkin. Bu klassik algoritmlarga nisbatan tezlikni sezilarli oshirishi mumkin, biroq umumiy holda «polinomial yechim»ni ta’minlamaydi.
Tavsif
Faraz qilaylik, — Gilbert fazosini gipertekislikka nisbatan akslantiruvchi unitar operator bo‘lsin; bu gipertekislikka perpendikulyar vektor — , — (1) tenglamaning ildiziga mos holat, — barcha holatlarning teng amplitudali superpozitsiyasidir.
Grover algoritmi operatorini holatiga sonining butun qismiga teng miqdorda qo‘llashdan iborat. Natijada olingan holat deyarli holatiga mos keladi. Olingan holatni o‘lchash orqali birga yaqin ehtimol bilan javob topiladi.
Izohlar
Faraz qilaylik, (1) tenglamaning ta ildizi bor. Bunday masalani yechishning klassik algoritmi (chiziqli qidiruv), tabiiyki, marta funksiyasiga murojaat qilishni talab etadi, bunda yechimni topish ehtimoli ga teng. Grover algoritmi esa qidiruv masalasini vaqt ichida yechadi, ya’ni vaqt klassik usuldagiga nisbatan kvadrat ildiz tartibida qisqaradi. Bu juda katta tezlashuvdir. Grover algoritmi quyidagi jihatlar bo‘yicha optimal ekani isbotlangan:
- Qiymati bo‘lgan doimiyni yaxshilash mumkin emas.
- Kvadratik tezlashuvdan kattaroq kvant tezlashuviga erishib bo‘lmaydi.
Grover algoritmi orakulga bog‘liq umumiy masalaning namunasi hisoblanadi. Aniqroq xususiy masalalarda kattaroq kvant tezlashuviga erishish mumkin. Masalan, Shorning ko‘paytuvchilarga ajratish algoritmi tegishli klassik algoritmlarga nisbatan eksponensial ustunlik beradi.
Shuni ta’kidlash kerakki, f funksiyasining qora quti ko‘rinishida berilgani, umumiy holda, na kvant, na klassik algoritmlarning murakkabligiga ta’sir ko‘rsatadi. f funksiyasining «ichki tuzilishi»ni bilish (masalan, uni ifodalovchi mantiqiy elementlar sxemasini bilish) odatda (1) tenglamani yechishda yordam bermaydi. Ma’lumotlar bazasida qidirish argument x qidirilayotgan yozuvga mos kelganda ma’lum bir qiymatni qaytaruvchi funksiyaga murojaat qilish bilan bog‘liq.
Grover sxemasidan foydalanadigan algoritmlar
- Butun qiymatli funksiyaning ekstremumini qidirish algoritmi (P. Xoyer va boshqalar). Quyidagi funksiyaning eng katta qiymati izlanadi: . Kvant algoritmi maksimumni marta murojaat qilib topadi; murojaat qilinadigan funksiya — f.
- Tuzilmaviy qidiruv algoritmi (Farxi, Gutman). (1) tenglamaning yechimi qo‘shimcha sharti ostida izlanadi, bu yerda — satrining teng uzunlikdagi ikkita satrga ajratilishi. Algoritmning murakkabligi klassik hisoblash vaqtining kvadrat ildizi tartibidadir.
- Ma’lumotlar bazasida bir xil satrlarni qidirish algoritmi (Ambaynis). kabi ikki xil argument izlanadi; ularda funksiyasi bir xil qiymatni qabul qiladi. Algoritm marta quyidagi funksiyaga murojaat qilishni talab etadi: f.
Variantlar va umumlashtirishlar
Grover algoritmining uzluksiz variantlari
- Faraz qilaylik, kvant tizimining gamiltoniani quyidagi ko‘rinishga ega: , bu yerda va mos ravishda hamda operatorlarini ifodalaydi. U holda gamiltoniani bilan holatidan boshlangan uzluksiz unitar evolyutsiya tabiiy ravishda holatiga olib keladi. Grover algoritmining bunday uzluksiz analogi murakkabligi diskret holatdagisi bilan aynan bir xil.
- Grover algoritmining adiabatik varianti. turidagi asosiy holatning f ga bog‘liq gamiltonian ta’sirida sekin evolyutsiyasi, adiabatik teoremaga muvofiq, tartibidagi vaqt ichida tizimni quyidagi holatga olib keladi: .
Havolalar
- Grover L. K. Kvant mexanikasi pichan ichidan ignani topishga yordam beradi (yuklab olish uchun)
- Loginov O. V. va Siganov A. V. Groverning kvant algoritmi, Sankt-Peterburg davlat universiteti
- Dastlabki kodlar C++ tilidagi kvant kompyuteri simulyatori va Grover algoritmi dasturiy amalga oshirilishining batafsil tavsifi hamda kvant ventillari sxemalari