← Arvutustehnika

Groveri otsingualgoritm

Leidke nõel heinakuhjast √N sammu asemel N

Interaktiivse simulatsiooni laadimine...

Miks √N ja mitte kiiremini?

Groveri algoritm saavutab O(√N) päringut ja see on tõestatavalt optimaalne. Iga iteratsioon pöörab olekut θ ≈ 2/√N radiaani.

Kuidas õiget vastust võimendatakse

Ühtlases superpositsioonis alustab iga kandidaat sama tillukese amplituudiga. Iga ring teeb kaht asja: oraakel pöörab sihtmärgi amplituudi märgi ümber ja seejärel peegeldab 'peegeldus keskmise suhtes' kõik amplituudid nende keskmise ümber — märgistatu tõuseb, ülejäänud langevad. Kordamisel läheneb sihtmärgi tõenäosus ühele. N = 1,000,000 pikkuse loendi puhul kontrollib klassikaline otsing keskmiselt 500,000 kirjet; Grover vajab vaid umbes 1,000.

Neli elementi, üks samm, kindlus

Kui N = 4 — kahe kubiti otsing — pole Grover mitte üksnes kiire, vaid täpne: üksainus iteratsioon tabab sihtmärki 100% tõenäosusega. Pöördenurk rahuldab tingimust sin(θ/2) = 1/√N = 1/2, seega θ = 60°, ja pärast ühte sammu on olek pöördunud täpselt (2·1+1)·30° = 90° sihttelje peale. See on haruldane juht, kus kvantalgoritm annab garanteeritud, mitte üksnes tõenäolise vastuse.

Ülesanne täielikult lahendatud

  1. Kaks iteratsiooni märgistatud elemendi leidmiseks 8 hulgast 5 sammu

    Groveri algoritm leiab märgitud elemendi 8 seast kahe iteratsiooniga. Mõtle välja, kust see kaks tuleb — ja mis juhtub, kui käivitada kolmas.

    |s′⟩ |w⟩ θ = 20.70° 2θ k = 0 12.50% k = 1 78.12% k = 2 94.53% k = 3 33.01%

    1. Enne töötlemise algust on olek ühtlane superpositsioon: iga element on võrdselt tõenäoline, seega on märgitud elemendi tõenäosus 1/8. See on sama mis klassikaline juhuslik pakkumine, ja paneel kuvab mõlemad, et seda selgitada.

      N=8:uniform superposition gives P=18=12.50%N=8:\quad \text{uniform superposition gives}\ P=\frac{1}{8}=12.50\%

    2. Iga Groveri iteratsioon on pööre fikseeritud nurga võrra kahemõõtmelises tasandis, mille moodustavad märgitud olek ja kõik ülejäänu. Nurk tuleneb amplituudist ning N = 8 korral on see umbes 20,7°.

      sin⁡θ=1N ⟹ θ=20.70∘;Pk=sin⁡2((2k+1)θ)\sin\theta=\frac{1}{\sqrt N}\ \Longrightarrow\ \theta=20.70^\circ;\quad P_k=\sin^2\left((2k+1)\theta\right)

    3. Seega ei ole tõenäosus kõver, mis tõuseb ja tasandub — see on siinus ruudus ning tõuseb järsult: 12,5%, seejärel 78,1%, seejärel 94,5%.

      k=1: 78.12%;k=2: 94.53%;k=3: 33.01%k=1:\ 78.12\%;\qquad k=2:\ 94.53\%;\qquad k=3:\ 33.01\%

    4. Optimaalne peatumispunkt on pööre, mis jõuab kõige lähemale 90°-le, mis on π/4 korda N-i ruutjuur. Kaheksa elemendi puhul on see 2,22, ja kuna murdosa iteratsioonist ei saa teha, on see 2.

      kopt=⌊π4N⌋=⌊2.221⌋=2k_{\text{opt}}=\left\lfloor\frac{\pi}{4}\sqrt N\right\rfloor=\left\lfloor2.221\right\rfloor=2

    5. Käivita kolmas ja pööre läheb märgist mööda. Tõenäosus langeb 33,0%-le — halvem kui pärast ühte iteratsiooni, ning suundub tagasi alguspunkti poole.

      classical ∼N2=4 queriesvsO ⁣(N)=2\text{classical}\ \sim\frac{N}{2}=4\ \text{queries}\quad\text{vs}\quad O\!\left(\sqrt N\right)=2

    Vastus

    Tööriist näitab nii lähte-superpositsiooni kui ka klassikalise 1 võimaluse korral N-st tulemuseks 12,50% ning peatab automaatse töö 2. sammul, kuid sammhaaval jätkates või otse lõppu liikudes jõuab 5. sammuni. Just üleminek parimast tulemusest valmistab üllatuse: rohkem iteratsioone halvendab tulemust, sest amplituudivõimendus on pööramine ja täisringiga jõutakse tagasi algusse. Seetõttu on ka Groveri algoritmi kiirendus kõigest ruutjuureline, mitte eksponentsiaalne — 90° saavutamiseks kulub ligikaudu √N pööret, nii et 8 elemendi puhul piisab 2-st, miljoni puhul aga 785-st. See on kasulik, kuid sugugi mitte selline eksponentsiaalne eelis, mida väljend „kvantotsing” võiks aimata lasta.

    Pk=sin⁡2((2k+1)θ) ROTATES: past kopt it falls againP_k=\sin^2\left((2k+1)\theta\right)\ \text{ROTATES}:\ \text{past}\ k_{\text{opt}}\ \text{it falls again}
Allikad (1)

· Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.