Problema di Simon

Nella teoria della complessità computazionale e nella computazione quantistica, il problema di Simon è un problema computazionale che può essere risolto in maniera esponenzialmente più veloce su un computer quantistico rispetto a un computer classico (o tradizionale). Il problema di Simon incorpora l'uso di una scatola nera (black box). I problemi con la scatola nera danno agli algoritmi quantistici un vantaggio rispetto agli algoritmi classici.

Il problema in sé è di poco interesse pratico perché ci sono poche situazioni realistiche in cui ci sia bisogno di risolvere il problema di Simon. Tuttavia, il problema è comunque importante perché si può dimostrare che un algoritmo quantistico può risolvere questo problema in modo esponenzialmente più veloce rispetto a un qualsiasi algoritmo classico conosciuto. Questo è il primo esempio di problema computazionale che può essere risolto in un tempo polinomiale su un computer quantistico.

Il problema fu ideato da Daniel Simon nel 1994. Simon mostrò un algoritmo quantistico, spesso detto algoritmo di Simon, che risolve il problema richiedendo esponenzialmente meno tempo computazionale (o più precisamente, chiamate) rispetto al miglior algoritmo classico. Nell'algoritmo di Simon è necessario effettuare un numero lineare di chiamate, mentre l'algoritmo classico ne necessita un numero esponenziale. Questo problema dà una separazione dell'oracolo tra le classi di complessità BPP e BQP, a differenza della separazione data dall'algoritmo di Deutsch-Jozsa, che separa P e EQP. La separazione è esponenziale (relativa a un oracolo) tra la complessità classica e quantistica.

L'algoritmo di Simon fu inoltre l'ispirazione per l'algoritmo di Shor. Entrambi i problemi sono casi particolari del problema del sottogruppo nascosto abeliano, per il quale sono conosciuti algoritmi quantistici efficienti.

Descrizione del problema

Sia data una funzione (implementata da una black box o oracolo) ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{n}}$, che gode della proprietà che per qualche ${\displaystyle s\in \{0,1\}^{n}}$ e per ogni ${\displaystyle x,y\in \{0,1\}^{n}}$,

${\displaystyle f(x)=f(y)}$ se e solo se ${\displaystyle x\oplus y\in \{0^{n},s\}}$ o ${\displaystyle {\displaystyle x=y\oplus s}}$

Lo scopo è identificare s e identificare se ${\displaystyle s=0^{n}}$ o ${\displaystyle s\neq 0^{n}}$ chiamando la funzione.

Qui, ${\displaystyle s=0^{n}}$ classifica una funzione iniettiva (uno-a-uno). Se invece ${\displaystyle s\neq 0^{n}}$ , la funzione è due-a-uno tale che ${\displaystyle {\displaystyle x\oplus y\in \{0^{n},s\}}}$

In altre parole, ${\displaystyle f}$ è una funzione due-a-uno tale che ${\displaystyle f(x)=f(x\oplus s)}$, per ogni ${\displaystyle x\in \{0,1\}^{n}}$ dove ${\displaystyle s\in \{0,1\}^{n}}$ è incognita.

Scopo

Lo scopo del problema è ridurre il numero di chiamate alla black box per determinare s in modo esponenzialmente veloce.

Esempio

Per esempio, se ${\displaystyle n=3}$, allora la funzione seguente è un esempio di una funzione che soddisfa la proprietà già menzionata:

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

In questo caso si ha la soluzione ${\displaystyle s=110}$. Può essere facilmente verificato che ogni output di ${\displaystyle f}$ compare due volte, e che il prodotto XOR bitwise tra le due stringhe di input corrispondenti a un qualsiasi output è pari a ${\displaystyle s=110}$.

Per esempio, le stringhe di input ${\displaystyle 010}$ e ${\displaystyle 100}$ sono entrambi mappati (da ${\displaystyle f}$) allo stesso output ${\displaystyle 000}$, ovvero ${\displaystyle f(010)=000}$ e ${\displaystyle f(100)=000}$. Se si applica XOR a 010 e 100 si ottiene 110, ovvero ${\displaystyle 010\oplus 100=110=s.}$ La stringa ${\displaystyle s=110}$ può anche essere verificata usando stringhe di input 001 e 111 che sono entrambi mappati (da f) alla stessa stringa di input 010. Anche se si applica XOR a 001 e 111, si ottiene 110, ovvero ${\displaystyle 001\oplus 111=110=s}$. Questo dà la stessa soluzione ${\displaystyle s=110}$ risolta prima.

