Grover qidiruv algoritmi

Grover algoritmi

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

(1)f(x)=1,

bu yerda f — Bul funksiyasi bo‘lib, n ta o‘zgaruvchiga bog‘liq. Algoritmni amerikalik matematik Lov Grover 1996-yilda taklif qilgan.

Faraz qilinishicha, f funksiyasi qora quti yoki orakul sifatida berilgan. Ya’ni yechimni izlashda orakulga faqat quyidagi turdagi savolni berish mumkin: «f funksiyasining ushbu argumentdagi qiymati nechaga teng: x?», va olingan javobdan keyingi hisoblashlarda foydalanish mumkin. Demak, (1) tenglamani yechish masalasi variantlarni birma-bir tekshirish masalasining umumiy shaklidir: bunda «qurilmaning paroli f», buning uchun klassik usulda to‘liq qidirish orqali barcha N=2n variantni tekshirish kerak bo‘ladi.

Grover algoritmi tenglamaning biror ildizini topish uchun π4N marta f funksiyasiga murojaat qiladi va buning uchun O(n) 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 2α burchakka buriladi; bunda I0~ va Ixtar orasidagi burchak π/2−α 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, Ia — Gilbert fazosini gipertekislikka nisbatan akslantiruvchi unitar operator bo‘lsin; bu gipertekislikka perpendikulyar vektor — a, |xtar⟩ — (1) tenglamaning ildiziga mos holat, |0~⟩=1N∑j|j⟩ — barcha holatlarning teng amplitudali superpozitsiyasidir.

Grover algoritmi G=−I0~Ixtar operatorini |0~⟩ holatiga πN/4 sonining butun qismiga teng miqdorda qo‘llashdan iborat. Natijada olingan holat deyarli |xtar⟩ holatiga mos keladi. Olingan holatni o‘lchash orqali birga yaqin ehtimol bilan javob topiladi.

Izohlar

Faraz qilaylik, (1) tenglamaning l ta ildizi bor. Bunday masalani yechishning klassik algoritmi (chiziqli qidiruv), tabiiyki, O(Nl) marta f funksiyasiga murojaat qilishni talab etadi, bunda yechimni topish ehtimoli 12 ga teng. Grover algoritmi esa qidiruv masalasini O(Nl) 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 π4 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: f:{0,1}n→{0,1}n. Kvant algoritmi maksimumni O(N) marta murojaat qilib topadi; murojaat qilinadigan funksiya — f.
  • Tuzilmaviy qidiruv algoritmi (Farxi, Gutman). (1) tenglamaning yechimi qo‘shimcha g(x1)=1 sharti ostida izlanadi, bu yerda x=x1x2 — x satrining teng uzunlikdagi ikkita satrga ajratilishi. Algoritmning murakkabligi klassik hisoblash vaqtining kvadrat ildizi tartibidadir.
  • Ma’lumotlar bazasida bir xil satrlarni qidirish algoritmi (Ambaynis). x1≠x2 kabi ikki xil argument izlanadi; ularda f:{0,1}n→{0,1}n funksiyasi bir xil qiymatni qabul qiladi. Algoritm O(N3/4) marta quyidagi funksiyaga murojaat qilishni talab etadi: f.

Variantlar va umumlashtirishlar

Grover algoritmining uzluksiz variantlari

  • Faraz qilaylik, kvant tizimining gamiltoniani quyidagi ko‘rinishga ega: H=H1+H2, bu yerda exp⁡(iH1) va exp⁡(iH2) mos ravishda I0~ hamda Ixtar operatorlarini ifodalaydi. U holda H gamiltoniani bilan |0~⟩ holatidan boshlangan uzluksiz unitar evolyutsiya tabiiy ravishda |xtar⟩ holatiga olib keladi. Grover algoritmining bunday uzluksiz analogi murakkabligi diskret holatdagisi bilan aynan bir xil.
  • Grover algoritmining adiabatik varianti. |0~⟩ turidagi asosiy holatning f ga bog‘liq gamiltonian ta’sirida sekin evolyutsiyasi, adiabatik teoremaga muvofiq, N tartibidagi vaqt ichida tizimni quyidagi holatga olib keladi: |xtar⟩.

Havolalar