Problema lui Simon

În teoria complexității de calcul și în calculul cuantic , problema Simon este o problemă de calcul care poate fi rezolvată într-un mod exponențial mai rapid pe un computer cuantic decât un computer clasic (sau tradițional). Problema lui Simon încorporează utilizarea unei cutii negre. Problemele cu cutia neagră oferă algoritmilor cuantici un avantaj față de algoritmii clasici.

Problema în sine are un interes practic redus, deoarece există puține situații realiste în care problema lui Simon trebuie rezolvată. Cu toate acestea, problema este importantă, deoarece se poate demonstra că un algoritm cuantic poate rezolva această problemă atât de exponențial mai rapid decât orice algoritm clasic cunoscut. Acesta este primul exemplu de problemă de calcul care poate fi rezolvată în timp polinomial pe un computer cuantic.

Problema a fost creată de Daniel Simon în 1994. Simon a arătat un algoritm cuantic , adesea a spus algoritmului Simon, care rezolvă problema exponențial necesitând mai puțin timp de calcul (sau mai precis, apeluri) decât cel mai bun algoritm clasic. În algoritmul lui Simon este necesar să efectuați un număr liniar de apeluri, în timp ce algoritmul clasic are nevoie de un număr exponențial. Această problemă oferă o separare oracolă între clasele de complexitate BPP și BQP , spre deosebire de data separării de algoritmul ' Deutsch-Jozsa , care separă P și EQP. Separarea este exponențială (în raport cu un oracol) între complexitatea clasică și cea cuantică.

Algoritmul Simon a fost, de asemenea, inspirația pentru algoritmul lui Shor . Ambele probleme sunt cazuri particulare ale problemei subgrupului ascuns abelian, dintre care se cunosc algoritmi cuantici eficienți.

Descrierea problemei

Ambele au o funcție (implementată de o cutie neagră sau oracol) $f:\{0,1\}^{n}\rightarrow \{0,1\}^{n}$ ${\ displaystyle f: \ {0,1 \} ^ {n} \ rightarrow \ {0,1 \} ^ {n}}$ ${\ displaystyle f: \ {0,1 \} ^ {n} \ rightarrow \ {0,1 \} ^ {n}}$ , care se bucură de proprietate pentru unii $s\in \{0,1\}^{n}$ ${\ displaystyle s \ in \ {0,1 \} ^ {n}}$ ${\ displaystyle s \ in \ {0,1 \} ^ {n}}$ și pentru fiecare $x,y\in \{0,1\}^{n}$ ${\ displaystyle x, y \ in \ {0,1 \} ^ {n}}$ ${\ displaystyle x, y \ in \ {0,1 \} ^ {n}}$ ,

f(x)=f(y)

{\ displaystyle f (x) = f (y)}

{\ displaystyle f (x) = f (y)}

dacă și numai dacă

x\oplus y\in \{0^{n},s\}

{\ displaystyle x \ oplus y \ in \ {0 ^ {n}, s \}}

{\ displaystyle x \ oplus y \ in \ {0 ^ {n}, s \}}

sau

{\displaystyle x=y\oplus s}

{\ displaystyle {\ displaystyle x = y \ oplus s}}

{\ displaystyle {\ displaystyle x = y \ oplus s}}

Scopul este de a identifica dacă să identifice dacă $s=0^{n}$ ${\ displaystyle s = 0 ^ {n}}$ ${\ displaystyle s = 0 ^ {n}}$ sau $s\neq 0^{n}$ ${\ displaystyle s \ neq 0 ^ {n}}$ ${\ displaystyle s \ neq 0 ^ {n}}$ apelând f (x).

Aici, $s=0^{n}$ ${\ displaystyle s = 0 ^ {n}}$ ${\ displaystyle s = 0 ^ {n}}$ clasificarea unei funcții de injecție (unu-la-unu). Dacă în schimb $s\neq 0^{n}$ ${\ displaystyle s \ neq 0 ^ {n}}$ ${\ displaystyle s \ neq 0 ^ {n}}$ , funcția este două-la-unu astfel încât ${\displaystyle x\oplus y\in \{0^{n},s\}}$ ${\ displaystyle {\ displaystyle x \ oplus y \ in \ {0 ^ {n}, s \}}}$ ${\ displaystyle {\ displaystyle x \ oplus y \ in \ {0 ^ {n}, s \}}}$

Cu alte cuvinte, $f$ ${\ displaystyle f}$ $f$ este o funcție două la unu astfel încât $f(x)=f(x\oplus s)$ ${\ displaystyle f (x) = f (x \ oplus s)}$ ${\ displaystyle f (x) = f (x \ oplus s)}$ , pentru fiecare $x\in \{0,1\}^{n}$ ${\ displaystyle x \ in \ {0,1 \} ^ {n}}$ ${\ displaystyle x \ in \ {0,1 \} ^ {n}}$ unde este $s\in \{0,1\}^{n}$ ${\ displaystyle s \ in \ {0,1 \} ^ {n}}$ ${\ displaystyle s \ in \ {0,1 \} ^ {n}}$ este necunoscut.

Domeniul de aplicare

Scopul problemei este de a reduce numărul de apeluri către o casetă neagră pentru a determina s atât de exponențial de repede.

Exemplu

De exemplu, dacă $n=3$ ${\ displaystyle n = 3}$ $n = 3$ , atunci următoarea funcție este un exemplu de funcție care satisface proprietatea deja menționată:

$X$ ${\ displaystyle x}$ $X$	$f(x)$ ${\ displaystyle f (x)}$ $f (x)$
000	101
001	010
010	000
011	110
100	000
101	110
110	101
111	010

În acest caz aveți soluția $s=110$ ${\ displaystyle s = 110}$ ${\ displaystyle s = 110}$ . Se poate verifica cu ușurință că fiecare ieșire a $f$ ${\ displaystyle f}$ $f$ Apare de două ori și că produsul XOR în biți între cele două șiruri corespunzătoare oricărei ieșiri de intrare este egal cu $s=110$ ${\ displaystyle s = 110}$ ${\ displaystyle s = 110}$ .

De exemplu, șirurile de intrare $010$ ${\ displaystyle 010}$ ${\ displaystyle 010}$ Și $100$ ${\ displaystyle 100}$ $100$ ambele sunt mapate (din $f$ ${\ displaystyle f}$ $f$ ) la aceeași ieșire $000$ ${\ displaystyle 000}$ ${\ displaystyle 000}$ , adică $f(010)=000$ ${\ displaystyle f (010) = 000}$ ${\ displaystyle f (010) = 000}$ Și $f(100)=000$ ${\ displaystyle f (100) = 000}$ ${\ displaystyle f (100) = 000}$ . Dacă aplicați XOR la 010 și 100 obțineți 110, adică $010\oplus 100=110=s.$ ${\ displaystyle 010 \ oplus 100 = 110 = s.}$ ${\ displaystyle 010 \ oplus 100 = 110 = s.}$ Șirul $s=110$ ${\ displaystyle s = 110}$ ${\ displaystyle s = 110}$ poate fi, de asemenea, verificat folosind șirurile de intrare 001 și 111, care sunt mapate (de la f) la același șir de intrare 010. Chiar dacă aveți XOR 001 și 111, obțineți 110, adică $001\oplus 111=110=s$ ${\ displaystyle 001 \ oplus 111 = 110 = s}$ ${\ displaystyle 001 \ oplus 111 = 110 = s}$ . Aceasta oferă aceeași soluție $s=110$ ${\ displaystyle s = 110}$ ${\ displaystyle s = 110}$ rezolvat primul.

În acest exemplu, funcția este de fapt două-la-unu unde ${\displaystyle s\neq 0^{n}}$ ${\ displaystyle {\ displaystyle s \ neq 0 ^ {n}}}$ ${\ displaystyle {\ displaystyle s \ neq 0 ^ {n}}}$ .

