Algoritmul Deutsch-Jozsa

Algoritmul Deutsch-Jozsa este un algoritm cuantic determinist propus de David Deutsch și Richard Jozsa în 1992 și ulterior îmbunătățit de Richard Cleve, Artur Ekert, Chiara Macchiavello și Michele Mosca în 1998. ^[1] ^[2] Deși este un interes practic rar , este unul dintre primele exemple de algoritmi cuantici care este exponențial mai rapid decât orice algoritm determinist clasic. ^[3]

Afirmarea problemei

În problema Deutsch-Jozsa, este dată o cutie neagră, numită oracol care implementează o anumită funcție $f\colon \{0,1\}^{n}\rightarrow \{0,1\}$ ${\ displaystyle f \ colon \ {0,1 \} ^ {n} \ rightarrow \ {0,1 \}}$ ${\ displaystyle f \ colon \ {0,1 \} ^ {n} \ rightarrow \ {0,1 \}}$ . Funcția ia valori binare de n cifre și scoate 0 sau 1 pentru fiecare dintre aceste valori. Funcția este definită constantă (ieșirea este întotdeauna 0 sau întotdeauna 1) sau echilibrată (dă 1 pentru jumătate din intrări și 0 pentru cealaltă jumătate). Prin urmare, sarcina este de a determina dacă $f$ ${\ displaystyle f}$ $f$ este constantă sau echilibrată.

Motivație

Această problemă a fost concepută special pentru a fi ușoară pentru un algoritm cuantic și dificilă pentru orice algoritm determinist clasic. Motivația este de a arăta o problemă a cutiei negre care poate fi rezolvată eficient fără erori de către un computer cuantic, în timp ce un computer determinist clasic ar avea nevoie de un număr mare de apeluri către oracol pentru a o rezolva. În termeni formali, oferă un oracol pentru care EQP , clasa problemelor care pot fi rezolvate exact și în timp polinomial pe un computer cuantic, și P sunt diferite. ^[4]

Deoarece problema este ușor de rezolvat pentru un computer probabilistic clasic, nu există o separare a oracolelor cu BPP , clasa problemelor rezolvabile de eroare limitată în timp polinomial pe un computer clasic probabilistic. Un exemplu de problemă care oferă o separare a oracolelor între BQP și BPP este problema lui Simon .

Soluție clasică

Pentru un algoritm determinist convențional cu n număr de biți, vor fi necesari $2^{n-1}+1$ ${\ displaystyle 2 ^ {n-1} +1}$ ${\ displaystyle 2 ^ {n-1} +1}$ evaluări ale $f$ ${\ displaystyle f}$ $f$ în cel mai rău caz. Pentru a demonstra asta $f$ ${\ displaystyle f}$ $f$ este constantă, jumătate plus una dintre intrări trebuie calculate și ieșirile lor trebuie să fie identice (amintind că funcția este cu siguranță fie constantă, fie echilibrată). Cel mai bun caz implică 2 evaluări și apare atunci când funcția este echilibrată și cele două ieșiri sunt diferite. Pentru un algoritm convențional randomizat , $k$ ${\ displaystyle k}$ $k$ evaluările sunt suficiente pentru a produce răspunsul corect cu probabilitate mare (eșec cu probabilitate $\epsilon \leq 1/2^{k}$ ${\ displaystyle \ epsilon \ leq 1/2 ^ {k}}$ ${\ displaystyle \ epsilon \ leq 1/2 ^ {k}}$ unde este $k\geq 1$ ${\ displaystyle k \ geq 1}$ $k \ geq 1$ ).In orice caz, $k=2^{n-1}+1$ ${\ displaystyle k = 2 ^ {n-1} +1}$ ${\ displaystyle k = 2 ^ {n-1} +1}$ evaluările sunt întotdeauna necesare dacă căutați un răspuns cu siguranță corect. Algoritmul cuantic Deutsch-Jozsa oferă un răspuns cu siguranță corect după o singură evaluare a $f$ ${\ displaystyle f}$ $f$ .

Istorie

Algoritmul Deutsch - Jozsa generalizează o lucrare anterioară a lui David Deutsch (în 1985), care a furnizat o soluție pentru cazul simplu în care $n=1$ ${\ displaystyle n = 1}$ $n = 1$ . Mai exact, avem o funcție booleană a cărei intrare este de 1 bit, $f:\{0,1\}\rightarrow \{0,1\}$ ${\ displaystyle f: \ {0,1 \} \ rightarrow \ {0,1 \}}$ ${\ displaystyle f: \ {0,1 \} \ rightarrow \ {0,1 \}}$ și ne întrebăm dacă este constantă. ^[5]

