Kvantjuhuslik kõnd

Klassikaline vs kvant: sama kõnd, üllatavalt erinev levik

Näidisarvutus — Kvantjuhuslik kõnd

Kvant/klassikaline suhe	2.0775×
Kvanttipp	0.2816

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

Interaktiivse simulatsiooni laadimine...

Juhuslikest kõndidest kvantotsingusse 🖖

Kvantkõnni ruutkiirendus tuleneb interferentsist, mitte tõenäosusest. Igal sammul viib Hadamardi värav mündi superpositsiooni, mistõttu nihkeoperaator liigutab amplituudi samaaegselt vasakule ja paremale. Paljude sammude jooksul kustutab amplituud keskosas end ise — vasakule ja paremale liikuvad panused jõuavad kohale vastandfaasides —, samas kui amplituud ±N/√2 lähedal võimendub konstruktiivselt. Seetõttu on jaotuse tipud servades, mitte keskel. Sama mehhanism juhib Groveri otsingut (kõnd hüperkuubil) ja Childsi eksponentsiaalse kiirendusega graafiläbimist: kvantkõnnid jõuavad kaugete tippudeni palju kiiremini kui ükski difusioonile tuginev protsess suudaks.

difusioon versus ballistiline sprint 🖖

Juhuslik ekslemine on lihtsalt korduv mündivise: kull – samm paremale, kiri – samm vasakule. Klassikaliselt sulanduvad sammud kellukõveraks — pärast 100 viset satud harva rohkem kui umbes 10 positsiooni kaugusele algusest, sest hajuvus kasvab nagu √N. Vaheta münt kvantmündi vastu ja ekslejal ei keskmistu enam midagi: ta paiskub väljapoole ja jõuab samade 100 sammuga juba ~70 positsioonini. Füüsikud nimetavad seda ballistiliseks levikuks: see kasvab lineaarselt N-iga, mitte tema ruutjuurena.

kvantekslemine ei unusta kunagi 🖖

Klassikaline juhuslik ekslemine on Markovi protsess: see kaotab tasapisi jälje sellest, kust alustati, ja ainult lõppjaotuse põhjal ei saa alguspunkti taastada. Kvantekslemine on unitaarne, seega on iga samm täiesti pööratav. Lase täpne Hadamardi-ja-nihke jada tagurpidi käia ning kogu hajutatud amplituud koondub taas üheks teravikuks alguspunkti — infot ei lähe kaotsi ja ekslemisel pole ühtki tasakaalujaotust, kuhu laiali valguda. Difusioon kustutab mineviku; kvantekslemine üksnes peidab selle.

Ülesanne täielikult lahendatud

2 kõndija hajuvus 10 sammu jooksul 9 sammu
10 sammu, 2 kõndijat. Üks viskab igal sammul ausat münti ja liigub ±1. Teine alustab mündi olekus |0⟩ ning enne iga käiku rakendatakse selle mündile Hadamardi väravat. Arvuta mõlema hajumine täpselt ja leia seejärel, mitu sammu vajab klassikaline kõndija sama maa läbimiseks.
1. Klassikalised sammud on sõltumatud ja igaüks neist annab dispersiooniks täpselt 1, seega dispersioonid liituvad. See ainus rida ongi kogu klassikaline vastus — ja just seepärast kuvatakse ülemisel paneelil ruutjuurt, mitte simulatsiooni.
  
  $σ_{c}^{2} = 10 1 + 1 + \dots + 1 = 10 ⟹ σ_{c} = 10 = 3.1623$
2. Kvantkõndija ei vali kunagi haru. Igas punktis kantakse kaasas 2 amplituudi, üks kummagi mündi väärtuse kohta; Hadamard asendab need nende summa ja vahega, ning seejärel liigub oleku |0⟩ pool vasakule ja oleku |1⟩ pool paremale. Punkt võib saada panuse mõlemalt naabrilt, seega amplituudid liituvad — ja vahe võib tulla 0.
  
  $(a_{0}, a_{1})_{x} ⟶ \frac{a _{0} + a _{1}}{2} (1, 0)_{x - 1} + \frac{a _{0} - a _{1}}{2} (0, 1)_{x + 1}$
