Groverin algoritmi

Groverin algoritmi ( englanniksi myös GSA . Grover search algorithm ) on kvanttialgoritmi laskentaongelman ratkaisemiseen eli yhtälön ratkaisun löytämiseen

(1)\qquad f(x)=1,

missä on n muuttujan Boolen funktio . [1] Sen ehdotti amerikkalainen matemaatikko Lov Grover vuonna 1996 . $f$

Oletetaan, että funktio annetaan mustan laatikon tai oraakkelin muodossa , eli ratkaisun aikana voit kysyä oraakkelilta vain kysymyksen, kuten: "mitä se on tässä ?" , ja käytä vastausta lisälaskelmissa. Toisin sanoen yhtälön (1) ratkaisutehtävä on brute-force-ongelman yleinen muoto: tässä on löydettävä "laitteen salasana ", joka klassisesti vaatii kaikkien vaihtoehtojen täydellisen luettelon . $f$ $f$ $x$ $f$ $N = 2^n$

Groverin algoritmi löytää yhtälön juuren käyttämällä funktiokutsuja kubittien avulla . [2] ${\frac {\pi }{4}}{\sqrt {N}}$ $f$ $Päällä)$

Groverin algoritmin tarkoitus on " lisää kohdetilan amplitudia " vähentämällä kaikkien muiden tilojen amplitudia. Geometrisesti Groverin algoritmi koostuu kvanttitietokoneen nykyisen tilavektorin kiertämisestä täsmälleen kohdetilaan (lyhintä polkua pitkin liikkuminen varmistaa Groverin algoritmin optimaalisen). Jokainen askel antaa kulman verran kiertoa , jossa ja välinen kulma on . Operaattorin G iteraatioiden jatkaminen antaa jatkon ympyrän kiertämiselle näiden vektoreiden muodostamassa todellisessa tasossa. $2\alpha$ $I_{{{\tilde 0}}}$ $I_{{x_{{tar}}}}$ $\pi /2-\alpha$

Groverin "amplitudivahvistus" näyttää olevan perustavanlaatuinen fyysinen ilmiö kvanttimonikehoteoriassa. Se on otettava huomioon esimerkiksi "harvinaiselta" vaikuttavien tapahtumien todennäköisyyksien arvioimiseksi. Prosessi, joka toteuttaa Grover-algoritmikaavion, johtaa alun perin merkityksettömän amplitudin räjähdysmäiseen kasvuun, joka voi nopeasti tuoda sen todella havaittaviin arvoihin.

Groverin algoritmia voidaan käyttää myös lukusarjan mediaanin ja aritmeettisen keskiarvon löytämiseen . Lisäksi sitä voidaan käyttää NP-täydellisten ongelmien ratkaisemiseen etsimällä tyhjentävästi mahdollisten ratkaisujen joukosta. Tämä voi johtaa merkittäviin nopeuden lisäyksiin verrattuna klassisiin algoritmeihin, vaikkakaan ilman " polynomiratkaisua " yleisesti ottaen.

Kuvaus

Olkoon unitaarinen operaattori, joka peilaa Hilbert-avaruutta vektoriin nähden kohtisuoraan hypertasoon nähden , on yhtälön (1) juurta vastaava tila, on kaikkien tilojen tasainen superpositio. $minä_{a}$ $a$ $|x_{{tar}}\rangle$ $|{\tilde 0}\rangle ={\frac {1}{{\sqrt {N))))\sum \limits _{j}|j\rangle$

Groverin algoritmi koostuu operaattorin soveltamisesta tilaan useita kertoja, jotka ovat yhtä suuret kuin :n kokonaislukuosa . Tulos vastaa melkein tilaa . Saatua tilaa mittaamalla saadaan vastaus, jonka todennäköisyys on lähellä yhtä. $G=-I_{{{\tilde 0}}}I_{{x_{{tar}}}}$ $|{\tilde 0}\rangle$ $\pi {\sqrt {N}}/4$ $|x_{{tar}}\rangle$

Muistiinpanot

