Гроверов алгоритам

Гроверов алгоритам је квантни алгоритам за претраживање несортиране базе података са Н уноса у О(Н^1/2) времену користећи О(лог Н) меморијског простора (видети велико О). Лов Гровер га је формулисао 1996.

У моделима класичног израчунавања, претраживање и сортирање несортиране базе података не може бити остварено за мање од линеарног времена (тако да је претраживање елемената члан - по - члан скоро оптимално). Гроверов алгоритам илуструје да у квантном моделу претрага може бити извршена брже од овога; то јест, његова временска сложеност О(Н^1/2) је асимптотски најбржа могућа за претраживање несортиране базе података у квантном моделу. Пружа квадратно побољшање, за разлику од других квантних алгоритама, који пружају експоненцијално побољшање у односу на њихове класичне алтернативе. Ипак, чак је и квадратно побољшање значајно када је Н велико.

Као и многи други квантни алгоритми, Гроверов алгоритам је пробабилистички у смислу да даје тачан резултат са високим процентом вероватноће. Вероватноћа појаве грешке може бити смањена понављањем алгоритма. (Пример детерминистичког квантног алгоритма је Деутсцх-Јозса алгоритхм, који увек даје тачан одговор.)

Примене

Иако се сврха Гроверовог алгоритма најчеће описује као "претраживање базе података", моће бити тачније описати је као "инверзија функције". Грубо речено, ако имамо функцију y=ф(x) која може бити евалуирана на квантном рачунару, овај алгоритам нам дозвољава да израчунамо x када је дато y. Инверзија функције је повезана са претрагом базе података тако што бисмо могли доћи до функције која даје тачну вредност y ако се x поклапа са жељеним уносом у базу, и још једну вредност y за остале вредности x.

Гроверов алгоритам се такође може користити за одређивање средишта и медијане скупа бројева, и за решавање проблема колизије. Алгоритам се може даље оптимизовати ако постоји више од једног траженог уноса и тражени број уноса је унапред познат.

Поставка

Узмимо несортирану базу података са Н уноса. Алгоритму је потребан Н-димензионални статусни простор Х, који може бити обезбеђен са н=лог₂ Н кјубита. Узимајући у обзир проблем одређивања индекса уноса базе података који задовољава неки постављени услов. Нека је ф функција која означава уносе базе података са 0 или 1, где је ф(ω)=1 ако и само ако ω задовољава тражени услов. Доступан нам је (преко квантне црне кутије) приступ ка подпроблему у облику линеарног оператора, У_ω, који се понаша као:

$U_{\omega }|\omega \rangle =-|\omega \rangle$

$U_{\omega }|x\rangle =|x\rangle \qquad {\mbox{za svako}}\ x\neq \omega$

Наш циљ је да идентификујемо индекс $|\omega \rangle$.

Кораци алгоритма

Квантно коло Репрезентација Гроверовог алгоритма

Кораци Гроверовог алгоритма су следећи: Нека је $|s\rangle$ униформна суперпозиција свих стања

$|s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=1}^{N}|x\rangle$.

Тада је оператор

$U_{s}=2\left|s\right\rangle \left\langle s\right|-I$

познат као Гроверов дифузиони оператор.

Ево алгоритма:

1. Иницијализација система у стање

   $|s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=1}^{N}|x\rangle$

2. Применити следеће "Гроверове итерације" р(Н) пута. Функција р(Н), која је асимптотски О(Н^½), описана је доле.
   1. Применити оператор $U_{\omega }$.
   2. Применити оператор $U_{s}$.
3. Применити мерење Ω. Резултати мерења ће бити λ_ω са вероватноћом која се приближава 1 за Н≫1. Из λ_ω, се може добити ω.

Прва итерација

Прелиминарна обсервација, паралелна са нашом дефиницијом

$U_{s}=2\left|s\right\rangle \left\langle s\right|-I$,

је да У_ω може бити изражено на алтернативни начин:

$U_{\omega }=I-2\left|\omega \right\rangle \left\langle \omega \right|$.

Да бисмо ово доказали довољно је проверити како се У_ω понаша у базним стањима:

$(I-2|\omega \rangle \langle \omega |)|\omega \rangle =|\omega \rangle -2|\omega \rangle \langle \omega |\omega \rangle =-|\omega \rangle =U_{\omega }|\omega \rangle$.

$(I-2|\omega \rangle \langle \omega |)|x\rangle =|x\rangle -2|\omega \rangle \langle \omega |x\rangle =|x\rangle =U_{\omega }|x\rangle$ за све $x\neq \omega$.

Следећа израчунавања показују шта се догађа у првој итерацији:

$\langle \omega |s\rangle =\langle s|\omega \rangle ={\frac {1}{\sqrt {N}}}$.

$\langle s|s\rangle =N{\frac {1}{\sqrt {N}}}\cdot {\frac {1}{\sqrt {N}}}=1$.

$U_{\omega }|s\rangle =(I-2|\omega \rangle \langle \omega |)|s\rangle =|s\rangle -2|\omega \rangle \langle \omega |s\rangle =|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle$.

$U_{s}(|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle )=(2|s\rangle \langle s|-I)(|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle )=2|s\rangle \langle s|s\rangle -|s\rangle -{\frac {4}{\sqrt {N}}}|s\rangle \langle s|\omega \rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle =$

$=2|s\rangle -|s\rangle -{\frac {4}{\sqrt {N}}}\cdot {\frac {1}{\sqrt {N}}}|s\rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle =|s\rangle -{\frac {4}{N}}|s\rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle ={\frac {N-4}{N}}|s\rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle$.

После примене два оператора ($U_{\omega }$ анд $U_{s}$ ), амплитуда траженог елемента је опала од $\left|\langle \omega |s\rangle \right|^{2}=1/N$ до $\left|\langle \omega |U_{s}U_{\omega }s\rangle \right|^{2}\approx 9/N$.

Опис $U_{\omega }$

Гроверовом алгоритму је потребан оператор "квантног одлучивања" $U_{\omega }$ Који препознаје решења траженог проблема и даје им негативан знак. Да бисмо одржали алгоритам претраге општим, оставићемо унутрашња дешавања одлучивања као црну кутију, али ћемо објаснити како је знак промењен. Одлучивање садржи функцију $f$ која враћа $f(x)=1$ ако је $|x\rangle$ решење траженог проблема и $f(x)=0$ у супротном. Одлучивање је линеарни оператор који делује на два кјубита, индекс кјубит $|x\rangle$ и кјубит одлучивања $|q\rangle$:

$|x\rangle |q\rangle {\overset {U_{\omega }}{\longrightarrow }}|x\rangle |q\oplus f(x)\rangle$

Као и обично, $\oplus$ означава сабирање по модулу 2. Операција мења кјубит одлучивања ако $f(x)=1$ или га у супротном оставља непромењеног. У Гроверовом алгоритму желимо да променимо знак стања $|x\rangle$ ако обележава решење. Ово је постигнуто постављањем кјубита претраживања у стање $(|0\rangle -|1\rangle )/{\sqrt {2}}$, које је промењено на $(|1\rangle -|0\rangle )/{\sqrt {2}}$ ако је $|x\rangle$ решење:

$|x\rangle \left(|0\rangle -|1\rangle \right)/{\sqrt {2}}{\overset {U_{\omega }}{\longrightarrow }}(-1)^{f(x)}|x\rangle \left(|0\rangle -|1\rangle \right)/{\sqrt {2}}$

Разматрамо $|x\rangle$ као промењено, пошто кјубит одлучивања није промењен, па по конвенцији кјубити одлучивања обично нису поменути у опису Гроверовог алгоритма. Мада је операција одлучивања $U_{\omega }$ једноставно написана као:

$|x\rangle {\overset {U_{\omega }}{\longrightarrow }}(-1)^{f(x)}|x\rangle$

Геометријски доказ коректности

Слика приказује геометријску репрезентацију прве итерације Гроверовог алгоритма. Вектор стања $|s\rangle$ је ротиран ка циљном вектору $|\omega \rangle$ ас схоwн.

Посматрајмо раван разапету са $|s'\rangle$ и $|\omega \rangle$, где је $|s'\rangle$ кет у подпростору нормалан на $|\omega \rangle$. Посматраћемо прву итерацију, која це понаша као иницијални кет $|s\rangle$. Пошто је $|\omega \rangle$ један од базних вектора у $|s\rangle$ преклапање је

$\langle s'|s\rangle ={\sqrt {\frac {N-1}{N}}}$

На геометријском језику, угао $\theta /2$ између $|s\rangle$ и $|s'\rangle$ је дат као:

$\sin \theta /2={\frac {1}{\sqrt {N}}}$

Оператор $U_{\omega }$ је рефлексија на хиперраван ортогоналну на $|\omega \rangle$ за векторе у равни разапете са $|s'\rangle$ и $|\omega \rangle$; нпр. понаша се као рефлексија преко $|s'\rangle$. Оператор $U_{s}$ је рефлексија кроз $|s\rangle$. Према томе, вектор стања остаје у равни разапетој са $|s'\rangle$ и $|\omega \rangle$ после сваке примене оператора $U_{s}$ и $U_{\omega }$, и једноставно је проверити да оператор $U_{s}U_{\omega }$ сваке Гроверове итерације ротира вектор стања за угао $\theta =2\arcsin {\frac {1}{\sqrt {N}}}$.

Потребно је да станемо када вектор стања прође близу $|\omega \rangle$; након овога, подитерације ротирају вектор стања даље од $|\omega \rangle$, умањујући вероватноћу добијања тачног одговора. Тачна вероватноћа тачности одговора је:

$\sin ^{2}\left(\left(r+{\frac {1}{2}}\right)\theta \right)$

где јер (цео) број Гроверових итерација. Најраније где добијамо меру близу оптималне је према томе $r\approx \pi {\sqrt {N}}/4$.

Алгебарски доказ коректности

Да бисмо обавили алгебарску анализу потребно је да откријемо шта се догађа када више пута применимо $U_{s}U_{\omega }$. Природан начин да се ово учини је помоћу анализе сопствених вредности матрице. Приметимо да током целокупног израчунавања, стање алгоритма је линеарна комбинација $s$ и $\omega$. Можемо написати дејство од $U_{s}$ и $U_{\omega }$ у нормалном простору разапетом са $\{|s\rangle ,|\omega \rangle \}$ као:

$U_{s}:a|\omega \rangle +b|s\rangle \mapsto (|\omega \rangle \,|s\rangle ){\begin{pmatrix}-1&0\\2/{\sqrt {N}}&1\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}.$

$U_{\omega }:a|\omega \rangle +b|s\rangle \mapsto (|\omega \rangle \,|s\rangle ){\begin{pmatrix}-1&-2/{\sqrt {N}}\\0&1\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}.$

Тако да у бази $\{|\omega \rangle ,|s\rangle \}$ (која није ни ортогонална нити база целокупног простора) дејство $U_{s}U_{\omega }$ примене $U_{\omega }$ праћено са $U_{s}$ дато је матрицом

$U_{s}U_{\omega }={\begin{pmatrix}-1&0\\2/{\sqrt {N}}&1\end{pmatrix}}{\begin{pmatrix}-1&-2/{\sqrt {N}}\\0&1\end{pmatrix}}={\begin{pmatrix}1&2/{\sqrt {N}}\\-2/{\sqrt {N}}&1-4/N\end{pmatrix}}.$

Испада да је ова матрица веома згодна Жорданова форма. Ако оријентишемо $t=\arcsin(1/{\sqrt {N}})$, то је