3. Alusta koordinaatide alguspunktist olekuga (1, 0) ning tee 2 sammu. Tõsta igalt sammult tegur 1/√2 ette, et amplituudid jääksid täisarvudeks; nõnda on pärast sammu n allolevad paarid jagatud väärtusega 2^n/2.
  
  $n = 1 : (1, 0)_{- 1}, (0, 1)_{+ 1} n = 2 : (1, 0)_{- 2}, (1, 1)_{0}, (0, - 1)_{+ 2}$
4. Sümmeetria kaob 3. sammul. Alguspunktis asuvas sõlmes on (1, 1): see saadab 1 + 1 = 2 vasakule ja 1 − 1 = 0 paremale. Hadamardi alumise rea miinusmärk on kustutanud selle sõlme kogu parempoolse panuse ning oleku x = −1 tõenäosus on nüüd 5 korda suurem kui oleku x = +1 tõenäosus.
  
  $n = 3 : (1, 0)_{- 3}, (2, 1)_{- 1}, (- 1, 0)_{+ 1}, (0, 1)_{+ 3} ⟹ p (- 1) = \frac{5}{8}, p (+ 1) = \frac{1}{8}$
5. Jatka arvutamist kuni 10. sammuni. Amplituudid on endiselt täisarvud jagatuna väärtusega 2⁵, seega on iga tõenäosus täisarv jagatuna 1024-ga — allolevad 11 lugejat on täpsed ning nende summa on 1024.
  
  $n = 10 : 1024 p (x) = 1, 82, 449, 64, 100, 72, 52, 64, 89, 50, 1 (x = - 10, - 8, \dots, + 10)$
6. Loe suurim lugeja otse loendist. See on 449 ja asub kohal x = −6, kaugele eemal nii alguspunktist kui ka kaugeimast servast.
  
  $x max p_{q} (x) = p_{q} (- 6) = \frac{449}{1024} = 0.4385$
7. Keskväärtus ei ole 0. |0⟩ on mündi see pool, mis liigub vasakule, ning juba 3. samm näitas, et see saab suurema osa, mistõttu kogu jaotus kaldub sinnapoole.
  
  $μ = x \sum x p (x) = - \frac{2512}{1024} = - 2.4531$
8. Dispersioon on ruutude keskväärtus miinus keskväärtuse ruut ning mõlemad summad tulevad samast 11 lugejast — uut teavet pole vaja.
  
  $σ_{q}^{2} = x \sum x^{2} p (x) - μ^{2} = \frac{30672}{1024} - 6.0177 = 23.935 ⟹ σ_{q} = 4.8924$
9. Jaga sammus 1 leitud klassikalise hajumisega.
  
  $\frac{σ _{q}}{σ _{c}} = \frac{4.8924}{3.1623} = 1.5471$
Vastus

σ_q = 4,8924 võrrelduna σ_c = 3,1623-ga — suhe 1,5471 — kusjuures kvanttipp on p_q(−6) = 0,4385. Tõlgenda see dispersioon nüüd sammude arvuna. Klassikalise kõndija hajumine on √M, seega väärtuse 4,8924 saavutamiseks on vaja M = σ_q² = 23,9, ümaralt 24 sammu: 2,4 korda rohkem tööd sama ulatuse saavutamiseks pärast 10 sammu. Klassikaline sammude arv on hajumiste suhte ruut ja see ongi oluline järeldus — 2× eelis hajumises on 4× eelis sammudes.

$M = σ_{q}^{2} = 23.9 \approx 24, \frac{M}{N} = (\frac{σ _{q}}{σ _{c}})^{2} = 1.547 1^{2} = 2.394$

Allikad (2)

Insight block 1 — the coined walk this tool steps through: Y. Aharonov, L. Davidovich and N. Zagury, "Quantum random walks." Physical Review A 48(2), 1687–1690, 1993.
And the exponential separation block 1 names: A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann and D. A. Spielman, "Exponential algorithmic speedup by a quantum walk." Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 59–68, 2003.

42Mathi meeskond · Uuendatud 2026-05-22

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

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

10 sammu - 10 sammu — asümmeetrilised kaksikhuiped juba nähtavad
30 sammu - 30 sammu — kvantlevik on klassikalisest märkimisväärselt laiem
50 sammu - 50 sammu — kvantlevik O(N) vs klassikaline O(√N)
Tasakaalus münt - 20 sammu, tasakaalustatud münt — sümmeetriline kahe tipuga jaotus