De cand $x_{2}=s\oplus x_{1}$ ${\ displaystyle x_ {2} = s \ oplus x_ {1}}$ ${\ displaystyle x_ {2} = s \ oplus x_ {1}}$ , puteți rescrie coeficientul $(-1)^{x_{1}\cdot y}+(-1)^{x_{2}\cdot y}$ ${\ displaystyle (-1) ^ {x_ {1} \ cdot y} + (- 1) ^ {x_ {2} \ cdot y}}$ ${\ displaystyle (-1) ^ {x_ {1} \ cdot y} + (- 1) ^ {x_ {2} \ cdot y}}$ după cum urmează:

Dificultatea problemei

Intuitiv, aceasta este o problemă foarte dificil de rezolvat într-un mod „clasic”. Intuiția din spatele dificultății este destul de simplă: dacă doriți să rezolvați problema clasic, trebuie să găsiți două intrări diferite $X$ ${\ displaystyle x}$ $X$ Și $y$ ${\ displaystyle y}$ $y$ pentru care $f(x)=f(y)$ ${\ displaystyle f (x) = f (y)}$ ${\ displaystyle f (x) = f (y)}$ . Nu există neapărat o structură în funcție $f$ ${\ displaystyle f}$ $f$ ceea ce ar putea ajuta la găsirea a două astfel de intrări: mai precis, este posibil să descoperiți ceva $f$ ${\ displaystyle f}$ $f$ (sau ce face) numai atunci când, pentru două intrări diferite, obțineți aceeași ieșire. În orice caz, ar trebui luat ${\displaystyle \Omega ({\sqrt {2^{n}}})}$ ${\ displaystyle {\ displaystyle \ Omega ({\ sqrt {2 ^ {n}}})}}$ ${\ displaystyle {\ displaystyle \ Omega ({\ sqrt {2 ^ {n}}})}}$ mai multe intrări înainte de a găsi probabil o pereche din care este mapată $f$ ${\ displaystyle f}$ ${\ displaystyle f}$ același rezultat ca și paradoxul zilei de naștere . Întrucât, în mod clasic, pentru a găsi s cu 100% certitudine ar trebui să verificați până la $2^{n-1}+1$ ${\ displaystyle 2 ^ {n-1} +1}$ ${\ displaystyle 2 ^ {n-1} +1}$ de intrare, problema lui Simon încearcă să găsească s folosind mult mai puține apeluri decât metoda clasică.

Prezentare generală a algoritmului

Idee

Ideea din spatele algoritmului lui Simon este de a „testa” (sau „proba”) un circuit cuantic (vezi figura de mai jos) „suficient timp” pentru a găsi $n-1$ ${\ displaystyle n-1}$ $n-1$ șiruri la n -bit liniar independent , adică

y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n},

{\ displaystyle y_ {1}, y_ {2}, \ dots, y_ {n-1} \ in \ {0,1 \} ^ {n},}

{\ displaystyle y_ {1}, y_ {2}, \ dots, y_ {n-1} \ in \ {0,1 \} ^ {n},}

astfel încât următoarele ecuații să fie satisfăcute