In questo esempio la funzione è di fatto due-a-uno dove ${\displaystyle {\displaystyle s\neq 0^{n}}}$.

Dato che ${\displaystyle x_{2}=s\oplus x_{1}}$, si può riscrivere il coefficiente ${\displaystyle (-1)^{x_{1}\cdot y}+(-1)^{x_{2}\cdot y}}$ come segue:

Difficoltà del problema

Intuitivamente, questo è un problema molto difficile da risolvere in modo "classico". L'intuizione dietro alla difficoltà è ragionevolmente semplice: se si vuole risolvere il problema classicamente, serve trovare due diversi input ${\displaystyle x}$ e ${\displaystyle y}$ per cui ${\displaystyle f(x)=f(y)}$. Non c'è necessariamente una struttura nella funzione ${\displaystyle f}$ che potrebbero aiutare a trovare due input del genere: più nello specifico, è possibile scoprire qualcosa di ${\displaystyle f}$ (o cosa fa) solo quando, per due diversi input si ottiene lo stesso output. In ogni caso, bisognerebbe prendere ${\displaystyle {\displaystyle \Omega ({\sqrt {2^{n}}})}}$ diversi input prima che sia probabile trovare una coppia che viene mappata da ${\displaystyle f}$ allo stesso output, come per il paradosso del compleanno. Siccome, classicamente per trovare s con una certezza del 100% servirebbe controllare fino a ${\displaystyle 2^{n-1}+1}$ input, il problema di Simon cerca di trovare s usando molte meno chiamate del metodo classico.

Panoramica dell'algoritmo

Idea

L'idea dietro all'algoritmo di Simon è "sondare" (o "campionare") un circuito quantistico (si veda la figura sotto) "abbastanza volte" per trovare ${\displaystyle n-1}$ stringhe a n-bit linearmente indipendenti, cioè

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

tali che le seguenti equazioni sono soddisfatte

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

dove ${\displaystyle y_{i}\cdot s}$ è il prodotto scalare modulo 2; vale a dire, ${\displaystyle y_{i}\cdot s=y_{i1}s_{1}\oplus y_{i2}s_{2}\oplus \dots \oplus y_{in}s_{n}}$ dove ${\displaystyle y_{ij},s_{j}\in \{0,1\}}$, per ${\displaystyle i=1,\dots ,n-1}$ e per ${\displaystyle j=1,\dots ,n}$.

Allora, questo sistema lineare contiene ${\displaystyle n-1}$ equazioni lineari in ${\displaystyle n}$ incognite (cioè i bit di ${\displaystyle s\in \{0,1\}^{n}}$), e lo scopo è risolvere per ottenere ${\displaystyle s}$, e ${\displaystyle s}$ è fissato per una data funzione ${\displaystyle f}$. Non c'è sempre una (unica) soluzione.

Circuito quantistico

Circuito quantistico che rappresenta/implementa l'algoritmo di Simon

Il circuito quantistico (in figura) è l'implementazione (e visualizzazione) della parte quantistica dell'algoritmo di Simon.

Per prima cosa si prepara uno stato quantistico di tutti zero (facilmente fattibile). Lo stato ${\displaystyle |0\rangle }$ rappresenta ${\displaystyle |0^{n}\rangle }$ dove ${\displaystyle n}$ è il numero di qubit. Metà di questo stato viene quindi trasformato con una porta di Hadamard. Il risultato è quindi mandato nell'oracolo (o black box, "scatola nera"), che sa come calcolare ${\displaystyle f}$. L'operatore ${\displaystyle U_{f}}$ agisce sui due registri come ${\displaystyle |x\rangle |0^{n}\rangle \rightarrow |x\rangle |f(x)\rangle }$. Dopo di ciò, parte dell'output prodotta dall'oracolo è trasformata usando un'altra trasformata di Hadamard. Infine, viene fatta una misura sul risultante stato quantistico. Durante questa misura si recuperano le stringhe a n bit, ${\displaystyle y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}}$, menzionate nella precedente sezione.

L'algoritmo di Simon può essere pensato come un algoritmo iterativo, che fa uso di un circuito quantistico, seguito da un algoritmo (possibilmente) classico per trovare la soluzione di un sistema lineare di equazioni.

Descrizione dell'algoritmo

Input

L'algoritmo di Simon inizia con l'input ${\displaystyle |0^{n}\rangle \otimes |0^{n}\rangle =|0^{n}\rangle |0^{n}\rangle }$, dove ${\displaystyle |0^{n}\rangle }$ è lo stato quantistico con ${\displaystyle n}$ zeri.