$U_{s}U_{\omega }=M{\begin{pmatrix}\exp(2it)&0\\0&\exp(-2it)\end{pmatrix}}M^{-1}$ где је $M={\begin{pmatrix}-i&i\\\exp(it)&\exp(-it)\end{pmatrix}}.$

Испоставља се да је р-ти степен матрице (У односу на р итерација)

$(U_{s}U_{\omega })^{r}=M{\begin{pmatrix}\exp(2rit)&0\\0&\exp(-2rit)\end{pmatrix}}M^{-1}$

Коришћењем ове форме можемо користити тригонометријске идентитете како бисмо израчунали вероватноћу посматрајући ω након р итерација поменутих у претходном одељку,

$\left|{\begin{pmatrix}\langle \omega |\omega \rangle &\langle \omega |s\rangle \end{pmatrix}}(U_{s}U_{\omega })^{r}{\begin{pmatrix}0\\1\end{pmatrix}}\right|^{2}=\sin ^{2}\left((2r+1)t\right)$.

Алтернативно, неко са правом може помислити да би време близу оптималног за разликовање било када су углови 2рт анд -2рт удаљени најдаље могуће, што је у вези са $2rt\approx \pi /2$ ор $r=\pi /4t=\pi /4\arcsin(1/{\sqrt {N}})\approx \pi {\sqrt {N}}/4$. Тада је систем у стању

$(|\omega \rangle \,|s\rangle )(U_{s}U_{\omega })^{r}{\begin{pmatrix}0\\1\end{pmatrix}}\approx (|\omega \rangle \,|s\rangle )M{\begin{pmatrix}i&0\\0&-i\end{pmatrix}}M^{-1}{\begin{pmatrix}0\\1\end{pmatrix}}=|w\rangle {\frac {1}{\cos(t)}}-|s\rangle {\frac {\sin(t)}{\cos(t)}}.$

Сада кратко израчунавање показује да обсервација доприноси тачном одговору ω са грешком О(1/Н).

Проширење простора за вишеструке поготке

Ако, уместо једног траженог уноса, постоји к уноса који одговарају, исти алгоритам важи, али број итерација мора бити π(Н/к)^1/2/4 уместо πН^1/2/4. Постоји неколико начина да се суочимо са случајем када је к непознато. На пример, један може применити Гроверов алгоритам неколико пута, са

$\pi {\frac {N^{1/2}}{4}},\pi {\frac {(N/2)^{1/2}}{4}},\pi {\frac {(N/4)^{1/2}}{4}},\ldots$

итерација. За произвољно к, једна од итерација ће пронаћи тражени унос са довољно високом вероватноћом. Укупан број итерација је највише

$\pi {\frac {N^{1/2}}{4}}\left(1+{\frac {1}{\sqrt {2}}}+{\frac {1}{2}}+\cdots \right)$

што је и даље О(Н^1/2). Може се показати да ово може бити унапређено. Ако је број означених појмова к, где је к непознато, постоји алгоритам који налази решење за ${\sqrt {N/k}}$ упита. Ова чињеница се може искористити за решавање проблема колизија.,

Парцијална квантна претрага

Модификацију Гроверовог алгоритм,а названу парцијална квантна претрага, описали су Гровер и Радхакришнан 2004. године I парцијалној претрази, нисмо заинтересовани за проналажење тачне адресе траженог појма, само неколико првих цифара адресе. Еквивалентно, можемо то посматрати као "сецкање" простора обухваћеног претрагом у блокове, и онда питати "у ком блоку се налази тражени појам?". У многим применама, оваква претрага доприноси довољно информација ако циљна адреса садржи тражену информацију. Како бисмо то показали, користићемо пример дат од стране L.К. Гровера, ако имамо листу студената уређену по просеку оцена, можемо бити заинтересовани само да ли је студент у доњем 25%, 25-50%, 50-70% или 75-100% проценту.