\left\{{\begin{aligned}y_{1}\cdot s&=0\\y_{2}\cdot s&=0\\&\,\,\,\vdots \\y_{n-1}\cdot s&=0\end{aligned}}\right.

{\ displaystyle \ left \ {{\ begin {align} y_ {1} \ cdot s & = 0 \\ y_ {2} \ cdot s & = 0 \\ & \, \, \, \ vdots \\ y_ { n- 1} \ cdot s & = 0 \ end {align}} \ right.}

{\ displaystyle \ left \ {{\ begin {align} y_ {1} \ cdot s & = 0 \\ y_ {2} \ cdot s & = 0 \\ & \, \, \, \ vdots \\ y_ { n- 1} \ cdot s & = 0 \ end {align}} \ right.}

unde este $y_{i}\cdot s$ ${\ displaystyle y_ {i} \ cdot s}$ ${\ displaystyle y_ {i} \ cdot s}$ Este forma produsului scalar 2 ; asta inseamna, $y_{i}\cdot s=y_{i1}s_{1}\oplus y_{i2}s_{2}\oplus \dots \oplus y_{in}s_{n}$ ${\ displaystyle y_ {i} \ cdot s = y_ {i1} s_ {1} \ oplus y_ {i2} s_ {2} \ oplus \ dots \ oplus y_ {in} s_ {n}}$ ${\ displaystyle y_ {i} \ cdot s = y_ {i1} s_ {1} \ oplus y_ {i2} s_ {2} \ oplus \ dots \ oplus y_ {in} s_ {n}}$ unde este $y_{ij},s_{j}\in \{0,1\}$ ${\ displaystyle y_ {ij}, s_ {j} \ in \ {0,1 \}}$ ${\ displaystyle y_ {ij}, s_ {j} \ in \ {0,1 \}}$ , pentru $i=1,\dots ,n-1$ ${\ displaystyle i = 1, \ dots, n-1}$ ${\ displaystyle i = 1, \ dots, n-1}$ si pentru $j=1,\dots ,n$ ${\ displaystyle j = 1, \ dots, n}$ ${\ displaystyle j = 1, \ dots, n}$ .

Deci, acest sistem liniar conține $n-1$ ${\ displaystyle n-1}$ $n - 1$ ecuații liniare în $n$ ${\ displaystyle n}$ $n$ necunoscute (adică biții de $s\in \{0,1\}^{n}$ ${\ displaystyle s \ in \ {0,1 \} ^ {n}}$ ${\ displaystyle s \ in \ {0,1 \} ^ {n}}$ ), iar scopul este de a rezolva pentru a obține $s$ ${\ displaystyle s}$ $s$ , Și $s$ ${\ displaystyle s}$ $s$ este fixat pentru o funcție dată $f$ ${\ displaystyle f}$ $f$ . Nu există întotdeauna o soluție (unică).

Circuitul cuantic

Circuit cuantic reprezentând / implementând algoritmul lui Simon

Circuitul cuantic (în imagine) este implementarea (și vizualizarea) părții cuantice a algoritmului lui Simon.

Mai întâi pregătiți o stare cuantică de zero (ușor de realizat). Statul $|0\rangle$ ${\ displaystyle | 0 \ rangle}$ ${\ displaystyle | 0 \ rangle}$ reprezintă $|0^{n}\rangle$ ${\ displaystyle | 0 ^ {n} \ rangle}$ ${\ displaystyle | 0 ^ {n} \ rangle}$ unde este $n$ ${\ displaystyle n}$ $n$ este numărul de qubiți. Jumătate din această stare este apoi transformată cu o poartă Hadamard . Rezultatul este apoi trimis la oracol (sau „cutie neagră”), care știe să calculeze $f$ ${\ displaystyle f}$ $f$ . Operatorul $U_{f}$ ${\ displaystyle U_ {f}}$ ${\ displaystyle U_ {f}}$ acționează asupra celor două registre ca $|x\rangle |0^{n}\rangle \rightarrow |x\rangle |f(x)\rangle$ ${\ displaystyle | x \ rangle | 0 ^ {n} \ rangle \ rightarrow | x \ rangle | f (x) \ rangle}$ ${\ displaystyle | x \ rangle | 0 ^ {n} \ rangle \ rightarrow | x \ rangle | f (x) \ rangle}$ . După aceea, o parte din ieșirea produsă de oracol este transformată folosind o altă transformare Hadamard. În cele din urmă, se face o măsurare a stării cuantice rezultate. În timpul acestei măsurători, șirurile de n-bit sunt recuperate, $y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}$ ${\ displaystyle y_ {1}, y_ {2}, \ dots, y_ {n-1} \ in \ {0,1 \} ^ {n}}$ ${\ displaystyle y_ {1}, y_ {2}, \ dots, y_ {n-1} \ in \ {0,1 \} ^ {n}}$ , menționat în secțiunea anterioară.

Algoritmul lui Simon poate fi considerat un algoritm iterativ, care folosește un circuit cuantic, urmat de un algoritm (posibil) clasic pentru a găsi soluția unui sistem liniar de ecuații.

Algoritmul lui Simon

Intrare

Algoritmul lui Simon începe cu intrare $|0^{n}\rangle \otimes |0^{n}\rangle =|0^{n}\rangle |0^{n}\rangle$ ${\ displaystyle | 0 ^ {n} \ rangle \ otimes | 0 ^ {n} \ rangle = | 0 ^ {n} \ rangle | 0 ^ {n} \ rangle}$ ${\ displaystyle | 0 ^ {n} \ rangle \ otimes | 0 ^ {n} \ rangle = | 0 ^ {n} \ rangle | 0 ^ {n} \ rangle}$ , unde este $|0^{n}\rangle$ ${\ displaystyle | 0 ^ {n} \ rangle}$ ${\ displaystyle | 0 ^ {n} \ rangle}$ este starea cuantică cu $n$ ${\ displaystyle n}$ $n$ zerouri.

(Simbolul $\otimes$ ${\ displaystyle \ otimes}$ $\ otimes$ Este simbolul tipic folosit pentru a reprezenta produsul tensor . Pentru a nu aglomera notația, simbolul $\otimes$ ${\ displaystyle \ otimes}$ $\ otimes$ este omis uneori: de exemplu în propoziția anterioară, $|0^{n}\rangle \otimes |0^{n}\rangle$ ${\ displaystyle | 0 ^ {n} \ rangle \ otimes | 0 ^ {n} \ rangle}$ ${\ displaystyle | 0 ^ {n} \ rangle \ otimes | 0 ^ {n} \ rangle}$ este echivalent cu $|0^{n}\rangle |0^{n}\rangle$ ${\ displaystyle | 0 ^ {n} \ rangle | 0 ^ {n} \ rangle}$ ${\ displaystyle | 0 ^ {n} \ rangle | 0 ^ {n} \ rangle}$ . În această intrare, este adesea folosit pentru a evita ambiguitatea sau confuzia.)

Exemplu

De exemplu, pentru $n=2$ ${\ displaystyle n = 2}$ $n = 2$ , intrarea inițială este

|0^{2}\rangle \otimes |0^{2}\rangle =|00\rangle \otimes |00\rangle =(|0\rangle \otimes |0\rangle )\otimes (|0\rangle \otimes |0\rangle )=|0\rangle \otimes |0\rangle \otimes |0\rangle \otimes |0\rangle =|0000\rangle =|0^{4}\rangle =|0^{2n}\rangle

{\ displaystyle | 0 ^ {2} \ rangle \ otimes | 0 ^ {2} \ rangle = | 00 \ rangle \ otimes | 00 \ rangle = (| 0 \ rangle \ otimes | 0 \ rangle) \ otimes (| 0 \ rangle \ otimes | 0 \ rangle) = | 0 \ rangle \ otimes | 0 \ rangle \ otimes | 0 \ rangle \ otimes | 0 \ rangle = | 0000 \ rangle = | 0 ^ {4} \ rangle = | 0 ^ {2n} \ rangle}

{\ displaystyle | 0 ^ {2} \ rangle \ otimes | 0 ^ {2} \ rangle = | 00 \ rangle \ otimes | 00 \ rangle = (| 0 \ rangle \ otimes | 0 \ rangle) \ otimes (| 0 \ rangle \ otimes | 0 \ rangle) = | 0 \ rangle \ otimes | 0 \ rangle \ otimes | 0 \ rangle \ otimes | 0 \ rangle = | 0000 \ rangle = | 0 ^ {4} \ rangle = | 0 ^ {2n} \ rangle}

.

Prima transformare a lui Hadamard

În primul rând, intrarea este transformată cu o transformată Hadamard. Mai exact, transformarea Hadamard $H^{\otimes n}$ ${\ displaystyle H ^ {\ otimes n}}$ ${\ displaystyle H ^ {\ otimes n}}$ (produsul tensorial poate fi aplicat și matricelor) se aplică primelor $n$ ${\ displaystyle n}$ $n$ qubit, adică în starea „parțială” $|0^{n}\rangle$ ${\ displaystyle | 0 ^ {n} \ rangle}$ ${\ displaystyle | 0 ^ {n} \ rangle}$ , deci starea după această operațiune se dovedește a fi

|\Psi \rangle =\left(H^{\otimes n}|0^{n}\rangle \right)\otimes |0^{n}\rangle =\left(\sum _{x\in \{0,1\}^{n}}{\frac {1}{\sqrt {2^{n}}}}\left|x\right\rangle \right)\otimes \left|0^{n}\right\rangle =\left({\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}\left|x\right\rangle \right)\otimes \left|0^{n}\right\rangle ={\frac {1}{2^{\frac {n}{2}}}}\sum _{x\in \{0,1\}^{n}}\left(\left|x\right\rangle \otimes \left|0^{n}\right\rangle \right)

{\ displaystyle | \ Psi \ rangle = \ left (H ^ {\ otimes n} | 0 ^ {n} \ rangle \ right) \ otimes | 0 ^ {n} \ rangle = \ left (\ sum _ {x \ în \ {0,1 \} ^ {n}} {\ frac {1} {\ sqrt {2 ^ {n}}}} \ left | x \ right \ rangle \ right) \ otimes \ left | 0 ^ { n} \ right \ rangle = \ left ({\ frac {1} {\ sqrt {2 ^ {n}}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left | x \ right \ rangle \ right) \ otimes \ left | 0 ^ {n} \ right \ rangle = {\ frac {1} {2 ^ {\ frac {n} {2}}}} \ sum _ {x \ în \ {0,1 \} ^ {n}} \ left (\ left | x \ right \ rangle \ otimes \ left | 0 ^ {n} \ right \ rangle \ right)}

{\ displaystyle | \ Psi \ rangle = \ left (H ^ {\ otimes n} | 0 ^ {n} \ rangle \ right) \ otimes | 0 ^ {n} \ rangle = \ left (\ sum _ {x \ în \ {0,1 \} ^ {n}} {\ frac {1} {\ sqrt {2 ^ {n}}}} \ left | x \ right \ rangle \ right) \ otimes \ left | 0 ^ { n} \ right \ rangle = \ left ({\ frac {1} {\ sqrt {2 ^ {n}}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left | x \ right \ rangle \ right) \ otimes \ left | 0 ^ {n} \ right \ rangle = {\ frac {1} {2 ^ {\ frac {n} {2}}}} \ sum _ {x \ în \ {0,1 \} ^ {n}} \ left (\ left | x \ right \ rangle \ otimes \ left | 0 ^ {n} \ right \ rangle \ right)}

unde este $x\in \{0,1\}^{n}$ ${\ displaystyle x \ in \ {0,1 \} ^ {n}}$ ${\ displaystyle x \ in \ {0,1 \} ^ {n}}$ denotă un șir de n biți (adică suma este peste toate n șirurile de biți). Termenul ${\frac {1}{\sqrt {2^{n}}}}$ ${\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n}}}}}$ ${\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n}}}}}$ poate fi ales din însumare deoarece nu depinde de $X$ ${\ displaystyle x}$ $X$ , Și ${\frac {1}{\sqrt {2^{n}}}}={\frac {1}{2^{\frac {n}{2}}}}$ ${\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n}}}} = {\ frac {1} {2 ^ {\ frac {n} {2}}}}}$ ${\ displaystyle {\ frac {1} {\ sqrt {2 ^ {n}}}} = {\ frac {1} {2 ^ {\ frac {n} {2}}}}}$ .