(Il simbolo ${\displaystyle \otimes }$ è il simbolo tipico usato per rappresentare il prodotto tensoriale. Per non ingombrare la notazione, il simbolo ${\displaystyle \otimes }$ viene talvolta omesso: per esempio nella frase precedente, ${\displaystyle |0^{n}\rangle \otimes |0^{n}\rangle }$ è equivalente a ${\displaystyle |0^{n}\rangle |0^{n}\rangle }$. In questa voce, è spesso usato per evitare ambiguità o confusione.)

Esempio

Ad esempio, per ${\displaystyle n=2}$, l'input iniziale è

${\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 trasformazione di Hadamard

Per prima cosa, l'input viene trasformato con una trasformata di Hadamard. Specificamente, la trasformata di Hadamard ${\displaystyle H^{\otimes n}}$ (il prodotto tensoriale può essere applicato anche a matrici) viene applicata ai primi ${\displaystyle n}$ qubit, cioè allo stato "parziale" ${\displaystyle |0^{n}\rangle }$, così lo stato dopo questa operazione risulta essere

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

dove ${\displaystyle x\in \{0,1\}^{n}}$ denota una stringa a n bit (cioè la somma è su tutte le stringhe a n bit). Il termine ${\displaystyle {\frac {1}{\sqrt {2^{n}}}}}$ può essere raccolto fuori dalla sommatoria perché non dipende da ${\displaystyle x}$, e ${\displaystyle {\frac {1}{\sqrt {2^{n}}}}={\frac {1}{2^{\frac {n}{2}}}}}$.

Esempio

Si supponga (ancora) ${\displaystyle n=2}$, allora l'input è ${\displaystyle |0000\rangle }$ e la trasformata di Hadamard ${\displaystyle H^{\otimes 2}}$ è

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

Se si applica ${\displaystyle H^{\otimes 2}}$ al primo ${\displaystyle |00\rangle }$, cioè allo stato

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

si ottiene

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

Per ottenere lo stato composto, si fa il prodotto tensore di ${\displaystyle H^{\otimes 2}|00\rangle }$ con ${\displaystyle |00\rangle }$, ossia

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

Oracolo

Si chiama ora l'oracolo o la black box (${\displaystyle U_{f}}$ in figura) per calcolare la funzione ${\displaystyle f}$ sull'input trasformato ${\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)}$, per ottenere lo stato

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

Seconda trasformazione di Hadamard

Si applica poi nuovamente la trasformata di ${\displaystyle H^{\otimes n}}$ agli stati dei primi ${\displaystyle n}$ qubit dello stato ${\displaystyle |\Psi \rangle '}$, e si ha

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

dove ${\displaystyle (-1)^{x\cdot y}}$ può essere o ${\displaystyle -1}$ o ${\displaystyle 1}$, a seconda di ${\displaystyle x\cdot y=x_{1}y_{1}+\dots +x_{n}y_{n}}$, dove ${\displaystyle x_{i},y_{i}\in \{0,1\}}$, per ${\displaystyle i=1,\dots ,n}$. Quindi, ad esempio, se ${\displaystyle x=101}$ e ${\displaystyle y=111}$, allora ${\displaystyle x\cdot y=1*1+0*1+1*1=2}$, che è pari, quindi in questo caso, ${\displaystyle (-1)^{x\cdot y}=(-1)^{1*1+0*1+1*1}=(-1)^{2}=1}$; ${\displaystyle {x\cdot y}}$ è sempre un numero non negativo.

Ora si riscriva lo stato

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

come segue:

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

Misura

Dopo aver effettuato tutte le operazioni di cui sopra, bisogna effettua una misura.

Ci sono ora due casi possibili da analizzare separatamente

• ${\displaystyle x\oplus y=0^{n}}$ o
• ${\displaystyle x\oplus y=s}$, con ${\displaystyle s\neq 0^{n}}$.

Primo caso

Si analizzi il caso in cui ${\displaystyle x\oplus y=0^{n}}$, il che significa che ${\displaystyle f}$ è uno-a-uno (iniettiva).

Lo stato prima della misura è

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

Ora, la probabilità che la misura dia una qualsiasi stringa ${\displaystyle y\in \{0,1\}^{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}}}}$

Questo segue dal fatto che

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

perché i due vettori differiscono solo nell'ordinamento delle loro componenti, dato che ${\displaystyle f}$ è iniettiva.

Il valore del membro di destra vale semplicemente

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

