Deutsch-Jozsa-algoritmi
Deutsch-Józsa algoritmi on kvantti -algoritmi , ehdottama David Deutsch ja Richard Józsa (fi) vuonna 1992 ja parannusta R. Cleve, A. Ekert, C. Macchiavello M. Mosca vuonna 1998 . Vaikka se ei ole kovin käytännöllisesti kiinnostava, se on yksi ensimmäisistä kvanttialgoritmeista, joka on tehokkaampi kuin klassinen algoritmi.
Klassinen ongelma ja ratkaisut
Deutsch-Jozsa -ongelman tapauksessa meillä on kvanttimusta ruutu, joka tunnetaan nimellä oraakkeli, joka toteuttaa matemaattisen funktion . Tiedämme, että tämä toiminto on joko vakio (lähtö on 0 tai 1 kaikille tuloille) tai tasapainotettu (lähtö on 0 puolessa tapauksista, 1 muissa tapauksissa). Ongelman tarkoitus on, onko funktio vakio vai tasapainotettu oraakkelin avulla.
f:{0,1}ei→{0,1}{\ displaystyle f: \ {0,1 \} ^ {n} \ oikeanpuoleinen \ {0,1 \}}
Deterministinen ratkaisu
Jos käytetään klassista ja determinististä algoritmia , ratkaisun löytäminen vaatii matemaattisen funktion arviointia pahimmassa tapauksessa, kuten alla selitetään.
2ei-1+1{\ displaystyle 2 ^ {n-1} +1}f{\ displaystyle f}
Toiminto hyväksyy tulot että me nimeämme kanssa .
2ei{\ displaystyle 2 ^ {n}}Ei{\ displaystyle E_ {i}}i∈[1;2ei]{\ displaystyle i \ sisään [1; 2 ^ {n}]}
Toiminnon testaaminen yhdessä tulotapauksessa (esimerkiksi ) ei tietenkään salli päätelmää. Mutta tämä antaa ensimmäisen tuloksen, joka toimii viitteenä.
f{\ displaystyle f}E1{\ displaystyle E_ {1}}Rref{\ displaystyle R_ {ref}}
Nyt lasketaan .
f(E2){\ displaystyle f (E_ {2})}
Parhaassa tapauksessa tulos on erilainen kuin ja voimme heti päätellä, että toiminto on tasapainoinen, ilman että tarvitsee mennä pidemmälle.
Rref{\ displaystyle R_ {ref}}
Muuten emme voi tehdä mitään johtopäätöstä ja se on syytä laskea . Ja niin edelleen...
f(E3){\ displaystyle f (E_ {3})}
Pahimmassa tapauksessa pääsemme pisteeseen, jossa puolet mahdollisista syöttöarvoista on testattu ja ne kaikki palauttivat tuloksen . Emme voi vielä päätellä, koska tämä identtisten tulosten osuus on mahdollista, että toiminto on vakio tai tasapainoinen!
Rref{\ displaystyle R_ {ref}}f{\ displaystyle f}
Toisaalta testistä seuraavalle tuloarvolle:
- Jos tulos on identtinen, on varmaa, että funktio on vakioRref{\ displaystyle R_ {ref}}f{\ displaystyle f}
- Jos tulos on erilainen kuin silloin, on varmaa, että toiminto on tasapainossaRref{\ displaystyle R_ {ref}}f{\ displaystyle f}
Siksi näemme, että pahimmassa tapauksessa suoritettavien arviointien määrä on "puolet mahdollisista tapauksista plus yksi", ts .
f{\ displaystyle f}2ei-1+1{\ displaystyle 2 ^ {n-1} +1}
Todennäköinen ratkaisu
Todennäköistä algoritmia käytettäessä vakiomäärä arviointeja on riittävä oikean vastauksen löytämiseksi suurella todennäköisyydellä, mutta arvioinnit ovat aina välttämättömiä, jotta vastaus olisi oikea todennäköisyydellä 1.
2ei-1+1{\ displaystyle 2 ^ {n-1} +1}
Deutsch-Jozsa-algoritmi
Deutsch-Jozsa-kvanttialgoritmi antaa mahdollisuuden löytää aina oikea vastaus yhdellä arvioinnilla .
f{\ displaystyle f}
Deutsch-algoritmi erikoistapausta varten
Tavoitteena on testata kunto ; tämä vastaa tarkistamista . Jos se on nolla, on vakio, muuten on tasapainossa.
f(0)=f(1){\ displaystyle f (0) = f (1)}f(0)⊕f(1){\ displaystyle f (0) \ oplus f (1)}f{\ displaystyle f}f{\ displaystyle f}
Algoritmi alkaa kahdella tilassa olevalla kvitillä . Hadamard-muunnoksen ensin kuhunkin qubit. Tämä antaa
|0⟩|1⟩{\ displaystyle | 0 \ rangle | 1 \ rangle}
12(|0⟩+|1⟩)(|0⟩-|1⟩).{\ displaystyle {\ frac {1} {2}} (| 0 \ rangle + | 1 \ rangle) (| 0 \ rangle - | 1 \ rangle).}Funktion kvanttitoteutus (oraakkeli) antaa mahdollisuuden siirtyä kohtaan . Soveltamalla tätä toimintoa valtioomme saamme
f{\ displaystyle f}|x⟩|y⟩{\ displaystyle | x \ rangle | y \ rangle}|x⟩|f(x)⊕y⟩{\ displaystyle | x \ rangle | f (x) \ oplus y \ rangle}
12{|0⟩(|f(0)⊕0⟩-|f(0)⊕1⟩)+|1⟩(|f(1)⊕0⟩-|f(1)⊕1⟩)}{\ displaystyle {\ frac {1} {2}} {\ bigg \ {} | 0 \ rangle {\ bigg (} | f (0) \ oplus 0 \ rangle - | f (0) \ oplus 1 \ rangle { \ bigg)} + | 1 \ rangle {\ bigg (} | f (1) \ oplus 0 \ rangle - | f (1) \ oplus 1 \ rangle {\ bigg)} {\ bigg \}}}
=12{(-1)f(0)|0⟩(|0⟩-|1⟩)+(-1)f(1)|1⟩(|0⟩-|1⟩)}{\ displaystyle = {\ frac {1} {2}} {\ bigg \ {} (- 1) ^ {f (0)} | 0 \ rangle {\ bigg (} | 0 \ rangle - | 1 \ rangle { \ bigg)} + (- 1) ^ {f (1)} | 1 \ rangle {\ bigg (} | 0 \ rangle - | 1 \ rangle {\ bigg)} {\ bigg \}}}
=(-1)f(0)12(|0⟩+(-1)f(0)⊕f(1)|1⟩)(|0⟩-|1⟩).{\ displaystyle = (- 1) ^ {f (0)} {\ frac {1} {2}} {\ bigg (} | 0 \ rangle + (- 1) ^ {f (0) \ oplus f (1 )} | 1 \ rangle {\ bigg)} {\ bigg (} | 0 \ rangle - | 1 \ rangle {\ bigg)}.}
Ohitamme viimeisen bitin ja globaalin vaiheen, niin meillä on valtio
12(|0⟩+(-1)f(0)⊕f(1)|1⟩).{\ displaystyle {\ frac {1} {\ sqrt {2}}} {\ bigg (} | 0 \ rangle + (- 1) ^ {f (0) \ oplus f (1)} | 1 \ rangle {\ bigg)}.}Soveltamalla tähän tilaan satunnainen muunnos saamme
12(|0⟩+|1⟩+((-1)f(0)⊕f(1))|0⟩-((-1)f(0)⊕f(1))|1⟩){\ displaystyle {\ frac {1} {2}} {\ bigg (} | 0 \ rangle + | 1 \ rangle + {\ big (} (- 1) ^ {f (0) \ oplus f (1)} {\ big)} | 0 \ rangle - {\ big (} (- 1) ^ {f (0) \ oplus f (1)} {\ big)} | 1 \ rangle {\ bigg)}}
=12{(1+(-1)f(0)⊕f(1))|0⟩+(1-(-1)f(0)⊕f(1))|1⟩}.{\ displaystyle = {\ frac {1} {2}} {\ bigg \ {} {\ bigg (} 1 + (- 1) ^ {f (0) \ oplus f (1)} {\ bigg)} | 0 \ rangle + {\ bigg (} 1 - (- 1) ^ {f (0) \ oplus f (1)} {\ bigg)} | 1 \ rangle {\ bigg \}}.}
f(0)⊕f(1)=0{\ displaystyle f (0) \ oplus f (1) = 0}vain ja vain, jos havaitsemme nollan. Joten funktio on vakio vain ja vain, jos mitataan nolla.
Deutsch-Jozsa-algoritmi
Aloitetaan tilasta n + 1 kubitti . Ensimmäiset kubitit ovat kaikki tilassa ja viimeinen qubit on tilassa . Sitten sovellamme Hadamard-muunnosta jokaiselle kubitille saadaksesi
|0⟩⊗ei|1⟩{\ displaystyle | 0 \ rangle ^ {\ otimes n} | 1 \ rangle}ei{\ displaystyle n}|0⟩{\ displaystyle | 0 \ rangle}|1⟩{\ displaystyle | 1 \ rangle}
12ei+1∑x=02ei-1|x⟩(|0⟩-|1⟩){\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n + 1}}}} \ summa _ {x = 0} ^ {2 ^ {n} -1} | x \ rangle (| 0 \ rangle - | 1 \ etäisyys)}.
Meillä on funktio toteutettu kvanttinaakelin muodossa. Oraakkeli muuttuu valtion osaksi . Kvantti-oraakelin käyttö siis antaa
f{\ displaystyle f}|x⟩|y⟩{\ displaystyle | x \ rangle | y \ rangle}|x⟩|y⊕f(x)⟩{\ displaystyle | x \ rangle | y \ oplus f (x) \ rangle}
12ei+1∑x=02ei-1|x⟩(|f(x)⟩-|1⊕f(x)⟩){\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n + 1}}}} \ summa _ {x = 0} ^ {2 ^ {n} -1} | x \ rangle (| f (x ) \ rangle - | 1 \ oplus f (x) \ rangle)}.
Kunkin , on tai . Näiden kahden mahdollisuuden nopea tarkastus jättää meidät
x{\ displaystyle x}f(x){\ displaystyle f (x)}0{\ displaystyle 0}1{\ displaystyle 1}
12ei+1∑x=02ei-1(-1)f(x)|x⟩(|0⟩-|1⟩){\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n + 1}}}} \ summa _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x )} | x \ rangle (| 0 \ rangle - | 1 \ rangle)}.
Tässä vaiheessa viimeinen qubit voidaan ohittaa. Sitten sovellamme Hadamard-muunnosta uudelleen kaikkiin jäljellä oleviin lajeihin saadaksesi
12ei∑x=02ei-1(-1)f(x)∑y=02ei-1(-1)x⋅y|y⟩=12ei∑y=02ei-1[∑x=02ei-1(-1)f(x)(-1)x⋅y]|y⟩{\ displaystyle {\ frac {1} {2 ^ {n}}} \ summa _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x)} \ summa _ { y = 0} ^ {2 ^ {n} -1} (- 1) ^ {x \ cdot y} | y \ rangle = {\ frac {1} {2 ^ {n}}} \ summa _ {y = 0} ^ {2 ^ {n} -1} \ vasemmalle [\ sum _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x)} (- 1) ^ { x \ cdot y} \ oikea] | y \ rangle}missä on bitti-bitti-tuotteen summa.
x⋅y=x0y0⊕x1y1⊕⋯⊕xei-1yei-1{\ displaystyle x \ cdot y = x_ {0} y_ {0} \ oplus x_ {1} y_ {1} \ oplus \ cdots \ oplus x_ {n-1} y_ {n-1}}
Lopuksi tutkitaan mittaamisen todennäköisyyttä ,
|0⟩⊗ei{\ displaystyle | 0 \ rangle ^ {\ otimes n}}
|12ei∑x=02ei-1(-1)f(x)|2{\ displaystyle {\ bigg |} {\ frac {1} {2 ^ {n}}} \ summa _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x) } {\ bigg |} ^ {2}}joka on arvoltaan 1, jos se on vakio ( rakentava häiriö ) ja 0, jos se on tasapainossa ( tuhoava häiriö ).
f(x){\ displaystyle f (x)}f(x){\ displaystyle f (x)}
Historia
Algoritmi perustuu David Deutschin työhön vuodelta 1985 , joka koskee tapausta . Kysymys oli, oliko Boolen funktio vakio.
ei=1{\ displaystyle n = 1}f:{0,1}→{0,1}{\ displaystyle f: \ {0,1 \} \ oikealle {{0,1 \}}
Vuonna 1992 ajatus yleistettiin, jotta sitä voidaan soveltaa useisiin tulobitteihin ja tietää onko toiminto vakio vai tasapainoinen.
ei{\ displaystyle n}
Deutschin algoritmi ei ollut alun perin deterministinen. Algoritmi palautti oikean vastauksen todennäköisyydellä 50%. Alkuperäinen Deutsch-Jozsa -algoritmi oli deterministinen, mutta toisin kuin Deutschin algoritmi, se vaati kaksi funktion arviointia.
Cleve et ai. On tehnyt useita parannuksia Deutsch-Jozsa -algoritmiin, mikä on johtanut deterministiseen algoritmiin, joka vaatii vain yhden funktion arvioinnin . Tätä algoritmia kutsutaan Deutsch-Joszan algoritmiksi käytettyjen tekniikoiden tärkeyden kunniaksi.
f{\ displaystyle f}
Deutsch-Józsa algoritmi toimi inspiraation Shor ja Grover algoritmeja, kaksi tärkeintä kvanttialgoritmi.
Viitteet
-
(en) David Deutsch ja Richard Jozsa , ” Ongelmien nopeat ratkaisut kvanttilaskennalla ” , Proceedings of the Royal Society of London A , voi. 439,
1992, s. 553.
-
(sisään) R. Cleve, A. Ekert, C. Macchiavello ja Mr. Mosca, " Quantum algorithms revisited " , Proceedings of the Royal Society of London A , voi. 454,
1998, s. 339-354 ( lue verkossa [PDF] ).
-
(in) David Deutsch , " The Church-Turing -periaate ja yleinen kvanttitietokone " , Proceedings of the Royal Society of London A , voi. 400,
1985, s. 97 ( lue verkossa [PDF] ).
-
(in) Peter W. Shor, " algoritmit Kvanttilaskenta: Diskreetit logaritmit ja Factoring " , IEEE Symposium Foundations of Computer Science ,
1994, s. 124-134 ( lue verkossa [PDF] ).
-
(sisään) Lov K. Grover, " Nopea kvanttimekaaninen algoritmi tietokantahakua varten " , Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing ,
1996, s. 212-219 ( lue verkossa [PDF] ).
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">