Exemplu

Să presupunem (încă) $n=2$ ${\ displaystyle n = 2}$ $n = 2$ , atunci intrarea este $|0000\rangle$ ${\ displaystyle | 0000 \ rangle}$ ${\ displaystyle | 0000 \ rangle}$ iar transformarea Hadamard $H^{\otimes 2}$ ${\ displaystyle H ^ {\ otimes 2}}$ ${\ displaystyle H ^ {\ otimes 2}}$ Și

H^{\otimes 2}={\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\otimes {\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}={\frac {1}{\sqrt {2}}}{\begin{bmatrix}{\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}&{\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\\{\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}&-\left({\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\right)\end{bmatrix}}={\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}}

{\ displaystyle H ^ {\ otimes 2} = {\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix}} \ otimes {\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix}} = {\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} {\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix}} & {\ frac {1} {\ sqrt { 2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix}} \\ {\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix}} & - \ left ({\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix }} \ right) \ end {bmatrix}} = {\ frac {1} {2}} {\ begin {bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \ end {bmatrix}}}

{\ displaystyle H ^ {\ otimes 2} = {\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix}} \ otimes {\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix}} = {\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} {\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix}} & {\ frac {1} {\ sqrt { 2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix}} \\ {\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix}} & - \ left ({\ frac {1} {\ sqrt {2}}} {\ begin {bmatrix} 1 & 1 \\ 1 & -1 \ end {bmatrix }} \ right) \ end {bmatrix}} = {\ frac {1} {2}} {\ begin {bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \ end {bmatrix}}}

Dacă se aplică $H^{\otimes 2}$ ${\ displaystyle H ^ {\ otimes 2}}$ ${\ displaystyle H ^ {\ otimes 2}}$ la primul $|00\rangle$ ${\ displaystyle | 00 \ rangle}$ ${\ displaystyle | 00 \ rangle}$ , adică statului

|00\rangle ={\begin{bmatrix}1\\0\\0\\0\end{bmatrix}}

{\ displaystyle | 00 \ rangle = {\ begin {bmatrix} 1 \\ 0 \\ 0 \\ 0 \ end {bmatrix}}}

{\ displaystyle | 00 \ rangle = {\ begin {bmatrix} 1 \\ 0 \\ 0 \\ 0 \ end {bmatrix}}}

primesti

{\begin{aligned}H^{\otimes 2}|00\rangle &={\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}}{\begin{bmatrix}1\\0\\0\\0\end{bmatrix}}={\frac {1}{2}}{\begin{bmatrix}1\\1\\1\\1\end{bmatrix}}\\[6pt]&={\frac {1}{2}}\left({\begin{bmatrix}1\\0\\0\\0\end{bmatrix}}+{\begin{bmatrix}0\\1\\0\\0\end{bmatrix}}+{\begin{bmatrix}0\\0\\1\\0\end{bmatrix}}+{\begin{bmatrix}0\\0\\0\\1\end{bmatrix}}\right)={\frac {1}{2}}\left(|00\rangle +|01\rangle +|10\rangle +|11\rangle \right)={\frac {1}{2^{2/2}}}\sum _{x\in \{0,1\}^{2}}\left|x\right\rangle \end{aligned}}

{\ displaystyle {\ begin {align} H ^ {\ otimes 2} | 00 \ rangle & = {\ frac {1} {2}} {\ begin {bmatrix} 1 & 1 & 1 & 1 \\ 1 & - 1 & 1 & -1 \\ 1 & 1 & - 1 & -1 \\ 1 & -1 & -1 & 1 \ end {bmatrix}} {\ begin {bmatrix} 1 \\ 0 \\ 0 \\ 0 \ end {bmatrix}} = {\ frac {1} {2}} {\ begin {bmatrix} 1 \\ 1 \\ 1 \\ 1 \ end {bmatrix}} \\ [6pt] & = {\ frac { 1} {2}} \ left ({\ begin {bmatrix} 1 \\ 0 \\ 0 \\ 0 \ end {bmatrix}} + {\ begin {bmatrix} 0 \\ 1 \\ 0 \\ 0 \ end {bmatrix}} + {\ begin {bmatrix} 0 \\ 0 \\ 1 \\ 0 \ end {bmatrix}} + {\ begin {bmatrix} 0 \\ 0 \\ 0 \\ 1 \ end {bmatrix}} \ right) = {\ frac {1} {2}} \ left (| 00 \ rangle + | 01 \ rangle + | 10 \ rangle + | 11 \ rangle \ right) = {\ frac {1} {2 ^ { 2/2}}} \ sum _ {x \ in \ {0,1 \} ^ {2}} \ left | x \ right \ rangle \ end {align}}}

{\ displaystyle {\ begin {align} H ^ {\ otimes 2} | 00 \ rangle & = {\ frac {1} {2}} {\ begin {bmatrix} 1 & 1 & 1 & 1 \\ 1 & - 1 & 1 & -1 \\ 1 & 1 & - 1 & -1 \\ 1 & -1 & -1 & 1 \ end {bmatrix}} {\ begin {bmatrix} 1 \\ 0 \\ 0 \\ 0 \ end {bmatrix}} = {\ frac {1} {2}} {\ begin {bmatrix} 1 \\ 1 \\ 1 \\ 1 \ end {bmatrix}} \\ [6pt] & = {\ frac { 1} {2}} \ left ({\ begin {bmatrix} 1 \\ 0 \\ 0 \\ 0 \ end {bmatrix}} + {\ begin {bmatrix} 0 \\ 1 \\ 0 \\ 0 \ end {bmatrix}} + {\ begin {bmatrix} 0 \\ 0 \\ 1 \\ 0 \ end {bmatrix}} + {\ begin {bmatrix} 0 \\ 0 \\ 0 \\ 1 \ end {bmatrix}} \ right) = {\ frac {1} {2}} \ left (| 00 \ rangle + | 01 \ rangle + | 10 \ rangle + | 11 \ rangle \ right) = {\ frac {1} {2 ^ { 2/2}}} \ sum _ {x \ in \ {0,1 \} ^ {2}} \ left | x \ right \ rangle \ end {align}}}

Pentru a obține starea compusă, produsul tensor al $H^{\otimes 2}|00\rangle$ ${\ displaystyle H ^ {\ otimes 2} | 00 \ rangle}$ ${\ displaystyle H ^ {\ otimes 2} | 00 \ rangle}$ cu $|00\rangle$ ${\ displaystyle | 00 \ rangle}$ ${\ displaystyle | 00 \ rangle}$ , sau

{\begin{aligned}\left(H^{\otimes 2}|00\rangle \right)\otimes |00\rangle &=\left({\frac {1}{2}}\sum _{x\in \{0,1\}^{2}}\left|x\right\rangle \right)\otimes |00\rangle ={\frac {1}{2}}\left(|00\rangle +|01\rangle +|10\rangle +|11\rangle \right)\otimes |00\rangle \\[6pt]&={\frac {1}{2}}\left(|00\rangle \otimes |00\rangle +|01\rangle \otimes |00\rangle +|10\rangle \otimes |00\rangle +|11\rangle \otimes |00\rangle \right)\\&={\frac {1}{2}}\sum _{x\in \{0,1\}^{2}}\left(\left|x\right\rangle \otimes |00\rangle \right).\end{aligned}}

