Computazioni classiche su computer quantistici

Ora rivolgeremo la nostra attenzione all'implementazione di algoritmi classici su computer quantistici. Vedremo che qualsiasi computazione eseguibile con un circuito booleano classico può essere eseguita anche da un circuito quantistico con un costo computazionale asintotico simile. Inoltre, questo può essere fatto in modo "pulito", come descriveremo a breve, il che è un requisito importante per utilizzare queste computazioni come subroutine all'interno di computazioni quantistiche più grandi.

Simulare i circuiti booleani con i circuiti quantistici

I circuiti booleani sono composti da gate AND, OR, NOT e FANOUT. Per simulare i circuiti booleani con i circuiti quantistici, inizieremo mostrando come ciascuno di questi quattro gate può essere simulato da gate quantistici. Una volta fatto ciò, convertire un dato circuito booleano in un circuito quantistico è una semplice questione di simulare un gate alla volta. Per fare questo avremo bisogno solo di gate NOT, gate controlled-NOT e gate di Toffoli, che sono tutti operazioni deterministiche oltre ad essere unitarie.

gate di Toffoli

I gate di Toffoli possono essere descritti in alternativa come gate controlled-controlled-NOT, la cui azione sugli stati della base standard è mostrata nella figura seguente.

Tenendo presente che utilizziamo la convenzione di ordinamento di Qiskit, in cui i qubit sono ordinati per significatività crescente dall'alto verso il basso, la rappresentazione matriciale di questo gate è la seguente.

$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}$$

Un altro modo di pensare ai gate di Toffoli è che sono essenzialmente gate di query per la funzione AND, nel senso che seguono lo schema visto nella lezione precedente per le implementazioni unitarie di gate di query di funzioni arbitrarie con input e output in forma di stringhe binarie.

I gate di Toffoli non sono inclusi nel set di gate predefinito discusso in precedenza nella lezione, ma è possibile costruire un gate di Toffoli a partire dai gate $H,$ $T,$ $T^{\dagger}$ e CNOT nel modo seguente.

Simulare i gate booleani con gate Toffoli, controlled-NOT e NOT

Un singolo gate di Toffoli, usato insieme a pochi gate NOT, può implementare un gate AND e un gate OR, mentre i gate FANOUT possono essere facilmente implementati usando gate controlled-NOT, come suggeriscono i diagrammi seguenti.

In tutti e tre i casi, i qubit su cui agiscono i gate AND, OR e FANOUT arrivano da sinistra come input, e per ciascuno è richiesto anche un qubit di workspace inizializzato allo stato zero. Questi qubit di workspace appaiono all'interno dei riquadri che rappresentano le implementazioni dei gate per indicare che sono nuovi, e quindi parte del costo di queste implementazioni.

Per i gate AND e OR abbiamo anche due qubit in eccesso, oltre al qubit di output. Ad esempio, all'interno del riquadro nel diagramma che rappresenta la simulazione di un gate AND, i due qubit in cima sono lasciati negli stati $\vert a\rangle$ e $\vert b\rangle.$ Questi qubit sono illustrati come rimasti all'interno dei riquadri perché non sono più necessari e non fanno parte dell'output. Per ora possono essere ignorati, anche se ci torneremo sopra a breve.

Il restante gate booleano, il gate NOT, è incluso nel nostro set predefinito di gate quantistici, quindi non è necessaria una simulazione per questo.

Simulazione gate per gate dei circuiti booleani

Supponiamo ora di avere un circuito booleano ordinario chiamato $C,$ composto da gate AND, OR, NOT e FANOUT, e con $n$ bit di input e $m$ bit di output. Sia $t = \operatorname{size}(C)$ il numero di gate in $C,$ e diamo il nome $f$ alla funzione che $C$ calcola, che ha la forma

$$f:\Sigma^n\rightarrow\Sigma^m$$

per $\Sigma = \{0,1\}.$

