Algorisme Deutsch–Jozsa

L'algoritme de Deutsch–Jozsa és un algorisme quàntic determinista proposat per David Deutsch i Richard Jozsa el 1992 amb millores de Richard Cleve, Artur Ekert, Chiara Macchiavello i Michele Mosca el 1998. Encara que de poca utilitat pràctica, és un dels primers exemples d'algorisme quàntic que és exponencialment més ràpid que qualsevol algorisme clàssic determinista possible.

El problema de Deutsch–Jozsa està dissenyat específicament per ser fàcil per a un algorisme quàntic i difícil per a qualsevol algorisme clàssic determinista. És un problema de caixa negra que es pot resoldre de manera eficient mitjançant un ordinador quàntic sense error, mentre que un ordinador clàssic determinista necessitaria un nombre exponencial de consultes a la caixa negra per resoldre el problema. Més formalment, produeix un oracle relatiu al qual EQP, la classe de problemes que es poden resoldre exactament en temps polinomial en un ordinador quàntic, i P són diferents.

Com que el problema és fàcil de resoldre en un ordinador clàssic probabilístic, no produeix una separació d'oracle amb BPP, la classe de problemes que es poden resoldre amb un error acotat en temps polinomial en un ordinador clàssic probabilístic. El problema de Simon és un exemple d'un problema que produeix una separació oracle entre BQP i BPP.

Una imatge de l'algoritme Deutsch–Jozsa escrit al Quantum Composer d'IBM

Declaració del problema

En el problema de Deutsch–Jozsa, se'ns dóna una computadora quàntica de caixa negra coneguda com a oracle que implementa alguna funció:

$f\colon \{0,1\}^{n}\rightarrow \{0,1\}$

La funció pren valors binaris de n bits com a entrada i produeix un 0 o un 1 com a sortida per a cada valor. Se'ns promet que la funció és constant (0 a totes les entrades o 1 a totes les entrades) o equilibrada (1 per exactament la meitat del domini d'entrada i 0 per a l'altra meitat). Llavors la tasca és determinar si $f$ és constant o equilibrada mitjançant l'ús de l'oracle.

Solució clàssica

Per a un algorisme determinista convencional on $n$ és el nombre de bits, $2^{n-1}+1$ avaluacions de $f$ serà necessari en el pitjor dels casos. Per demostrar-ho $f$ és constant, s'ha d'avaluar una mica més de la meitat del conjunt d'entrades i trobar que les seves sortides són idèntiques (perquè es garanteix que la funció sigui equilibrada o constant, no entremig). El millor dels casos es produeix quan la funció està equilibrada i els dos primers valors de sortida són diferents. Per a un algorisme aleatoritzat convencional, una constant $k$ avaluacions de la funció n'hi ha prou per produir la resposta correcta amb una probabilitat alta (fallir amb probabilitat $\epsilon \leq 1/2^{k}$ amb $k\geq 1$ ). No obstant això, $k=2^{n-1}+1$ encara calen avaluacions si volem una resposta que no tingui possibilitat d'error. L'algorisme quàntic de Deutsch-Jozsa produeix una resposta que sempre és correcta amb una sola avaluació $f$.

Història

L'algorisme de Deutsch–Jozsa generalitza el treball anterior (1985) de David Deutsch, que va proporcionar una solució per al cas senzill en què $n=1$. Concretament, donada una funció booleana l'entrada de la qual és d'un bit, $f:\{0,1\}\rightarrow \{0,1\}$, és constant?

L'algoritme, tal com Deutsch l'havia proposat originalment, no era determinista. L'algorisme va tenir èxit amb una probabilitat de la meitat. El 1992, Deutsch i Jozsa van produir un algorisme determinista que es va generalitzar a una funció que pren $n$ bits per a la seva entrada. A diferència de l'algorisme de Deutsch, aquest algorisme requeria dues avaluacions de funcions en lloc d'una sola.

Cleve et al. van fer més millores a l'algoritme de Deutsch-Jozsa, donant lloc a un algorisme que és alhora determinista i només requereix una única consulta de $f$. Aquest algorisme encara es coneix com algorisme Deutsch-Jozsa en honor a les tècniques innovadores que van emprar.

Algoritme

Perquè funcioni l'algoritme Deutsch–Jozsa, la informàtica oracle $f(x)$ des de $x$ ha de ser un oracle quàntic que no decohereix $x$. Tampoc n'ha de fer una còpia $x$, perquè això violaria el teorema de no clonació.

Circuit quàntic de l'algoritme de Deutsch-Jozsa

L'algorisme comença amb el $n+1$ estat de bits $|0\rangle ^{\otimes n}|1\rangle$. És a dir, els primers n bits estan cadascun a l'estat $|0\rangle$ i la part final és $|1\rangle$. S'aplica una porta Hadamard a cada bit per obtenir l'estat

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

on $x$ corre per sobre de tot $n$ -cadenes de bits. Tenim la funció $f$ implementat com un oracle quàntic. L'oracle mapa el seu estat d'entrada $|x\rangle |y\rangle$ a $|x\rangle |y\oplus f(x)\rangle$, on $\oplus$ indica l'addició mòdul 2. Aplicant l'oracle quàntic dóna;

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

Per a cadascun $x,f(x)$ és 0 o 1. Provant aquestes dues possibilitats, veiem que l'estat anterior és igual

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

En aquest punt l'últim qubit ${\frac {|0\rangle -|1\rangle }{\sqrt {2}}}$ es pot ignorar i queda el següent:

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

A continuació, farem que el qubit passi per una porta Hadamard

$H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle$

( $j\cdot k=j_{0}k_{0}\oplus j_{1}k_{1}\oplus \cdots \oplus j_{n-1}k_{n-1}$ és la suma del producte bit a bit, on $\oplus$ és la suma mòdul 2) sobre el primer registre a obtenir

${\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]=\sum _{y=0}^{2^{n}-1}\left[{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle$

A partir d'això, podem veure que la probabilitat d'un estat $k$ a mesurar és

$\left|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot k}\right|^{2}$

La probabilitat de mesurar $k=0$, corresponent a $|0\rangle ^{\otimes n}$, és

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

que valora a 1 si $f(x)$ és constant (interferència constructiva) i 0 si $f(x)$ és equilibrat (interferència destructiva). És a dir, la mesura final serà $|0\rangle ^{\otimes n}$ (tots zeros) si i només si $f(x)$ és constant i donarà algun altre estat si $f(x)$ està equilibrat.