{\ displaystyle {\ begin {align} \ left (H ^ {\ otimes 2} | 00 \ rangle \ right) \ otimes | 00 \ rangle & = \ left ({\ frac {1} {2}} \ sum _ {x \ in \ {0,1 \} ^ {2}} \ left | x \ right \ rangle \ right) \ otimes | 00 \ rangle = {\ frac {1} {2}} \ left (| 00 \ rangle + | 01 \ rangle + | 10 \ rangle + | 11 \ rangle \ right) \ otimes | 00 \ rangle \\ [6pt] & = {\ frac {1} {2}} \ left (| 00 \ rangle \ otimes | 00 \ rangle + | 01 \ rangle \ otimes | 00 \ rangle + | 10 \ rangle \ otimes | 00 \ rangle + | 11 \ rangle \ otimes | 00 \ rangle \ right) \\ & = {\ frac {1 } {2}} \ sum _ {x \ in \ {0,1 \} ^ {2}} \ left (\ left | x \ right \ rangle \ otimes | 00 \ rangle \ right). \ End {align} }}

{\ displaystyle {\ begin {align} \ left (H ^ {\ otimes 2} | 00 \ rangle \ right) \ otimes | 00 \ rangle & = \ left ({\ frac {1} {2}} \ sum _ {x \ in \ {0,1 \} ^ {2}} \ left | x \ right \ rangle \ right) \ otimes | 00 \ rangle = {\ frac {1} {2}} \ left (| 00 \ rangle + | 01 \ rangle + | 10 \ rangle + | 11 \ rangle \ right) \ otimes | 00 \ rangle \\ [6pt] & = {\ frac {1} {2}} \ left (| 00 \ rangle \ otimes | 00 \ rangle + | 01 \ rangle \ otimes | 00 \ rangle + | 10 \ rangle \ otimes | 00 \ rangle + | 11 \ rangle \ otimes | 00 \ rangle \ right) \\ & = {\ frac {1 } {2}} \ sum _ {x \ in \ {0,1 \} ^ {2}} \ left (\ left | x \ right \ rangle \ otimes | 00 \ rangle \ right). \ End {align} }}

Oracol