Да бисмо описали парцијалну претрагу, користићемо базу података подељену на $K$ блокова, од којих је сваки величине $b=N/K$. Очигледно, проблем парцијалне претраге је једноставнији. Размотримо класичан приступ - одаберемо насумично један блок, па затим применимо уобичајену претрагу кроз остатак блокова (на језику теорије скупова лангуаге, комплемент). Уколико не пронађемо тражени појам, знаћемо да није у блоку у коме смо тражили. Просечан број итерација креће се од $N/2$ до $(N-b)/2$.

Гроверовом алгоритму је потребно $\pi /4{\sqrt {N}}$ итерација. Парцијална претрага ће бити бржа за нумерички фактор који зависи од броја блокова $K$. Парцијална претрага користи $n_{1}$ глобалних итерација $n_{2}$ локалних итерација. Глобални Гроверов оператор је означен са $G_{1}$ док је локални Гроверов оператор означен са $G_{2}$.

Глобални Гроверов оператор делује на блокове. Специјално, дат је као:

1. Применити $j_{1}$ стандардних Гроверових итерација на целокупну базу.
2. Применити $j_{2}$ локалних Гроверових итерација. Локална Гроверова итерација је директна сума Гроверових итерација и сваког блока.
3. Применити једну стандатдну Гроверову итерацију

Оптималне вредности $j_{1}$ и $j_{2}$ су размотрене у чланку Гровера и Радхакришнана. Неко се може запитати шта се дешава ако се примени узастопна парцијална претрага на различитим нивоима "резолуције". Ова идеја је детаљно проучена од стране Корепина анд Ксуа, који су је назвали квантно бинарно стабло претраге. Доказали су да да није бржа у односу на примену једне парцијалне претраге.

Оптималност

Познато је да је Гроверов алгоритам оптималан. Што ће рећи, било који алгоритам који приступа бази података коришћењем само оператора У_ω мора применити У_ω најмање онолико пута колико и Гроверов алгоритам. Овај резултат је битан за разумевање ограничења квантног израчунавања. Да је проблем Гроверове претраге решив за лог^ц Н применом У_ω, из тога би следило да је класа НП садржана у БQП, свођењем проблема из НП на проблеме типа Гроверове претраге. Оптималност Гроверовог алгоритма налаже (али не доказује) да класа НП није садржана у БQП.

Број итерација за к пронађених погодака, π(Н/к)^1/2/4, је такође оптималан.

Литература

• Гровер, Лов К. (1996). „А фаст qуантум мецханицал алгоритхм фор датабасе сеарцх”. Бибцоде:1996qуант.пх..5043Г. арXив:qуант-пх/9605043 . 
• Гровер, Лов К. (2001). „Фром Сцхрöдингер'с еqуатион то тхе qуантум сеарцх алгоритхм”. Прамана. 69 (7): 769—777. Бибцоде:2001Прама..56..333Г. С2ЦИД 9505022. арXив:qуант-пх/0109116 . дои:10.1007/с12043-001-0128-3. 
• Ниелсен, M.А. анд Цхуанг, I.L. Qуантум цомпутатион анд qуантум информатион. Цамбридге Университy Пресс, 2000. Цхаптер 6.
• Wхат'с а Qуантум Пхоне Боок?, Лов Гровер, Луцент Тецхнологиес
• Лавор, C.; Манссур, L. Р. У.; Португал, Р. (2003). „Гровер'с Алгоритхм: Qуантум Датабасе Сеарцх”. Бибцоде:2003qуант.пх..1079Л. арXив:qуант-пх/0301079 . 
• Гровер'с алгоритхм он арxив.орг

Спољашње везе

• Grover's Algorithm simulation and circuit diagram.
• Grover’s Quantum Search Algorithm Архивирано на сајту Wayback Machine (17. новембар 2020) animated explanation.
• Simulation and circuit diagram with cats