Algoritmo di Deutsch

L'algoritmo di Deutsch risolve il problema della parità per il caso speciale che $n = 1.$ Nel contesto dell'informatica quantistica questo problema viene talvolta indicato come problema di Deutsch, e in questa lezione seguiremo questa nomenclatura.

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

La prima e l'ultima di queste funzioni sono costanti, mentre le due centrali sono bilanciate, il che significa che i due possibili valori di uscita della funzione si verificano lo stesso numero di volte quando si passa da un ingresso all'altro. Il problema di Deutsch consiste nel determinare a quale delle due categorie appartiene la funzione di ingresso: costante o bilanciata.

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

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

Ogni algoritmo di interrogazione classica che risolva correttamente questo problema deve interrogare entrambi i bit: $f(0)$ e $f(1).$ Se apprendiamo che $f(1) = 1,$, ad esempio, la risposta potrebbe ancora essere $0$ o $1,$ a seconda che si tratti di $f(0) = 1$ o $f(0) = 0,$ rispettivamente. Ogni altro caso è simile: conoscere solo uno dei due bit non fornisce alcuna informazione sulla loro parità. Quindi, il circuito booleano descritto nella sezione precedente è il massimo 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 utilizzando una singola interrogazione, fornendo quindi un vantaggio quantificabile della computazione quantistica rispetto a quella classica. Si tratta forse di un vantaggio modesto - una sola interrogazione 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, ripercorriamo l'azione del circuito di cui sopra e identifichiamo gli stati dei qubit nei momenti suggeriti dalla 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

(Come sempre, seguiamo la convenzione di ordinamento dei qubit di Qiskit, che pone il qubit superiore a destra e quello inferiore a sinistra) Può sembrare poco intuitivo scrivere questo prodotto di stato parzialmente distribuito (lasciando gli stati del qubit 1 sfalsati), ma questo renderà le nostre 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/più a destra è sottoposto a XOR sul qubit in basso/più a sinistra, che trasforma $\vert \pi_1\rangle$ nello stato

Possiamo semplificare questa espressione osservando che la formula

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

In alternativa, possiamo esprimere $\vert\pi_2\rangle$ in questo modo:

È appena successo qualcosa di interessante! Sebbene l'azione del gate $U_f$ sugli stati base standard lasci il qubit in alto a destra da solo e faccia lo XOR del valore della funzione sul qubit in basso a sinistra, in questo caso vediamo che lo stato del qubit in alto a destra è cambiato (in generale), mentre lo stato del qubit in basso a sinistra rimane lo stesso - in particolare si trova nello stato $\vert - \rangle$ prima e dopo l'esecuzione del gate $U_f$. Questo fenomeno è noto come contraccolpo di fase e ne parleremo più avanti.

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

Si noti che in questa espressione abbiamo $f(0) \oplus f(1)$ nell'esponente di $-1$ invece di $f(1) - f(0),$, come ci si potrebbe aspettare 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 superiore si ottiene lo stato

che porta al risultato corretto con probabilità $1$ quando viene misurato il qubit destro/superiore.

Ulteriori osservazioni sul contraccolpo di fase

Prima di proseguire, analizziamo l'analisi di cui sopra da un'angolazione leggermente diversa che può far luce sul fenomeno del contraccolpo di fase.

Innanzitutto, si noti che la formula seguente funziona per tutte le scelte di bit $b,c\in\Sigma.$

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

Utilizzando questa formula, vediamo che

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

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

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

Parleremo di autovettori e autovalori in modo più dettagliato nella prossima lezione sulla stima di fase e sulla fattorizzazione, dove il fenomeno del contraccolpo di fase viene generalizzato ad altre operazioni unitarie.

Tenendo presente che gli scalari fluttuano 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:

Implementazione in Qiskit

Vediamo ora come implementare l'algoritmo di Deutsch in Qiskit. Inizieremo con un controllo della versione e poi eseguiremo le importazioni necessarie solo per questa implementazione. Per le implementazioni di altri algoritmi che seguiranno, eseguiremo le importazioni necessarie separatamente, per una maggiore modularità.

from qiskit import __version__

print(__version__)

Output:

2.1.1

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

Per prima cosa definiremo un circuito quantistico che implementa una porta di interrogazione per una delle quattro funzioni $f_1,$ $f_2,$ $f_3,$ o $f_4$ da un bit a un bit descritte in precedenza. Come abbiamo già detto, l'implementazione delle porte di interrogazione non fa parte dell'algoritmo di Deutsch; qui stiamo essenzialmente mostrando un modo per preparare l'input, sotto forma di implementazione circuitale di una porta di interrogazione.

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 l'aspetto di ciascun circuito utilizzando il metodo draw . Ecco il circuito della funzione $f_3.$

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

Output:

Successivamente creeremo il circuito quantistico vero e proprio per l'algoritmo di Deutsch, sostituendo la porta di interrogazione con un'implementazione del circuito quantistico 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 della porta di interrogazione 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 si presenta il circuito utilizzando il metodo draw .

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

Output:

Infine, creeremo una funzione che esegua una volta il circuito precedentemente definito e fornisca il risultato appropriato: "costante" o "bilanciato"

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))

Output:

'balanced'