Algoritmul propus inițial de Deutsch nu a fost, de fapt, determinist. A avut succes cu o șansă de 50%. În 1992, Deutsch și Jozsa au formulat un algoritm determinist care a generalizat la o funcție pe care o ia $n$ ${\ displaystyle n}$ $n$ bit, dar avea nevoie de două evaluări ale funcției în loc de una singură.

Cleve și colab. a adus îmbunătățiri suplimentare ^[2], ceea ce a condus la un algoritm determinist care avea nevoie doar de un singur apel de $f$ ${\ displaystyle f}$ $f$ . Cu toate acestea, acest algoritm se numește Deutsch - Jozsa în onoarea tehnicilor inovatoare pe care le-au folosit.

Algoritm

Pentru ca algoritmul să funcționeze, oracolul care calculează $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ din $X$ ${\ displaystyle x}$ $X$ nu trebuie să se prăbușească $X$ ${\ displaystyle x}$ $X$ . De asemenea, nu ar trebui să lăsați copii ale $X$ ${\ displaystyle x}$ $X$ după chemarea oracolului.

Circuitul cuantic al algoritmului Deutsch-Jozsa

Algoritmul începe cu starea a $n+1$ ${\ displaystyle n + 1}$ $n + 1$ pic $|0\rangle ^{\otimes n}|1\rangle$ ${\ displaystyle | 0 \ rangle ^ {\ otimes n} | 1 \ rangle}$ ${\ displaystyle | 0 \ rangle ^ {\ otimes n} | 1 \ rangle}$ : primii n biți sunt în stare $|0\rangle$ ${\ displaystyle | 0 \ rangle}$ ${\ displaystyle | 0 \ rangle}$ iar ultima este în $|1\rangle$ ${\ displaystyle | 1 \ rangle}$ ${\ displaystyle | 1 \ rangle}$ . O poartă Hadamard este aplicată fiecărui bit pentru a obține starea

{\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle )

{\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n + 1}}}} sum _ {x = 0} ^ {2 ^ {n} -1} | x \ rangle (| 0 \ rangle - | 1 \ rangle)}

{\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n + 1}}}} sum _ {x = 0} ^ {2 ^ {n} -1} | x \ rangle (| 0 \ rangle - | 1 \ rangle)}

.

Acum funcția se aplică $f$ ${\ displaystyle f}$ $f$ implementat ca un oracol. Oracolul mapează starea $|x\rangle |y\rangle$ ${\ displaystyle | x \ rangle | y \ rangle}$ ${\ displaystyle | x \ rangle | y \ rangle}$ la $|x\rangle |y\oplus f(x)\rangle$ ${\ displaystyle | x \ rangle | y \ oplus f (x) \ rangle}$ ${\ displaystyle | x \ rangle | y \ oplus f (x) \ rangle}$ , unde este $\oplus$ ${\ displaystyle \ oplus}$ $\ oplus$ este adaosul modulo 2. Aplicarea oracolului dă

{\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|f(x)\rangle -|1\oplus f(x)\rangle )

{\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n + 1}}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} | x \ rangle (| f (x ) \ rangle - | 1 \ oplus f (x) \ rangle)}

{\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n + 1}}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} | x \ rangle (| f (x ) \ rangle - | 1 \ oplus f (x) \ rangle)}

.

Pentru fiecare $x,f(x)$ ${\ displaystyle x, f (x)}$ ${\ displaystyle x, f (x)}$ este 0 sau 1. Având în vedere aceste două posibilități, statutul este egal cu

{\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle )

{\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n + 1}}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x )} | x \ rangle (| 0 \ rangle - | 1 \ rangle)}

{\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n + 1}}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x )} | x \ rangle (| 0 \ rangle - | 1 \ rangle)}

.

În acest moment ultimul qubit ${\frac {|0\rangle -|1\rangle }{\sqrt {2}}}$ ${\ displaystyle {\ frac {| 0 \ rangle - | 1 \ rangle} {\ sqrt {2}}}}$ ${\ displaystyle {\ frac {| 0 \ rangle - | 1 \ rangle} {\ sqrt {2}}}}$ poate fi ignorat și, prin urmare, rămâne:

{\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle

{\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n}}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x)} | x \ rangle}

{\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n}}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x)} | x \ rangle}

.

Pentru a obține o poartă Hadamard se aplică fiecărui qubit

