Groveri otsingualgoritm
Leidke nõel heinakuhjast √N sammu asemel N
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.