Pertanto, quando ${\displaystyle x\oplus y=0^{n}}$, l'esito della misura è semplicemente una stringa a n bit uniformemente distribuita.

Secondo caso

Si analizzi ora il caso in cui ${\displaystyle x\oplus y=s}$, dove ${\displaystyle s\neq 0^{n}}$. In questo caso, ${\displaystyle f}$ è una funzione due-a-uno, cioè ci sono due input che vengono mappati da ${\displaystyle f}$ allo stesso output.

L'analisi effettuata nel prima è ancora valida: la probabilità di misurare una qualsiasi stringa ${\displaystyle y\in \{0,1\}^{n}}$ può essere ancora rappresentata da

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

Tuttavia, in questo secondo caso, è necessario capire quale sia il valore di ${\displaystyle p_{y}}$.

Sia ${\displaystyle A=f(\{0,1\}^{n})}$, l'insieme immagine di ${\displaystyle f}$. Sia ${\displaystyle z\in A}$ (un certo output della funzione), allora per ogni ${\displaystyle x_{1}\in \{0,1\}^{n}}$, c'è una e una sola ${\displaystyle x_{2}\in \{0,1\}^{n}}$, tale che ${\displaystyle f(x_{1})=f(x_{2})=z}$; inoltre si ha che ${\displaystyle x_{1}\oplus x_{2}=s}$, che è equivalente a ${\displaystyle x_{2}=s\oplus x_{1}}$.

Quindi, si ha

${\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\in A}\left(((-1)^{x_{1}\cdot y}+(-1)^{x_{2}\cdot y})\left|z\right\rangle \right){\Bigg \|}}^{2}}$

Dato che ${\displaystyle (x_{1}\oplus s)\cdot y=(x_{1}\cdot y)\oplus (s\cdot y)}$, si può ancora riscrivere come

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

Ora, se ${\displaystyle y\cdot s=y_{1}s_{1}+\dots +y_{n}s_{n}}$ è dispari, allora ${\displaystyle (-1)^{y\cdot s}=-1}$. Allora,

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

In definitiva, ${\displaystyle p_{y}}$ può essere scritta come

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

Numero dispari

Se, invece, ${\displaystyle y\cdot s}$ è pari, allora ${\displaystyle (-1)^{y\cdot s}=1}$. In questo caso,

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

Di conseguenza si ha

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

Dato che ${\displaystyle p_{y}=0}$, non si misurerà mai nessuna stringa ${\displaystyle y\in \{0,1\}^{n}}$. Si ha interferenza distruttiva.

Numero pari

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

Quindi si ha

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

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

${\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}={\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 ${\displaystyle x\oplus y=0^{n}}$, i risultati della misura sono ${\displaystyle y\in \{0,1\}^{n}}$ con probabilità ${\displaystyle p_{y}={\frac {1}{2^{n}}}}$

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

${\displaystyle 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 ${\displaystyle y\in \{0,1\}^{n}}$ che soddisfa ${\displaystyle s\cdot y=0}$, e la distribuzione è uniforme su tutte le stringhe che soddisfano questa condizione.

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

${\displaystyle {\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 ${\displaystyle n-1}$ equazioni lineari in ${\displaystyle n}$ incognite (cioè i bit di ${\displaystyle s}$), e lo scopo è risolverlo per ottenere ${\displaystyle s}$. Si noti che ognuna delle ${\displaystyle 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 ${\displaystyle s}$ se ${\displaystyle y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}}$ sono linearmente indipendenti. La probabilità che ${\displaystyle y_{1},y_{2},\dots ,y_{n-1}}$ siano linearmente indipendente è almeno

${\displaystyle \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 ${\displaystyle s'\neq 0^{n}}$ e verificare che ${\displaystyle f(0^{n})=f(s')}$. Se ${\displaystyle f(0^{n})=f(s')}$, allora ${\displaystyle s=s'}$ e il problema è risolto. Se ${\displaystyle f(0^{n})\neq f(s')}$, deve essere ${\displaystyle s=0^{n}}$. Se così non fosse, l'unica soluzione non nulla delle equazioni lineari sarebbe stata ${\displaystyle s}$). Ad ogni modo, con l'indipendenza lineare delle equazioni, si può risolvere il problema.

Complessità

L'algoritmo di Simon necessita di ${\displaystyle O(n)}$ chiamate all'oracolo, mentre un algoritmo classico ne necessita almeno ${\displaystyle \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 ${\displaystyle \Omega (n)}$ chiamate.^[1][2]

Note

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.