Consideriamo ora cosa succede quando analizziamo uno alla volta i gate AND, OR e FANOUT di $C,$ sostituendo ciascuno con la corrispondente simulazione descritta sopra, inclusa l'aggiunta dei qubit di workspace necessari. Chiamiamo $R$ il circuito risultante, e ordiniamo i qubit di $R$ in modo che gli $n$ bit di input di $C$ corrispondano agli $n$ qubit in cima di $R$ e i qubit di workspace siano in fondo.

Qui, $k$ è il numero di qubit di workspace necessari — uno per ogni gate AND, OR e FANOUT di $C$ — e $g$ è una funzione della forma $g:\Sigma^n \rightarrow \Sigma^{n+k-m}$ che descrive gli stati dei qubit in eccesso creati dalle simulazioni dei gate dopo l'esecuzione di $R.$ Nella figura, i qubit corrispondenti all'output $f(x)$ sono in cima e i restanti qubit in eccesso che memorizzano $g(x)$ sono in fondo. Se lo desideriamo, possiamo forzare questo ordinamento riorganizzando i qubit usando gate SWAP, che possono essere implementati con tre gate controlled-NOT come segue:

Come vedremo nella prossima sezione, non è davvero essenziale riorganizzare i qubit di output in questo modo, ma è abbastanza semplice farlo se lo scegliamo.

La funzione $g$ che descrive gli stati classici dei qubit in eccesso è determinata dal circuito $C,$ ma in realtà non dobbiamo preoccuparcene troppo; non ci interessa specificamente in quale stato si trovano questi qubit al termine della computazione. La lettera $g$ viene dopo $f,$ quindi è un nome ragionevole per questa funzione per questo motivo, ma c'è una ragione migliore per scegliere il nome $g$ — è l'abbreviazione di garbage (spazzatura).

Pulire la spazzatura

Se il nostro unico interesse è valutare la funzione $f$ calcolata da un dato circuito booleano $C$ con un circuito quantistico, non dobbiamo andare oltre la simulazione gate per gate appena descritta. Ciò significa che, oltre all'output della funzione, avremo un bel po' di spazzatura rimasta.

Tuttavia, questo non è sufficiente se vogliamo eseguire computazioni classiche come subroutine all'interno di computazioni quantistiche più grandi, perché quei qubit di spazzatura causeranno problemi. Il fenomeno dell'interferenza è di fondamentale importanza per gli algoritmi quantistici, e i qubit di spazzatura possono rovinare i pattern di interferenza necessari al funzionamento degli algoritmi quantistici.

Fortunatamente, non è difficile fare pulizia della spazzatura, per così dire. La chiave è sfruttare il fatto che, poiché $R$ è un circuito quantistico, possiamo eseguirlo al contrario, semplicemente sostituendo ogni gate con il suo inverso e applicandoli nell'ordine inverso, ottenendo così un circuito quantistico per l'operazione $R^{\dagger}.$ I gate di Toffoli, i gate CNOT e i gate NOT sono in realtà i propri inversi, quindi eseguire $R$ al contrario è davvero solo una questione di applicare i gate nell'ordine inverso — ma più in generale qualsiasi circuito quantistico può essere invertito come appena descritto.

In particolare, quello che possiamo fare è aggiungere altri $m$ qubit (ricordando che la funzione $f$ ha $m$ bit di output), usare gate CNOT per copiare l'output di $R$ su questi qubit, e invertire $R$ per eliminare la spazzatura. La figura seguente illustra il circuito risultante e ne descrive l'azione sugli stati della base standard.

Se mettiamo un riquadro attorno all'intero circuito e lo chiamiamo $Q,$ appare così:

Dato che $C$ ha $t$ gate, il circuito $Q$ avrà $O(t)$ gate.