Acum se numește oracol sau cutie neagră ( $U_{f}$ ${\ displaystyle U_ {f}}$ ${\ displaystyle U_ {f}}$ în figură) pentru a calcula funcția $f$ ${\ displaystyle f}$ $f$ pe intrarea transformată $|\Psi \rangle ={\frac {1}{2^{n/2}}}\sum _{x\in \{0,1\}^{n}}\left(\left|x\right\rangle \otimes \left|0^{n}\right\rangle \right)$ ${\ displaystyle | \ Psi \ rangle = {\ frac {1} {2 ^ {n / 2}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left (\ left | x \ right \ rangle \ otimes \ left | 0 ^ {n} \ right \ rangle \ right)}$ ${\ displaystyle | \ Psi \ rangle = {\ frac {1} {2 ^ {n / 2}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left (\ left | x \ right \ rangle \ otimes \ left | 0 ^ {n} \ right \ rangle \ right)}$ , pentru a obține statutul

|\Psi \rangle '={\frac {1}{2^{n/2}}}\sum _{x\in \{0,1\}^{n}}\left(\left|x\right\rangle \otimes \left|f(x)\right\rangle \right)

{\ displaystyle | \ Psi \ rangle '= {\ frac {1} {2 ^ {n / 2}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left (\ left | x \ right \ rangle \ otimes \ left | f (x) \ right \ rangle \ right)}

{\ displaystyle | \ Psi \ rangle '= {\ frac {1} {2 ^ {n / 2}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left (\ left | x \ right \ rangle \ otimes \ left | f (x) \ right \ rangle \ right)}

A doua transformare a lui Hadamard

Transformarea lui este apoi aplicată din nou $H^{\otimes n}$ ${\ displaystyle H ^ {\ otimes n}}$ ${\ displaystyle H ^ {\ otimes n}}$ la stările celor dintâi $n$ ${\ displaystyle n}$ $n$ stat qubit $|\Psi \rangle '$ ${\ displaystyle | \ Psi \ rangle '}$ ${\ displaystyle | \ Psi \ rangle '}$ , si tu ai

{\begin{aligned}|\Psi \rangle ''&={\frac {1}{2^{n/2}}}\sum _{x\in \{0,1\}^{n}}\left(\left(H^{\otimes n}\left|x\right\rangle \right)\otimes \left|f(x)\right\rangle \right)\\[4pt]&={\frac {1}{2^{n/2}}}\sum _{x\in \{0,1\}^{n}}\left(\left({\frac {1}{2^{n/2}}}\sum _{y\in \{0,1\}^{n}}(-1)^{x\cdot y}\left|y\right\rangle \right)\otimes \left|f(x)\right\rangle \right)={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left(\sum _{y\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|y\right\rangle \otimes \left|f(x)\right\rangle \right)\right)\end{aligned}}

{\ displaystyle {\ begin {align} | \ Psi \ rangle '' & = {\ frac {1} {2 ^ {n / 2}}} \ sum _ {x \ in \ {0,1 \} ^ { n}} \ left (\ left (H ^ {\ otimes n} \ left | x \ right \ rangle \ right) \ otimes \ left | f (x) \ right \ rangle \ right) \\ [4pt] & = {\ frac {1} {2 ^ {n / 2}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left (\ left ({\ frac {1} {2 ^ {n / 2}}} \ sum _ {y \ in \ {0,1 \} ^ {n}} (- 1) ^ {x \ cdot y} \ left | y \ right \ rangle \ right) \ otimes \ left | f (x) \ right \ rangle \ right) = {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left (\ sum _ {y \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | y \ right \ rangle \ otimes \ left | f (x ) \ right \ rangle \ right) \ right) \ end {align}}}

{\ displaystyle {\ begin {align} | \ Psi \ rangle '' & = {\ frac {1} {2 ^ {n / 2}}} \ sum _ {x \ in \ {0,1 \} ^ { n}} \ left (\ left (H ^ {\ otimes n} \ left | x \ right \ rangle \ right) \ otimes \ left | f (x) \ right \ rangle \ right) \\ [4pt] & = {\ frac {1} {2 ^ {n / 2}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left (\ left ({\ frac {1} {2 ^ {n / 2}}} \ sum _ {y \ in \ {0,1 \} ^ {n}} (- 1) ^ {x \ cdot y} \ left | y \ right \ rangle \ right) \ otimes \ left | f (x) \ right \ rangle \ right) = {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left (\ sum _ {y \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | y \ right \ rangle \ otimes \ left | f (x ) \ right \ rangle \ right) \ right) \ end {align}}}

unde este $(-1)^{x\cdot y}$ ${\ displaystyle (-1) ^ {x \ cdot y}}$ ${\ displaystyle (-1) ^ {x \ cdot y}}$ poate fi sau $-1$ ${\ displaystyle -1}$ $-1$ sau $1$ ${\ displaystyle 1}$ $1$ , depinde de $x\cdot y=x_{1}y_{1}+\dots +x_{n}y_{n}$ ${\ displaystyle x \ cdot y = x_ {1} y_ {1} + \ dots + x_ {n} y_ {n}}$ ${\ displaystyle x \ cdot y = x_ {1} y_ {1} + \ dots + x_ {n} y_ {n}}$ , unde este $x_{i},y_{i}\in \{0,1\}$ ${\ displaystyle x_ {i}, y_ {i} \ in \ {0,1 \}}$ ${\ displaystyle x_ {i}, y_ {i} \ in \ {0,1 \}}$ , pentru $i=1,\dots ,n$ ${\ displaystyle i = 1, \ dots, n}$ ${\ displaystyle i = 1, \ dots, n}$ . Deci, de exemplu, dacă $x=101$ ${\ displaystyle x = 101}$ ${\ displaystyle x = 101}$ Și $y=111$ ${\ displaystyle y = 111}$ ${\ displaystyle y = 111}$ , asa de $x\cdot y=1*1+0*1+1*1=2$ ${\ displaystyle x \ cdot y = 1 * 1 + 0 * 1 + 1 * 1 = 2}$ ${\ displaystyle x \ cdot y = 1 * 1 + 0 * 1 + 1 * 1 = 2}$ , ceea ce este egal, deci în acest caz, $(-1)^{x\cdot y}=(-1)^{1*1+0*1+1*1}=(-1)^{2}=1$ ${\ displaystyle (-1) ^ {x \ cdot y} = (- 1) ^ {1 * 1 + 0 * 1 + 1 * 1} = (- 1) ^ {2} = 1}$ ${\ displaystyle (-1) ^ {x \ cdot y} = (- 1) ^ {1 * 1 + 0 * 1 + 1 * 1} = (- 1) ^ {2} = 1}$ ; ${x\cdot y}$ ${\ displaystyle {x \ cdot y}}$ ${\ displaystyle {x \ cdot y}}$ este întotdeauna un număr non-negativ.

Acum statul este rescris

|\Psi \rangle ''={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left(\sum _{y\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|y\right\rangle \otimes \left|f(x)\right\rangle \right)\right)

{\ displaystyle | \ Psi \ rangle '' = {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left (\ sum _ {y \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | y \ right \ rangle \ otimes \ left | f (x) \ right \ rangle \ right) \ right)}

{\ displaystyle | \ Psi \ rangle '' = {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left (\ sum _ {y \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | y \ right \ rangle \ otimes \ left | f (x) \ right \ rangle \ right) \ right)}

după cum urmează:

|\Psi \rangle ''=\sum _{y\in \{0,1\}^{n}}\left(\left|y\right\rangle \otimes \left({\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right)\right)\right)

{\ displaystyle | \ Psi \ rangle '' = \ sum _ {y \ in \ {0,1 \} ^ {n}} \ left (\ left | y \ right \ rangle \ otimes \ left ({\ frac { 1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) \ right) \ right)}

{\ displaystyle | \ Psi \ rangle '' = \ sum _ {y \ in \ {0,1 \} ^ {n}} \ left (\ left | y \ right \ rangle \ otimes \ left ({\ frac { 1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) \ right) \ right)}

Măsura

După efectuarea tuturor operațiunilor de mai sus, trebuie efectuată o măsurare.

Acum există două cazuri posibile care trebuie analizate separat

$x\oplus y=0^{n}$ ${\ displaystyle x \ oplus y = 0 ^ {n}}$ ${\ displaystyle x \ oplus y = 0 ^ {n}}$ sau
$x\oplus y=s$ ${\ displaystyle x \ oplus y = s}$ ${\ displaystyle x \ oplus y = s}$ , cu $s\neq 0^{n}$ ${\ displaystyle s \ neq 0 ^ {n}}$ ${\ displaystyle s \ neq 0 ^ {n}}$ .

Primul caz

Să analizăm cazul în care $x\oplus y=0^{n}$ ${\ displaystyle x \ oplus y = 0 ^ {n}}$ ${\ displaystyle x \ oplus y = 0 ^ {n}}$ , ceea ce înseamnă că $f$ ${\ displaystyle f}$ $f$ Este unu-la-unu ( injectiv ).

Starea înainte de măsurare este

\sum _{y\in \{0,1\}^{n}}\left|y\right\rangle \otimes \left({\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right)\right)

{\ displaystyle \ sum _ {y \ in \ {0,1 \} ^ {n}} \ left | y \ right \ rangle \ otimes \ left ({\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) \ right)}

{\ displaystyle \ sum _ {y \ in \ {0,1 \} ^ {n}} \ left | y \ right \ rangle \ otimes \ left ({\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) \ right)}

Acum, probabilitatea ca măsura să dea orice șir $y\in \{0,1\}^{n}$ ${\ displaystyle y \ in \ {0,1 \} ^ {n}}$ ${\ displaystyle y \ in \ {0,1 \} ^ {n}}$ Și

p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}={\frac {1}{2^{n}}}

{\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((-1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) {\ Bigg \ |}} ^ {2} = {\ frac {1} {2 ^ {n} }}}

{\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((-1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) {\ Bigg \ |}} ^ {2} = {\ frac {1} {2 ^ {n} }}}

Aceasta rezultă din faptul că

{{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|x\right\rangle \right){\Bigg \|}}^{2}

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

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

deoarece cei doi vectori diferă doar în ordinea componentelor lor, având în vedere că $f$ ${\ displaystyle f}$ $f$ este injectiv .

Valoarea membrului din dreapta se menține pur și simplu

{{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|x\right\rangle \right){\Bigg \|}}^{2}={\frac {1}{2^{n}}}

{\ displaystyle {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | x \ right \ rangle \ right) {\ Bigg \ |}} ^ {2} = {\ frac {1} {2 ^ {n}}}}

{\ displaystyle {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((- 1) ^ {x \ cdot y} \ left | x \ right \ rangle \ right) {\ Bigg \ |}} ^ {2} = {\ frac {1} {2 ^ {n}}}}

Prin urmare, când $x\oplus y=0^{n}$ ${\ displaystyle x \ oplus y = 0 ^ {n}}$ ${\ displaystyle x \ oplus y = 0 ^ {n}}$ Rezultatul măsurării este pur și simplu un șir de n-biți distribuit uniform .

Al doilea caz

Să analizăm acum cazul în care $x\oplus y=s$ ${\ displaystyle x \ oplus y = s}$ ${\ displaystyle x \ oplus y = s}$ , unde este $s\neq 0^{n}$ ${\ displaystyle s \ neq 0 ^ {n}}$ ${\ displaystyle s \ neq 0 ^ {n}}$ . În acest caz, $f$ ${\ displaystyle f}$ $f$ este o funcție două la unu, adică există două intrări care sunt mapate din $f$ ${\ displaystyle f}$ $f$ la aceeași ieșire.

Analiza efectuată în prima este încă valabilă: probabilitatea de a măsura orice șir $y\in \{0,1\}^{n}$ ${\ displaystyle y \ in \ {0,1 \} ^ {n}}$ ${\ displaystyle y \ in \ {0,1 \} ^ {n}}$ poate fi totuși reprezentat de

p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}

{\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((-1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) {\ Bigg \ |}} ^ {2}}

{\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((-1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) {\ Bigg \ |}} ^ {2}}

Cu toate acestea, în acest al doilea caz, este necesar să înțelegem care este valoarea $p_{y}$ ${\ displaystyle p_ {y}}$ $p_ {y}$ .

Este $A=f(\{0,1\}^{n})$ ${\ displaystyle A = f (\ {0,1 \} ^ {n})}$ ${\ displaystyle A = f (\ {0,1 \} ^ {n})}$ , setul de imagini al $f$ ${\ displaystyle f}$ $f$ . Este $z\in A$ ${\ displaystyle z \ în A}$ $z \ în A$ (o ieșire a funcției), apoi pentru fiecare $x_{1}\in \{0,1\}^{n}$ ${\ displaystyle x_ {1} \ in \ {0,1 \} ^ {n}}$ ${\ displaystyle x_ {1} \ in \ {0,1 \} ^ {n}}$ , există unul și unul singur $x_{2}\in \{0,1\}^{n}$ ${\ displaystyle x_ {2} \ in \ {0,1 \} ^ {n}}$ ${\ displaystyle x_ {2} \ in \ {0,1 \} ^ {n}}$ , astfel încât $f(x_{1})=f(x_{2})=z$ ${\ displaystyle f (x_ {1}) = f (x_ {2}) = z}$ ${\ displaystyle f (x_ {1}) = f (x_ {2}) = z}$ ; în plus, avem asta $x_{1}\oplus x_{2}=s$ ${\ displaystyle x_ {1} \ oplus x_ {2} = s}$ ${\ displaystyle x_ {1} \ oplus x_ {2} = s}$ , care este echivalent cu $x_{2}=s\oplus x_{1}$ ${\ displaystyle x_ {2} = s \ oplus x_ {1}}$ ${\ displaystyle x_ {2} = s \ oplus x_ {1}}$ .

Deci, iată-l

p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{z\in A}\left(((-1)^{x_{1}\cdot y}+(-1)^{x_{2}\cdot y})\left|z\right\rangle \right){\Bigg \|}}^{2}

{\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((-1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) {\ Bigg \ |}} ^ {2} = {{\ Bigg \ |} {\ frac {1 } {2 ^ {n}}} \ sum _ {z \ în A} \ left (((- 1) ^ {x_ {1} \ cdot y} + (- 1) ^ {x_ {2} \ cdot y }) \ left | z \ right \ rangle \ right) {\ Bigg \ |}} ^ {2}}

{\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {x \ in \ {0,1 \} ^ {n}} \ left ((-1) ^ {x \ cdot y} \ left | f (x) \ right \ rangle \ right) {\ Bigg \ |}} ^ {2} = {{\ Bigg \ |} {\ frac {1 } {2 ^ {n}}} \ sum _ {z \ în A} \ left (((- 1) ^ {x_ {1} \ cdot y} + (- 1) ^ {x_ {2} \ cdot y }) \ left | z \ right \ rangle \ right) {\ Bigg \ |}} ^ {2}}

De cand $(x_{1}\oplus s)\cdot y=(x_{1}\cdot y)\oplus (s\cdot y)$ ${\ displaystyle (x_ {1} \ oplus s) \ cdot y = (x_ {1} \ cdot y) \ oplus (s \ cdot y)}$ ${\ displaystyle (x_ {1} \ oplus s) \ cdot y = (x_ {1} \ cdot y) \ oplus (s \ cdot y)}$ , puteți rescrie în continuare ca

(-1)^{x_{1}\cdot y}+(-1)^{x_{2}\cdot y}=(-1)^{x_{1}\cdot y}+(-1)^{(x_{1}\oplus s)\cdot y}

{\ displaystyle (-1) ^ {x_ {1} \ cdot y} + (- 1) ^ {x_ {2} \ cdot y} = (- 1) ^ {x_ {1} \ cdot y} + (- 1) ^ {(x_ {1} \ oplus s) \ cdot y}}

{\ displaystyle (-1) ^ {x_ {1} \ cdot y} + (- 1) ^ {x_ {2} \ cdot y} = (- 1) ^ {x_ {1} \ cdot y} + (- 1) ^ {(x_ {1} \ oplus s) \ cdot y}}

Acum dacă $y\cdot s=y_{1}s_{1}+\dots +y_{n}s_{n}$ ${\ displaystyle y \ cdot s = y_ {1} s_ {1} + \ dots + y_ {n} s_ {n}}$ ${\ displaystyle y \ cdot s = y_ {1} s_ {1} + \ dots + y_ {n} s_ {n}}$ este ciudat atunci $(-1)^{y\cdot s}=-1$ ${\ displaystyle (-1) ^ {y \ cdot s} = - 1}$ ${\ displaystyle (-1) ^ {y \ cdot s} = - 1}$ . Atunci,

(-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})

{\ displaystyle (-1) ^ {x_ {1} \ cdot y} (1 + (- 1) ^ {y \ cdot s})}

{\ displaystyle (-1) ^ {x_ {1} \ cdot y} (1 + (- 1) ^ {y \ cdot s})}

Categoric, $p_{y}$ ${\ displaystyle p_ {y}}$ $p_ {y}$ poate fi scris ca

p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})\left|z\right\rangle \right){\Bigg \|}}^{2}

{\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {z \ în A} \ left ((- 1) ^ {x_ {1 } \ cdot y} (1 + (- 1) ^ {y \ cdot s}) \ left | z \ right \ rangle \ right) {\ Bigg \ |}} ^ {2}}

{\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {z \ în A} \ left ((- 1) ^ {x_ {1 } \ cdot y} (1 + (- 1) ^ {y \ cdot s}) \ left | z \ right \ rangle \ right) {\ Bigg \ |}} ^ {2}}

Numar impar

Dacă în schimb, $y\cdot s$ ${\ displaystyle y \ cdot s}$ ${\ displaystyle y \ cdot s}$ este uniform, atunci $(-1)^{y\cdot s}=1$ ${\ displaystyle (-1) ^ {y \ cdot s} = 1}$ ${\ displaystyle (-1) ^ {y \ cdot s} = 1}$ . În acest caz,

(-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})=(-1)^{x_{1}\cdot y}(1-1)=0

{\ displaystyle (-1) ^ {x_ {1} \ cdot y} (1 + (- 1) ^ {y \ cdot s}) = (- 1) ^ {x_ {1} \ cdot y} (1- 1) = 0}

{\ displaystyle (-1) ^ {x_ {1} \ cdot y} (1 + (- 1) ^ {y \ cdot s}) = (- 1) ^ {x_ {1} \ cdot y} (1- 1) = 0}

În consecință, avem

p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})\left|z\right\rangle \right){\Bigg \|}}^{2}=0

{\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {z \ în A} \ left ((- 1) ^ {x_ {1 } \ cdot y} (1 + (- 1) ^ {y \ cdot s}) \ left | z \ right \ rangle \ right) {\ Bigg \ |}} ^ {2} = 0}

