Prova d'intercanvi

La prova d'intercanvi és un procediment de càlcul quàntic que s'utilitza per comprovar quant difereixen dos estats quàntics, que apareix per primera vegada al treball de Barenco et al.^[1] i posteriorment redescoberta per Harry Buhrman, Richard Cleve, John Watrous i Ronald de Wolf.^[2] Apareix habitualment en l'aprenentatge automàtic quàntic i és un circuit utilitzat per a proves de concepte en implementacions d'ordinadors quàntics.^[3]^[4]

Formalment, la prova d'intercanvi pren dos estats d'entrada $|\phi \rangle$ i $|\psi \rangle$ i produeix una variable aleatòria de Bernoulli que és 1 amb probabilitat $\textstyle {\frac {1}{2}}-{\frac {1}{2}}{|\langle \psi |\phi \rangle |}^{2}$ (on les expressions aquí utilitzen la notació bra–ket). Això permet, per exemple, estimar el producte interior quadrat entre els dos estats, ${|\langle \psi |\phi \rangle |}^{2}$ , a $\varepsilon$ error additiu agafant la mitjana $O(\textstyle {\frac {1}{\varepsilon ^{2}}})$ execucions de la prova d'intercanvi. Això requereix $O(\textstyle {\frac {1}{\varepsilon ^{2}}})$ còpies dels estats d'entrada. El producte interior quadrat mesura aproximadament la "superposició" entre els dos estats i es pot utilitzar en aplicacions algebraiques lineals, inclosa la agrupació d'estats quàntics.^[5]

Explicació del circuit modifica

Considereu dos estats: $|\phi \rangle$ i $|\psi \rangle$ . L'estat del sistema al començament del protocol és $|0,\phi ,\psi \rangle$ . Després de la porta Hadamard, l'estat del sistema és ${\frac {1}{\sqrt {2}}}(|0,\phi ,\psi \rangle +|1,\phi ,\psi \rangle )$ . La porta SWAP controlada transforma l'estat en ${\frac {1}{\sqrt {2}}}(|0,\phi ,\psi \rangle +|1,\psi ,\phi \rangle )$ . La segona porta Hadamard resulta

{\frac {1}{2}}(|0,\phi ,\psi \rangle +|1,\phi ,\psi \rangle +|0,\psi ,\phi \rangle -|1,\psi ,\phi \rangle )={\frac {1}{2}}|0\rangle (|\phi ,\psi \rangle +|\psi ,\phi \rangle )+{\frac {1}{2}}|1\rangle (|\phi ,\psi \rangle -|\psi ,\phi \rangle )

La porta de mesura del primer qubit assegura que sigui 0 amb una probabilitat de

P({\text{Primer qubit}}=0)={\frac {1}{2}}{\Big (}\langle \phi |\langle \psi |+\langle \psi |\langle \phi |{\Big )}{\frac {1}{2}}{\Big (}|\phi \rangle |\psi \rangle +|\psi \rangle |\phi \rangle {\Big )}={\frac {1}{2}}+{\frac {1}{2}}{|\langle \psi |\phi \rangle |}^{2}

quan es mesura. Si

\psi

i

\phi

són ortogonals

({|\langle \psi |\phi \rangle |}^{2}=0)

, aleshores la probabilitat que es mesura 0 és

{\frac {1}{2}}

. Si els estats són iguals

({|\langle \psi |\phi \rangle |}^{2}=1)

, aleshores la probabilitat que es mesura 0 és 1.^[6]

En general, per $P$ proves de la prova d'intercanvi utilitzant $P$ còpies de $|\phi \rangle$ i $P$ còpies de $|\psi \rangle$ , la fracció de mesures que són zero és $1-\textstyle {\frac {1}{P}}\textstyle \sum _{i=1}^{P}M_{i}$ , així que prenent $P\rightarrow \infty$ , es pot obtenir una precisió arbitrària d'aquest valor.