{\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{y=0}^{2^{n}-1}(-1)^{x\cdot y}|y\rangle \right]={\frac {1}{2^{n}}}\sum _{y=0}^{2^{n}-1}\left[\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle

{\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n}}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x)} \ left [{\ frac {1} {\ sqrt {2 ^ {n}}}} \ sum _ {y = 0} ^ {2 ^ {n} -1} (- 1) ^ {x \ cdot y} | y \ rangle \ right] = {\ frac {1} {2 ^ {n}}} \ sum _ {y = 0} ^ {2 ^ {n} -1} \ left [\ sum _ {x = 0 } ^ {2 ^ {n} -1} (- 1) ^ {f (x)} (- 1) ^ {x \ cdot y} \ right] | y \ rangle}

{\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n}}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x)} \ left [{\ frac {1} {\ sqrt {2 ^ {n}}}} \ sum _ {y = 0} ^ {2 ^ {n} -1} (- 1) ^ {x \ cdot y} | y \ rangle \ right] = {\ frac {1} {2 ^ {n}}} \ sum _ {y = 0} ^ {2 ^ {n} -1} \ left [\ sum _ {x = 0 } ^ {2 ^ {n} -1} (- 1) ^ {f (x)} (- 1) ^ {x \ cdot y} \ right] | y \ rangle}

unde este $x\cdot y=x_{0}y_{0}\oplus x_{1}y_{1}\oplus \cdots \oplus x_{n-1}y_{n-1}$ ${\ displaystyle x \ cdot y = x_ {0} y_ {0} \ oplus x_ {1} y_ {1} \ oplus \ cdots \ oplus x_ {n-1} y_ {n-1}}$ ${\ displaystyle x \ cdot y = x_ {0} y_ {0} \ oplus x_ {1} y_ {1} \ oplus \ cdots \ oplus x_ {n-1} y_ {n-1}}$ este suma este produsul bit-to-bit.

În cele din urmă, luați în considerare probabilitatea de măsurare $|0\rangle ^{\otimes n}$ ${\ displaystyle | 0 \ rangle ^ {\ otimes n}}$ ${\ displaystyle | 0 \ rangle ^ {\ otimes n}}$ ,

{\bigg |}{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{\bigg |}^{2}

{\ displaystyle {\ bigg |} {\ frac {1} {2 ^ {n}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x) } {\ bigg |} ^ {2}}

{\ displaystyle {\ bigg |} {\ frac {1} {2 ^ {n}}} \ sum _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x) } {\ bigg |} ^ {2}}

care este echivalent cu 1 dacă $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ este constantă (interferență constructivă) și 0 dacă $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ este echilibrat (interferență distructivă). Cu alte cuvinte, măsura va da $|0\rangle ^{\otimes n}$ ${\ displaystyle | 0 \ rangle ^ {\ otimes n}}$ ${\ displaystyle | 0 \ rangle ^ {\ otimes n}}$ (adică toate zero) dacă $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ este constantă și va da oricărei alte stări dacă $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ este echilibrat.

Algoritmul lui Deutsch

Algoritmul lui Deutsch este un caz special al acestui algoritm. Starea trebuie verificată $f(0)=f(1)$ ${\ displaystyle f (0) = f (1)}$ $f (0) = f (1)$ . Este echivalent cu verificarea $f(0)\oplus f(1)$ ${\ displaystyle f (0) \ oplus f (1)}$ ${\ displaystyle f (0) \ oplus f (1)}$ (unde este $\oplus$ ${\ displaystyle \ oplus}$ $\ oplus$ este adaosul modulo 2, care poate fi văzut ca o poartă cuantică XOR implementată ca o poartă NU controlată ), dacă suma este zero, atunci $f$ ${\ displaystyle f}$ $f$ este constant, altfel nu este.

Începe cu statul $|0\rangle |1\rangle$ ${\ displaystyle | 0 \ rangle | 1 \ rangle}$ ${\ displaystyle | 0 \ rangle | 1 \ rangle}$ iar la fiecare qubit se aplică o poartă Hadamard . Asta da

{\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).

{\ displaystyle {\ frac {1} {2}} (| 0 \ rangle + | 1 \ rangle) (| 0 \ rangle - | 1 \ rangle).}

{\ displaystyle {\ frac {1} {2}} (| 0 \ rangle + | 1 \ rangle) (| 0 \ rangle - | 1 \ rangle).}

Se aplică oracolul care se aplică $|x\rangle |y\rangle$ ${\ displaystyle | x \ rangle | y \ rangle}$ ${\ displaystyle | x \ rangle | y \ rangle}$ în $|x\rangle |f(x)\oplus y\rangle$ ${\ displaystyle | x \ rangle | f (x) \ oplus y \ rangle}$ ${\ displaystyle | x \ rangle | f (x) \ oplus y \ rangle}$ . Aplicarea acestei funcții la starea actuală produce

