L'algoritmo di Deutsch

L'algoritmo di Deutsch risolve il problema della parità per il caso speciale in cui $n = 1.$ In ambito di calcolo quantistico questo problema viene talvolta chiamato problema di Deutsch, e seguiremo questa nomenclatura in questa lezione.

Per essere precisi, l'input è rappresentato da una funzione $f:\Sigma \rightarrow \Sigma$ da un bit a un bit. Esistono quattro funzioni di questo tipo:

$$\rule[-10mm]{0mm}{10mm} \begin{array}{c|c} a & f_1(a)\\ \hline 0 & 0\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_2(a)\\ \hline 0 & 0\\ 1 & 1 \end{array} \qquad \begin{array}{c|c} a & f_3(a)\\ \hline 0 & 1\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_4(a)\\ \hline 0 & 1\\ 1 & 1 \end{array}$$

La prima e l'ultima di queste funzioni sono costanti, mentre le due centrali sono bilanciate, nel senso che i due possibili valori di output della funzione compaiono lo stesso numero di volte al variare degli input. Il problema di Deutsch consiste nel determinare a quale di queste due categorie appartiene la funzione di input: costante o bilanciata.

Il problema di Deutsch

Input: una funzione $f:\{0,1\}\rightarrow\{0,1\}$
Output: $0$ se $f$ è costante, $1$ se $f$ è bilanciata

Se interpretiamo la funzione di input $f$ nel problema di Deutsch come un accesso casuale a una stringa, stiamo considerando una stringa di due bit: $f(0)f(1).$

$$\begin{array}{cc} \mathsf{function} & \mathsf{string}\\ \hline f_1 & 00 \\ f_2 & 01 \\ f_3 & 10 \\ f_4 & 11 \end{array}$$

Visto in questo modo, il problema di Deutsch consiste nel calcolare la parità (o, equivalentemente, lo XOR esclusivo) dei due bit.

Ogni algoritmo di query classico che risolve correttamente questo problema deve interrogare entrambi i bit: $f(0)$ e $f(1).$ Se scopriamo che $f(1) = 1,$ per esempio, la risposta potrebbe comunque essere $0$ o $1,$ a seconda che $f(0) = 1$ oppure $f(0) = 0,$ rispettivamente. Tutti gli altri casi sono analoghi: conoscere soltanto uno dei due bit non fornisce alcuna informazione sulla loro parità. Quindi, il circuito booleano descritto nella sezione precedente è il meglio che possiamo fare in termini di numero di query necessarie per risolvere questo problema.

Descrizione del circuito quantistico

L'algoritmo di Deutsch risolve il problema di Deutsch con una singola query, offrendo così un vantaggio quantificabile del calcolo quantistico rispetto a quello classico. Può sembrare un vantaggio modesto — una query invece di due — ma da qualche parte bisogna pur cominciare. I progressi scientifici hanno talvolta origini apparentemente umili.

Ecco un circuito quantistico che descrive l'algoritmo di Deutsch:

Analisi

Per analizzare l'algoritmo di Deutsch, percorreremo passo dopo passo l'azione del circuito qui sopra e identificheremo gli stati dei qubit nei momenti suggeriti da questa figura:

Lo stato iniziale è $\vert 1\rangle \vert 0 \rangle,$ e le due operazioni di Hadamard sul lato sinistro del circuito trasformano questo stato in

$$\vert \pi_1 \rangle = \vert - \rangle \vert + \rangle = \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 0\rangle + \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 1\rangle.$$

(Come sempre, seguiamo la convenzione di ordinamento dei qubit di Qiskit, che colloca il qubit in alto a destra e quello in basso a sinistra.) Potrebbe sembrare poco intuitivo scrivere questo stato prodotto parzialmente distribuito (lasciando fattorizzati gli stati del qubit 1), ma questo renderà le espressioni successive più compatte.

Successivamente viene eseguito il gate $U_f.$ Secondo la definizione del gate $U_f,$ il valore della funzione $f$ per lo stato classico del qubit in alto/a destra viene applicato tramite XOR al qubit in basso/a sinistra, trasformando $\vert \pi_1\rangle$ nello stato

$$\vert \pi_2 \rangle = \frac{1}{2} \bigl( \vert 0 \oplus f(0) \rangle - \vert 1 \oplus f(0) \rangle \bigr) \vert 0 \rangle + \frac{1}{2} \bigl( \vert 0 \oplus f(1) \rangle - \vert 1 \oplus f(1) \rangle \bigr) \vert 1 \rangle.$$

