Groveri otsingualgoritm

Leidke nõel heinakuhjast √N sammu asemel N

Näidisarvutus — Groveri otsingualgoritm

Praegune iteratsioon	0 (Superpositsioon)
Sihtmärgi tõenäosus	12.50%
Klassikaline (1/N)	12.50%
Iteratsioon	0 / 2 · Superpositsioon

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

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

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.
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 = \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 θ = \frac{1}{N} ⟹ θ = 20.7 0^{\circ}; P_{k} = sin^{2} ((2 k + 1) θ)$
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%$
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.
  
  $k_{opt} = ⌊ \frac{π}{4} N ⌋ = ⌊ 2.221 ⌋ = 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 \sim \frac{N}{2} = 4 queries vs O (N) = 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.

$P_{k} = sin^{2} ((2 k + 1) θ) ROTATES : past k_{opt} it falls again$

Allikad (1)

The algorithm this tool steps through: L. K. Grover, "A fast quantum mechanical algorithm for database search." Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 212–219, 1996.

42Mathi meeskond · Uuendatud 2026-07-29

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

N = 4 - N=4 elementi — sihtmärgi leidmiseks piisab 1 Groveri iteratsioonist
N = 8 - N=8 elementi — optimaalne on ~2 iteratsiooni, klassikaline demosuurus
N = 16 - N=16 elementi — optimaalne on 3 iteratsiooni, O(√N) on näha
N = 32 - N=32 elementi — ~4 iteratsiooni, näitab ruutkiirendust