Se tralasciamo i $k$ qubit di workspace aggiuntivi, quello che abbiamo è un circuito $Q$ che funziona esattamente come un gate di query per la funzione $f.$ Se vogliamo semplicemente calcolare la funzione $f$ su una stringa $x,$ possiamo impostare $y = 0^m$ e il valore risultante $f(x)$ apparirà sugli $m$ qubit in fondo — oppure possiamo fornire uno stato diverso agli $m$ qubit in fondo se lo desideriamo (forse per sfruttare un phase kickback, come nell'algoritmo di Deutsch o nell'algoritmo di Deutsch-Jozsa).

Ciò significa che per qualsiasi algoritmo di query, se abbiamo un circuito booleano che calcola la funzione di input, possiamo sostituire ogni gate di query con un'implementazione circuitale di esso, e l'algoritmo di query funzionerà correttamente.

Nota che i qubit di workspace sono necessari per far funzionare questo processo, ma vengono riportati ai loro stati iniziali una volta eseguito il circuito combinato. Questo permette di riutilizzare questi qubit come qubit di workspace per altri scopi. Esistono anche strategie note per ridurre il numero di qubit di workspace necessari (al costo di rendere i circuiti più grandi), ma non discuteremo quelle strategie qui.

Implementare funzioni invertibili

La costruzione appena descritta ci permette di simulare qualsiasi circuito booleano con un circuito quantistico in modo privo di spazzatura. Se $C$ è un circuito booleano che implementa una funzione $f:\Sigma^n \rightarrow \Sigma^m,$ allora otteniamo un circuito quantistico $Q$ che opera come segue sugli stati della base standard.

$$Q \bigl( \vert y \rangle \vert 0^k \rangle \vert x\rangle\bigr) = \vert y \oplus f(x) \rangle \vert 0^k \rangle \vert x\rangle$$

Il numero $k$ indica quanti qubit di workspace sono necessari in totale. Questo è sufficiente per gli scopi di questo corso, ma è possibile portare questa metodologia un passo avanti quando la funzione $f$ stessa è invertibile.

Per essere precisi, supponiamo che la funzione $f$ abbia la forma $f:\Sigma^n \rightarrow \Sigma^n,$ e supponiamo inoltre che esista una funzione $f^{-1}$ tale che $f^{-1}(f(x)) = x$ per ogni $x\in\Sigma^n$ (che è necessariamente unica quando esiste). Ciò significa che l'operazione che trasforma $\vert x \rangle$ in $\vert f(x) \rangle$ per ogni $x\in\Sigma^n$ è unitaria, quindi potremmo sperare di costruire un circuito quantistico che implementi l'operazione unitaria definita da

$$U \vert x \rangle = \vert f(x) \rangle$$

per ogni $x\in\Sigma^n.$

Per essere chiari, il fatto che questa sia un'operazione unitaria dipende dall'invertibilità di $f$ — non è unitaria quando $f$ non è invertibile. Tralasciando i qubit di workspace, $U$ è diversa dall'operazione che il circuito $Q$ implementa perché non stiamo mantenendo una copia dell'input e applicando uno XOR con una stringa arbitraria, stiamo sostituendo $x$ con $f(x).$

La domanda è: quando $f$ è invertibile, possiamo farlo?

La risposta è sì, a condizione che sia consentito utilizzare qubit di workspace e che, oltre ad avere un circuito booleano che calcola $f,$ ne abbiamo anche uno che calcola $f^{-1}.$ Quindi, questo non è una scorciatoia per invertire computazionalmente le funzioni quando non sappiamo già come farlo! Il diagramma seguente illustra come può essere fatto componendo due circuiti quantistici, $Q_f$ e $Q_{f^{-1}},$ ottenuti individualmente per le funzioni $f$ e $f^{-1}$ attraverso il metodo descritto sopra, insieme a $n$ gate di swap, prendendo $k$ come il massimo tra i numeri di qubit di workspace richiesti da $Q_f$ e $Q_{f^{-1}}.$