Possiamo semplificare questa espressione osservando che la formula

$$\vert 0 \oplus a\rangle - \vert 1 \oplus a\rangle = (-1)^a \bigl( \vert 0\rangle - \vert 1\rangle \bigr)$$

vale per entrambi i possibili valori $a\in\Sigma.$ Più esplicitamente, i due casi sono i seguenti.

$$\begin{aligned} \vert 0 \oplus 0\rangle - \vert 1 \oplus 0\rangle & = \vert 0 \rangle - \vert 1 \rangle = (-1)^0 \bigl( \vert 0\rangle - \vert 1\rangle \bigr)\\ \vert 0 \oplus 1\rangle - \vert 1 \oplus 1\rangle & = \vert 1 \rangle - \vert 0\rangle = (-1)^1 \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \end{aligned}$$

Quindi, possiamo esprimere $\vert\pi_2\rangle$ in modo alternativo così:

$$\begin{aligned} \vert\pi_2\rangle & = \frac{1}{2} (-1)^{f(0)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 0 \rangle + \frac{1}{2} (-1)^{f(1)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 1 \rangle \\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

Qualcosa di interessante è appena accaduto! Sebbene l'azione del gate $U_f$ sugli stati della base standard lasci invariato il qubit in alto/a destra e applichi il valore della funzione tramite XOR al qubit in basso/a sinistra, qui vediamo che lo stato del qubit in alto/a destra è cambiato (in generale), mentre lo stato del qubit in basso/a sinistra rimane invariato — trovandosi nello stato $\vert - \rangle$ sia prima che dopo l'esecuzione del gate $U_f.$ Questo fenomeno è noto come phase kickback, e ne parleremo più approfonditamente a breve.

Con un'ultima semplificazione, che consiste nel portare fuori dalla somma il fattore $(-1)^{f(0)},$ otteniamo questa espressione dello stato $\vert\pi_2\rangle$:

$$\begin{aligned} \vert\pi_2\rangle & = (-1)^{f(0)} \vert - \rangle \biggl( \frac{\vert 0\rangle + (-1)^{f(0) \oplus f(1)} \vert 1\rangle}{\sqrt{2}}\biggr) \\ & = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert + \rangle & \text{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert - \rangle & \text{if $f(0) \oplus f(1) = 1$}. \end{cases} \end{aligned}$$

Nota che in questa espressione abbiamo $f(0) \oplus f(1)$ nell'esponente di $-1$ invece di $f(1) - f(0),$ che è ciò che potremmo aspettarci da un punto di vista puramente algebrico, ma otteniamo lo stesso risultato in entrambi i casi. Questo perché il valore $(-1)^k$ per qualsiasi intero $k$ dipende solo dal fatto che $k$ sia pari o dispari.

Applicando il gate di Hadamard finale al qubit in alto otteniamo lo stato

$$\vert \pi_3 \rangle = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert 0 \rangle & \text{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert 1 \rangle & \text{if $f(0) \oplus f(1) = 1$}, \end{cases}$$

che porta al risultato corretto con probabilità $1$ quando il qubit a destra/in alto viene misurato.

Ulteriori osservazioni sul phase kickback

Prima di proseguire, analizziamo l'analisi precedente da una prospettiva leggermente diversa, che potrebbe fare luce sul fenomeno del phase kickback.

Per prima cosa, nota che la seguente formula vale per tutte le scelte di bit $b,c\in\Sigma.$

$$\vert b \oplus c\rangle = X^c \vert b \rangle$$

Questo può essere verificato controllando i due possibili valori $c = 0$ e $c = 1$:

$$\begin{aligned} \vert b \oplus 0 \rangle & = \vert b\rangle = \mathbb{I} \vert b \rangle = X^0 \vert b \rangle\\ \vert b \oplus 1 \rangle & = \vert \neg b\rangle = X \vert b \rangle = X^1 \vert b \rangle. \end{aligned}$$

Usando questa formula, vediamo che

$$U_f \bigl(\vert b\rangle \vert a \rangle\bigr) = \vert b \oplus f(a) \rangle \vert a \rangle = \bigl(X^{f(a)}\vert b \rangle\bigr) \vert a \rangle$$

per ogni scelta di bit $a,b\in\Sigma.$ Poiché questa formula è vera per $b=0$ e $b=1,$ vediamo per linearità che

$$U_f \bigl( \vert \psi \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)}\vert \psi \rangle\bigr) \vert a \rangle$$

per tutti i vettori di stato di un qubit $\vert \psi\rangle,$ e quindi

$$U_f \bigl( \vert - \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)} \vert - \rangle \bigr) \vert a \rangle = (-1)^{f(a)} \vert - \rangle \vert a \rangle.$$

