Algoritmo di Deutsch-Jozsa

L'algoritmo di Deutsch-Jozsa è un algoritmo quantistico deterministico proposto da David Deutsch e Richard Jozsa nel 1992 e successivamente migliorato da Richard Cleve, Artur Ekert, Chiara Macchiavello, e Michele Mosca nel 1998. Sebbene sia di scarso interesse pratico, è uno dei primi esempi di algoritmi quantistici ad essere esponenzialmente più veloce di un qualsiasi algoritmo deterministico classico.

Enunciato del problema

Nel problema di Deutsch-Jozsa, viene data una scatola nera, detta oracolo che implementa una certa funzione $f\colon \{0,1\}^{n}\rightarrow \{0,1\}$. La funzione prende valori binari a n cifre e produce come output o 0 o 1 per ciascuno di questi valori. La funzione è definita costante (l'output è sempre 0 o sempre 1) o bilanciata (dà 1 per la metà degli input e 0 per l'altra metà). Il compito è quindi di determinare se $f$ è costante o bilanciata.

Motivazione

Questo problema è stato specificamente progettato per essere facile per un algoritmo quantistico e difficile per un qualsiasi algoritmo classico deterministico. La motivazione è quella di mostrare un problema con scatola nera che può essere risolto efficientemente senza errori da un computer quantistico, mentre un computer classico deterministico avrebbe bisogno di un gran numero di chiamate all'oracolo per risolverlo. In termini formali, dà un oracolo relativamente al quale EQP, la classe di problemi risolvibili esattamente e in tempo polinomiale su un computer quantistico, e P sono diverse.

Siccome il problema è facile da risolvere per un computer classico probabilistico, non c'è una separazione degli oracoli con BPP, la classe di problemi risolvibili con errore limitato in tempo polinomiale su computer classico probabilistico. Un esempio di problema che dà una separazione degli oracoli tra la BQP e la BPP è il problema di Simon.

Soluzione classica

Per un algoritmo deterministico convenzionale con n numero di bit, saranno necessarie $2^{n-1}+1$ valutazioni di $f$ nel caso peggiore. Per dimostrare che $f$ è costante, va calcolata la metà più uno degli input e i loro output devono essere identici (ricordando che la funzione è sicuramente o costante o bilanciata). Il caso migliore prevede 2 valutazioni e avviene quando la funzione è bilanciata e i due output sono diversi. Per un convenzionale algoritmo randomizzato, $k$ valutazioni bastano per produrre la risposta esatta con alta probabilità (fallimento con probabilità $\epsilon \leq 1/2^{k}$ dove $k\geq 1$).Tuttavia, $k=2^{n-1}+1$ valutazioni sono sempre necessarie se si cerca una risposta certamente esatta. L'algoritmo quantistico di Deutsch-Jozsa dà una risposta certamente esatta dopo una singola valutazione di $f$.

Storia

L'algoritmo di Deutsch–Jozsa generalizza un precedente lavoro di David Deutsch (nel 1985), che forniva una soluzione per il caso semplice in cui $n=1$. Nello specifico si ha una funzione booleana il cui input è 1 bit, $f:\{0,1\}\rightarrow \{0,1\}$ e ci si chiede se è costante.

L'algoritmo proposto in origine da Deutsch non era, in realtà, deterministico. Aveva successo con una probabilità del 50%. Nel 1992, Deutsch e Jozsa formularono un algoritmo deterministico che si generalizzava a una funzione che prende $n$ bit, ma necessitava due valutazioni della funzione invece di una sola.

Cleve et al. fecero ulteriori migliorie, che portarono a un algoritmo deterministico che necessitava una sola chiamata di $f$. Questo algoritmo si chiama comunque di Deutsch–Jozsa in onore delle innovative tecniche che impiegarono.

Algoritmo

Affinché l'algoritmo funzioni, l'oracolo che calcola $f(x)$ da $x$ non deve collassare $x$. Non deve inoltre lasciare copie di $x$ dopo la chiamata dell'oracolo.

Il circuito quantistico dell'algoritmo di Deutsch-Jozsa

L'algoritmo comincia con lo stato a $n+1$ bit $|0\rangle ^{\otimes n}|1\rangle$: i primi n bit sono nello stato $|0\rangle$ e l'ultimo è in $|1\rangle$. Viene applicata una porta di Hadamard a ogni bit per ottenere lo stato

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

Ora si applica la funzione $f$ implementata come oracolo. L'oracolo mappa lo stato $|x\rangle |y\rangle$ a $|x\rangle |y\oplus f(x)\rangle$, dove $\oplus$ è l'addizione modulo 2. Applicare l'oracolo dà

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

Per ogni $x,f(x)$ è 0 o 1. Tenendo conto di queste due possibilità, lo stato risulta uguale a

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

A questo punto l'ultimo qubit ${\frac {|0\rangle -|1\rangle }{\sqrt {2}}}$ può essere ignorato, e quindi rimane:

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

Si applica una porta di Hadamard a ogni qubit per ottenere

${\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$

dove $x\cdot y=x_{0}y_{0}\oplus x_{1}y_{1}\oplus \cdots \oplus x_{n-1}y_{n-1}$ è la somma è la prodotto bit-a-bit.

Infine, si esamini la probabilità di misurare $|0\rangle ^{\otimes n}$,

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

che equivale a 1 se $f(x)$ è costante (interferenza costruttiva) e 0 se $f(x)$ è bilanciata (interferenza distruttiva). In altre parole, la misura darà $|0\rangle ^{\otimes n}$ (cioè tutti zero) se $f(x)$ è costante e darà un qualsiasi altro stato se $f(x)$ è bilanciata.

Algoritmo di Deutsch

L'algoritmo di Deutsch è un caso particolare di questo algoritmo. Bisogna verificare la condizione $f(0)=f(1)$. Equivale a controllare $f(0)\oplus f(1)$ (dove $\oplus$ è l'addizione modulo 2, che può essere vista come una porta XOR quantistica implementata come porta NOT controllata), se la somma è nulla, allora $f$ è costante, altrimenti non lo è.

Si comincia dallo stato $|0\rangle |1\rangle$ e si applica una porta di Hadamard a ogni qubit. Questo dà

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

Si applica l'oracolo che mappa $|x\rangle |y\rangle$ in $|x\rangle |f(x)\oplus y\rangle$. Applicare questa funzione allo stato attuale 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 ))$

$={\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 ).$

Ignorando l'ultimo bit e la fase globale, si ha lo stato

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

Applicando nuovamente la porta di Hadamard si ottiene

${\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 ).$

$f(0)\oplus f(1)=0$ se e solo se si misura $|0\rangle$ e $f(0)\oplus f(1)=1$ se e solo se si misura $|1\rangle$. Quindi si sa con certezza se $f(x)$ è costante o bilanciata.

Collegamenti esterni

• Lezione di Deutsch sull'algoritmo di Deutsch-Jozsa, su quiprocone.org.