{\ displaystyle p_ {y} = {{\ Bigg \ |} {\ frac {1} {2 ^ {n}}} \ sum _ {z \ în A} \ left ((- 1) ^ {x_ {1 } \ cdot y} (1 + (- 1) ^ {y \ cdot s}) \ left | z \ right \ rangle \ right) {\ Bigg \ |}} ^ {2} = 0}

De cand $p_{y}=0$ ${\ displaystyle p_ {y} = 0}$ ${\ displaystyle p_ {y} = 0}$ , niciun șir nu va fi măsurat vreodată $y\in \{0,1\}^{n}$ ${\ displaystyle y \ in \ {0,1 \} ^ {n}}$ ${\ displaystyle y \ in \ {0,1 \} ^ {n}}$ . Si ha interferenza distruttiva.

Numero pari

(-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})=(-1)^{x_{1}\cdot y}2

(-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})=(-1)^{x_{1}\cdot y}2

(-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})=(-1)^{x_{1}\cdot y}2

Quindi si ha

p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}(2)\left|z\right\rangle \right){\Bigg \|}}^{2}={{\Bigg \|}{\frac {2}{2^{n}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}\left|z\right\rangle \right){\Bigg \|}}^{2}={{\Bigg \|}{\frac {1}{2^{n-1}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}\left|z\right\rangle \right){\Bigg \|}}^{2}

p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}(2)\left|z\right\rangle \right){\Bigg \|}}^{2}={{\Bigg \|}{\frac {2}{2^{n}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}\left|z\right\rangle \right){\Bigg \|}}^{2}={{\Bigg \|}{\frac {1}{2^{n-1}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}\left|z\right\rangle \right){\Bigg \|}}^{2}

p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}(2)\left|z\right\rangle \right){\Bigg \|}}^{2}={{\Bigg \|}{\frac {2}{2^{n}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}\left|z\right\rangle \right){\Bigg \|}}^{2}={{\Bigg \|}{\frac {1}{2^{n-1}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}\left|z\right\rangle \right){\Bigg \|}}^{2}

Si tratta del caso di interferenza costruttiva ,

{\frac {2}{2^{n}}}=2*2^{-n}=2^{1}*2^{-n}=2^{-n+1}=2^{-(n-1)}={\frac {1}{2^{n-1}}}

{\frac {2}{2^{n}}}=2*2^{-n}=2^{1}*2^{-n}=2^{-n+1}=2^{-(n-1)}={\frac {1}{2^{n-1}}}

{\frac {2}{2^{n}}}=2*2^{-n}=2^{1}*2^{-n}=2^{-n+1}=2^{-(n-1)}={\frac {1}{2^{n-1}}}

.

Quindi, per riassumere, in questo caso si hanno le seguenti probabilità