La chiave che rende tutto questo possibile è che $X\vert - \rangle = - \vert - \rangle.$ In termini matematici, il vettore $\vert - \rangle$ è un autovettore della matrice $X$ con autovalore $-1.$

Discuteremo autovettori e autovalori in modo più dettagliato nella prossima lezione sulla stima della fase e la fattorizzazione, dove il fenomeno del phase kickback viene generalizzato ad altre operazioni unitarie.

Tenendo presente che gli scalari si propagano liberamente attraverso i prodotti tensoriali, troviamo un modo alternativo di ragionare su come l'operazione $U_f$ trasforma $\vert \pi_1\rangle$ in $\vert \pi_2\rangle$ nell'analisi precedente:

$$\begin{aligned} \vert \pi_2 \rangle & = U_f \bigl( \vert - \rangle \vert + \rangle \bigr)\\ & = \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 0\rangle \bigr) + \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 1\rangle \bigr)\\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

Implementazione in Qiskit

Vediamo ora come implementare l'algoritmo di Deutsch in Qiskit. Inizieremo con una verifica della versione e poi eseguiremo le importazioni necessarie esclusivamente per questa implementazione. Per le implementazioni degli altri algoritmi che seguono, eseguiremo le importazioni necessarie separatamente, a favore di una maggiore modularità.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-aer

from qiskit import __version__

print(__version__)

2.1.1

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

Per prima cosa definiremo un circuito quantistico che implementa un gate di query per una delle quattro funzioni $f_1,$ $f_2,$ $f_3,$ o $f_4$ da un bit a un bit descritte in precedenza. Come già accennato, l'implementazione dei gate di query non è propriamente parte dell'algoritmo di Deutsch in sé; qui stiamo essenzialmente mostrando un modo per preparare l'input, sotto forma di un'implementazione circuitale di un gate di query.

def deutsch_function(case: int):
    # This function generates a quantum circuit for one of the 4 functions
    # from one bit to one bit

    if case not in [1, 2, 3, 4]:
        raise ValueError("`case` must be 1, 2, 3, or 4.")

    f = QuantumCircuit(2)
    if case in [2, 3]:
        f.cx(0, 1)
    if case in [3, 4]:
        f.x(1)
    return f

Possiamo vedere come appare ogni circuito usando il metodo draw. Ecco il circuito per la funzione $f_3.$

display(deutsch_function(3).draw(output="mpl"))

Successivamente creeremo il circuito quantistico vero e proprio per l'algoritmo di Deutsch, sostituendo il gate di query con un'implementazione circuitale fornita come argomento. A breve inseriremo uno dei quattro circuiti definiti dalla funzione deutsch_function che abbiamo definito in precedenza. Le barriere sono incluse per mostrare la separazione visiva tra l'implementazione del gate di query e il resto del circuito.

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in Deutsch's algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)

    qc.x(n)
    qc.h(range(n + 1))

    qc.barrier()
    qc.compose(function, inplace=True)
    qc.barrier()

    qc.h(range(n))
    qc.measure(range(n), range(n))

    return qc

Anche in questo caso possiamo vedere come appare il circuito usando il metodo draw.

display(compile_circuit(deutsch_function(3)).draw(output="mpl"))

Infine, creeremo una funzione che esegue una volta il circuito definito in precedenza e restituisce il risultato appropriato: "constant" o "balanced."

def deutsch_algorithm(function: QuantumCircuit):
    # Determine if a one-bit function is constant or balanced.

    qc = compile_circuit(function)

    result = AerSimulator().run(qc, shots=1, memory=True).result()
    measurements = result.get_memory()
    if measurements[0] == "0":
        return "constant"
    return "balanced"

Ora possiamo eseguire l'algoritmo di Deutsch su una qualsiasi delle quattro funzioni definite sopra.

f = deutsch_function(3)
display(deutsch_algorithm(f))

'balanced'