Oletetaan, että yhtälöllä (1) on juuret. Klassinen algoritmi tällaisen ongelman ratkaisemiseksi ( lineaarinen haku ) vaatii luonnollisesti kutsuja ongelman ratkaisemiseksi todennäköisyydellä . Groverin algoritmin avulla voit ratkaista hakutehtävän ajoissa , eli klassisen neliöjuuren järjestyksessä, mikä on valtava nopeus. On osoitettu, että Groverin algoritmi on optimaalinen seuraavissa suhteissa: $l$ $O({\tfrac {N}{l)))$ $f$ ${\tfrac {1}{2))$ $O({\sqrt {\tfrac {N}{l)})$

Vakiota ei voi parantaa [3] . ${\tfrac {\pi }{4}}$
Kvadraattista suurempaa kvanttikiihtyvyyttä ei voida saavuttaa [4] .

Groverin algoritmi on esimerkki oraakkelista riippuvaisesta massaongelmasta . Tarkempia ongelmia varten on mahdollista saada suurempi kvanttikiihtyvyys. Esimerkiksi Shor-faktorointialgoritmi antaa eksponentiaalisen vahvistuksen verrattuna vastaaviin klassisiin algoritmeihin.

Se, että f on annettu mustana laatikkona, ei yleensä vaikuta sekä kvantti- että klassisten algoritmien monimutkaisuuteen. Funktion f "laitteen" tuntemus (esimerkiksi sen toiminnallisista elementeistä määrittävän piirin tuntemus) ei yleensä auta yhtälön (1) ratkaisemisessa. Tietokannasta etsiminen tarkoittaa funktion kutsumista, joka ottaa tietyn arvon, jos x -argumentti vastaa haettua tietokannan merkintää.

Algoritmit Groverin kaaviolla

Algoritmi kokonaislukufunktion ääripään etsimiseen (P. Hoyer ym.). Haetaan funktion suurinta arvoa . Kvanttialgoritmi löytää maksimin f : stä . $f\colon \{0,1\}^{n}\rightarrow \{0,1\}^{n}$ $O({\sqrt {N)))$
Rakennehakualgoritmi (Farhi, Gutman). Yhtälön (1) ratkaisua etsitään lisäehdolla , jossa on merkkijonon jakaminen kahdeksi samanpituiseksi merkkijonoksi. Algoritmin monimutkaisuus on klassisen ajan neliöjuuren suuruusluokkaa. $g(x_{1})=1$ $x=x_{1}x_{2}$ $x$
Algoritmi vastaavien merkkijonojen löytämiseksi tietokannasta (Ambainis). Etsitään paria eri argumentteja , joilla funktio saa saman arvon. Algoritmi vaatii kutsuja f :lle . $x_{1}\neq x_{2}$ $f\colon \{0,1\}^{n}\rightarrow \{0,1\}^{n}$ $O(N^{{3/4}})$

Muunnelmia ja yleistyksiä

Jatkuvat versiot Groverin algoritmista

Olkoon kvanttijärjestelmän Hamiltonin muoto , missä ja ovat operaattorit ja vastaavasti. Sitten jatkuva unitaarinen evoluutio Hamiltonin kanssa alkaen , johtaa luonnollisesti . Tällaisen Groverin algoritmin jatkuvan analogin monimutkaisuus on täsmälleen sama kuin erillisessä tapauksessa. $H=H_{1}+H_{2}$ $\exp(iH_{1})$ $\exp(iH_{2})$ $I_{{{\tilde 0}}}$ $I_{{x_{{tar}}}}$ $H$ $|{\tilde 0}\rangle$ $|x_{{tar}}\rangle$
Groverin algoritmin adiabaattinen versio . Tyypin hidas perustilan kehitys f :stä riippuvan Hamiltonin vaikutuksesta adiabaattisen lauseen mukaan järjestysajan kuluessa johtaa tilaan . $|{\tilde 0}\rangle$ ${\sqrt {N}}$ $|x_{{tar}}\rangle$

Muistiinpanot

↑ GSA:ta kutsutaan joskus epätarkasti tietokannan hauksi .
↑ Algoritmin monimutkaisuus, sillä tehtävää oraakkelin kanssa kutsutaan myös sen työskentelyajaksi, määräytyy oraakkelin kutsujen lukumäärän mukaan.
↑ Christof Zalka, Groverin kvanttihakualgoritmi on optimaalinen, Phys.Rev. A60 (1999) 2746-2751 [1] (linkki ei saatavilla)
↑ Juri Ozhigov, Lower Bounds of Quantum Search for Extreme Point, Proc. Roy, Soc. London. A455 (1999) 2165-2172 [2]

Linkit

Grover L.K. Quantum mechanics auttaa löytämään neulan heinäsuovasta (lataa)
Loginov O. V. ja Tsyganov A. V. Groverin kvanttialgoritmi, Pietarin valtionyliopisto
Lähdetekstit kvanttitietokonesimulaattoriin C++-kielellä ja Groverin algoritmin toteutukset yksityiskohtaisella kuvauksella ja kaavioilla kvanttiporteista

Kvanttialgoritmit
Shorin algoritmi Groverin algoritmi Deutsch-Yozhi algoritmi Feynmanin ongelma Zalka-Wiesner-algoritmi kvanttihehkutus

kvanttiinformatiikka

Yleiset käsitteet

kvanttiviestintä

kvanttikanava
- kvanttiverkko
kvantti kryptografia
- Kvanttiavainten jakelu
Kvanttienergian teleportaatio
kvanttiteleportaatio
Ultra-tiheä kvanttikoodaus
LOCC
kvanttitislaus

Kvanttialgoritmit

kvanttisimulaattori
Deutsch-Yozhi algoritmi
Bernstein-Wazirani-algoritmi
Groverin algoritmi
Kvantti-Fourier-muunnos
Shorin algoritmi
Simonin ongelma
Kvanttivaiheen arviointialgoritmi
Kvanttilaskenta-algoritmi
kvanttihehkutus
Algoritminen jäähdytys
Kvanttialgoritmi lineaarisen yhtälöjärjestelmän ratkaisemiseen
Amplitudin vahvistus

Kvanttikompleksiteoria

Turingin kvanttikone
EQP
BQP
QMA
PostBQP
QIP

Kvanttilaskentamallit

kvanttipiiri
- kvanttiportti
Yksipuolinen kvanttitietokone
- klusterin
Adiabaattinen kvanttilaskenta
Topologinen kvanttitietokone

Epäkoherenssin ehkäisy

Kvanttivirheiden korjaus
Stabilointikoodit
Stabilointiformalismi
Kvanttikonvoluutiokoodi

Fyysiset toteutukset

kvanttioptiikka	Kavitaatiokvanttielektrodynamiikka Ääriviivan kvanttielektrodynamiikka Lineaariseen optiikkaan perustuva kvanttilaskenta KLM-protokolla Bosoninen näytteenotto
superkylmiä atomeja	Absorboituneen ionin kvanttitietokone Optinen ritilä
takaisin perustuva	Ydinmagneettiseen resonanssiin perustuva kvanttitietokone Kanen kvanttitietokone Häviö kvanttitietokone - DiVincenzo NV keskusta
Suprajohtavat kvanttitietokoneet	lataa qubit suoratoisto qubit Vaihe qubit Transmon