p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}={\begin{cases}{\frac {1}{2^{n-1}}}&\quad {\text{se }}y\cdot s{\text{ pari}}\\0&\quad {\text{se }}y\cdot s{\text{ dispari}}\\\end{cases}}

p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}={\begin{cases}{\frac {1}{2^{n-1}}}&\quad {\text{se }}y\cdot s{\text{ pari}}\\0&\quad {\text{se }}y\cdot s{\text{ dispari}}\\\end{cases}}

p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}={\begin{cases}{\frac {1}{2^{n-1}}}&\quad {\text{se }}y\cdot s{\text{ pari}}\\0&\quad {\text{se }}y\cdot s{\text{ dispari}}\\\end{cases}}

Elaborazione classica

Facendo girare il circuito, risultano due casi:

Nel caso (particolare) in cui $x\oplus y=0^{n}$ $x\oplus y=0^{n}$ $x\oplus y=0^{n}$ , i risultati della misura sono $y\in \{0,1\}^{n}$ $y\in \{0,1\}^{n}$ $y\in \{0,1\}^{n}$ con probabilità $p_{y}={\frac {1}{2^{n}}}$ $p_{y}={\frac {1}{2^{n}}}$ $p_{y}={\frac {1}{2^{n}}}$

nel caso in cui $x\oplus y=s$ $x\oplus y=s$ $x\oplus y=s$ ( $s\neq 0^{n}$ $s\neq 0^{n}$ $s\neq 0^{n}$ ), la probabilità di ottenere una stringa $y\in \{0,1\}^{n}$ $y\in \{0,1\}^{n}$ $y\in \{0,1\}^{n}$ è data da

p_{y}={\begin{cases}{\frac {1}{2^{n-1}}}&\quad {\text{se }}y\cdot s{\text{ pari}}\\0&\quad {\text{se }}y\cdot s{\text{ dispari}}\\\end{cases}}

p_{y}={\begin{cases}{\frac {1}{2^{n-1}}}&\quad {\text{se }}y\cdot s{\text{ pari}}\\0&\quad {\text{se }}y\cdot s{\text{ dispari}}\\\end{cases}}

p_{y}={\begin{cases}{\frac {1}{2^{n-1}}}&\quad {\text{se }}y\cdot s{\text{ pari}}\\0&\quad {\text{se }}y\cdot s{\text{ dispari}}\\\end{cases}}

Perciò, in ambo i casi i risultati della misura danno $y\in \{0,1\}^{n}$ $y\in \{0,1\}^{n}$ $y\in \{0,1\}^{n}$ che soddisfa $s\cdot y=0$ $s\cdot y=0$ $s\cdot y=0$ , e la distribuzione è uniforme su tutte le stringhe che soddisfano questa condizione.

Si hanno informazioni a sufficienza per determinare $s$ ${\displaystyle s}$ $s$ ? Sì, a patto che il processo sia ripetuto molte volte. Nello specifico, se il processo sopra viene ripetuto $n-1$ ${\displaystyle n-1}$ $n - 1$ volte, si ottengono $n-1$ ${\displaystyle n-1}$ $n - 1$ stringhe $y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}$ $y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}$ $y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}$ , tali che

{\begin{cases}y_{1}\cdot s&=0\\y_{2}\cdot s&=0\\&\vdots \\y_{n-1}\cdot s&=0\end{cases}}

{\begin{cases}y_{1}\cdot s&=0\\y_{2}\cdot s&=0\\&\vdots \\y_{n-1}\cdot s&=0\end{cases}}

{\begin{cases}y_{1}\cdot s&=0\\y_{2}\cdot s&=0\\&\vdots \\y_{n-1}\cdot s&=0\end{cases}}

Questo è un sistema di $n-1$ ${\displaystyle n-1}$ $n - 1$ equazioni lineari in $n$ ${\displaystyle n}$ $n$ incognite (cioè i bit di $s$ ${\displaystyle s}$ $s$ ), e lo scopo è risolverlo per ottenere $s$ ${\displaystyle s}$ $s$ . Si noti che ognuna delle $y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}$ $y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}$ $y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}$ che si ottengono dalle misura è, naturalmente, l'esito di una misura, quindi è conosciuta.

Si otterrà una unica soluzione non nulla $s$ ${\displaystyle s}$ $s$ se $y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}$ $y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}$ $y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}$ sono linearmente indipendenti. La probabilità che $y_{1},y_{2},\dots ,y_{n-1}$ $y_{1},y_{2},\dots ,y_{n-1}$ $y_{1},y_{2},\dots ,y_{n-1}$ siano linearmente indipendente è almeno

\prod _{k=1}^{\infty }\left(1-{\frac {1}{2^{k}}}\right)=0.288788\dots >{\frac {1}{4}}

\prod _{k=1}^{\infty }\left(1-{\frac {1}{2^{k}}}\right)=0.288788\dots >{\frac {1}{4}}

\prod _{k=1}^{\infty }\left(1-{\frac {1}{2^{k}}}\right)=0.288788\dots >{\frac {1}{4}}

Se sono linearmente indipendenti, si può risolvere il sistema e trovare una candidata per la soluzione $s'\neq 0^{n}$ $s'\neq 0^{n}$ $s'\neq 0^{n}$ e verificare che $f(0^{n})=f(s')$ $f(0^{n})=f(s')$ $f(0^{n})=f(s')$ . Se $f(0^{n})=f(s')$ $f(0^{n})=f(s')$ $f(0^{n})=f(s')$ , allora $s=s'$ ${\displaystyle s=s'}$ $s=s'$ e il problema è risolto. Se $f(0^{n})\neq f(s')$ $f(0^{n})\neq f(s')$ $f(0^{n})\neq f(s')$ , deve essere $s=0^{n}$ $s=0^{n}$ $s=0^{n}$ . Se così non fosse, l'unica soluzione non nulla delle equazioni lineari sarebbe stata $s$ ${\displaystyle s}$ $s$ ). Ad ogni modo, con l'indipendenza lineare delle equazioni, si può risolvere il problema.

Complessità

L'algoritmo di Simon necessita di $O(n)$ ${\displaystyle O(n)}$ $O(n)$ chiamate all'oracolo, mentre un algoritmo classico ne necessita almeno $\Omega (2^{n/2})$ $\Omega (2^{n/2})$ $\Omega (2^{n/2})$ . Si sa anche che l'algoritmo di Simon è ottimale, nel senso che ogni altro algoritmo quantistico che risolve questo problema necessiterà di $\Omega (n)$ $\Omega (n)$ $\Omega (n)$ chiamate. ^[1] ^[2]

Note

^ P. Koiran, V. Nesme e N. Portier, The quantum query complexity of the Abelian hidden subgroup problem ( ps ), in Theoretical Computer Science , vol. 380, n. 1-2, 2007, pp. 115–126, DOI : 10.1016/j.tcs.2007.02.057 .
^ P. Koiran, V. Nesme e N. Portier, A quantum lower bound for the query complexity of Simon's Problem ( ps ), in Proc. ICALP. , vol. 3580, 2005, pp. 1287–1298, Bibcode : 2005quant.ph..1060K , arXiv : quant-ph/0501060 .

Portale Informatica

Portale Quantistica

[1] P. Koiran, V. Nesme e N. Portier, The quantum query complexity of the Abelian hidden subgroup problem ( ps ), in Theoretical Computer Science , vol. 380, n. 1-2, 2007, pp. 115–126, DOI : 10.1016/j.tcs.2007.02.057 .

[2] P. Koiran, V. Nesme e N. Portier, A quantum lower bound for the query complexity of Simon's Problem ( ps ), in Proc. ICALP. , vol. 3580, 2005, pp. 1287–1298, Bibcode : 2005quant.ph..1060K , arXiv : quant-ph/0501060 .

[1]

[2]