{\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))

{\ displaystyle {\ frac {1} {2}} (| 0 \ rangle (| f (0) \ oplus 0 \ rangle - | f (0) \ oplus 1 \ rangle) + | 1 \ rangle (| f ( 1) \ oplus 0 \ rangle - | f (1) \ oplus 1 \ rangle))}

{\ displaystyle {\ frac {1} {2}} (| 0 \ rangle (| f (0) \ oplus 0 \ rangle - | f (0) \ oplus 1 \ rangle) + | 1 \ rangle (| f ( 1) \ oplus 0 \ rangle - | f (1) \ oplus 1 \ rangle))}

={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))

{\ displaystyle = {\ frac {1} {2}} ((- 1) ^ {f (0)} | 0 \ rangle (| 0 \ rangle - | 1 \ rangle) + (- 1) ^ {f ( 1)} | 1 \ rangle (| 0 \ rangle - | 1 \ rangle))}

{\ displaystyle = {\ frac {1} {2}} ((- 1) ^ {f (0)} | 0 \ rangle (| 0 \ rangle - | 1 \ rangle) + (- 1) ^ {f ( 1)} | 1 \ rangle (| 0 \ rangle - | 1 \ rangle))}

=(-1)^{f(0)}{\frac {1}{2}}\left(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle \right)(|0\rangle -|1\rangle ).

{\ displaystyle = (- 1) ^ {f (0)} {\ frac {1} {2}} \ left (| 0 \ rangle + (- 1) ^ {f (0) \ oplus f (1)} | 1 \ rangle \ right) (| 0 \ rangle - | 1 \ rangle).}

{\ displaystyle = (- 1) ^ {f (0)} {\ frac {1} {2}} \ left (| 0 \ rangle + (- 1) ^ {f (0) \ oplus f (1)} | 1 \ rangle \ right) (| 0 \ rangle - | 1 \ rangle).}

Prin ignorarea ultimului bit și a fazei globale, se obține starea

{\frac {1}{\sqrt {2}}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle ).

{\ displaystyle {\ frac {1} {\ sqrt {2}}} (| 0 \ rangle + (- 1) ^ {f (0) \ oplus f (1)} | 1 \ rangle).}

{\ displaystyle {\ frac {1} {\ sqrt {2}}} (| 0 \ rangle + (- 1) ^ {f (0) \ oplus f (1)} | 1 \ rangle).}

Aplicarea din nou a porții Hadamard este obținută

{\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )

{\ displaystyle {\ frac {1} {2}} (| 0 \ rangle + | 1 \ rangle + (- 1) ^ {f (0) \ oplus f (1)} | 0 \ rangle - (- 1) ^ {f (0) \ oplus f (1)} | 1 \ rangle)}

{\ displaystyle {\ frac {1} {2}} (| 0 \ rangle + | 1 \ rangle + (- 1) ^ {f (0) \ oplus f (1)} | 0 \ rangle - (- 1) ^ {f (0) \ oplus f (1)} | 1 \ rangle)}

={\frac {1}{2}}((1+(-1)^{f(0)\oplus f(1)})|0\rangle +(1-(-1)^{f(0)\oplus f(1)})|1\rangle ).

{\ displaystyle = {\ frac {1} {2}} ((1 + (- 1) ^ {f (0) \ oplus f (1)}) | 0 \ rangle + (1 - (- 1) ^ { f (0) \ oplus f (1)}) | 1 \ rangle).}

{\ displaystyle = {\ frac {1} {2}} ((1 + (- 1) ^ {f (0) \ oplus f (1)}) | 0 \ rangle + (1 - (- 1) ^ { f (0) \ oplus f (1)}) | 1 \ rangle).}

$f(0)\oplus f(1)=0$ ${\ displaystyle f (0) \ oplus f (1) = 0}$ ${\ displaystyle f (0) \ oplus f (1) = 0}$ dacă și numai se măsoară $|0\rangle$ ${\ displaystyle | 0 \ rangle}$ $| 0 \ rangle$ Și $f(0)\oplus f(1)=1$ ${\ displaystyle f (0) \ oplus f (1) = 1}$ ${\ displaystyle f (0) \ oplus f (1) = 1}$ dacă și numai dacă măsoară $|1\rangle$ ${\ displaystyle | 1 \ rangle}$ $| 1 \ rangle$ . Deci știți sigur dacă $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ este constantă sau echilibrată.