L'algoritmo di Deutsch-Jozsa

Per questo modulo Qiskit in Classrooms, gli studenti devono avere un ambiente Python funzionante con i seguenti pacchetti installati:

• qiskit v2.1.0 o successivo
• qiskit-ibm-runtime v0.40.1 o successivo
• qiskit-aer v0.17.0 o successivo
• qiskit.visualization
• numpy
• pylatexenc

Per configurare e installare i pacchetti sopra indicati, consulta la guida Installa Qiskit. Per eseguire job su computer quantistici reali, gli studenti dovranno creare un account con IBM Quantum® seguendo i passaggi nella guida Configura il tuo account IBM Cloud.

Questo modulo è stato testato e ha utilizzato quattro secondi di tempo QPU. Si tratta solo di una stima. L'utilizzo effettivo può variare.

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

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Guarda il video di presentazione del modulo della Dott.ssa Katie McCormick qui sotto, oppure clicca qui per vederlo su YouTube.

---

Introduzione

All'inizio degli anni '80, i fisici quantistici e gli informatici avevano una vaga intuizione che la meccanica quantistica potesse essere sfruttata per eseguire calcoli molto più potenti di quelli possibili con i computer classici. Il ragionamento era il seguente: è difficile per un computer classico simulare sistemi quantistici, ma un computer quantistico dovrebbe essere in grado di farlo in modo più efficiente. E se un computer quantistico potesse simulare sistemi quantistici in modo più efficiente, forse esistevano altre attività che poteva svolgere meglio di un computer classico.

La logica era solida, ma i dettagli dovevano ancora essere elaborati. Tutto iniziò nel 1985, quando David Deutsch descrisse il primo "computer quantistico universale". In quello stesso articolo, fornì il primo esempio di problema per cui un computer quantistico poteva risolvere qualcosa in modo più efficiente di un computer classico. Questo primo esempio didattico è oggi noto come "algoritmo di Deutsch". Il miglioramento dell'algoritmo di Deutsch era modesto, ma Deutsch collaborò con Richard Jozsa qualche anno dopo per ampliare ulteriormente il divario tra computer classici e quantistici.

Questi algoritmi — quello di Deutsch e l'estensione di Deutsch-Jozsa — non sono particolarmente utili, ma restano comunque molto importanti per alcune ragioni:

1. Storicamente, sono stati tra i primi algoritmi quantistici a dimostrare di poter superare le controparti classiche. Capirli ci aiuta a comprendere come il pensiero della comunità sull'informatica quantistica si sia evoluto nel tempo.
2. Possono aiutarci a capire alcuni aspetti della risposta a una domanda sorprendentemente sottile: cosa dà potere all'informatica quantistica? A volte i computer quantistici vengono paragonati a enormi processori paralleli che scalano esponenzialmente. Ma non è del tutto corretto. Sebbene una parte della risposta risieda nel cosiddetto "parallelismo quantistico", estrarre quante più informazioni possibile in una singola esecuzione è un'arte sottile. Gli algoritmi di Deutsch e Deutsch-Jozsa mostrano come questo possa essere fatto.

In questo modulo impareremo l'algoritmo di Deutsch, l'algoritmo di Deutsch-Jozsa e cosa ci insegnano sul potere dell'informatica quantistica.

Parallelismo quantistico e i suoi limiti

Una parte del potere dell'informatica quantistica deriva dal "parallelismo quantistico", che è essenzialmente la capacità di eseguire operazioni su più input contemporaneamente, poiché gli stati di input dei qubit possono trovarsi in una sovrapposizione di più stati classicamente ammessi. TUTTAVIA, sebbene un circuito quantistico possa valutare più stati di input contemporaneamente, estrarre tutte quelle informazioni in una volta sola è impossibile.

Per capire cosa intendo, supponiamo di avere un bit $x$ e una funzione applicata a quel bit, $f(x)$. Esistono quattro possibili funzioni binarie che mappano un singolo bit in un altro singolo bit:

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

Vorremmo scoprire quale di queste funzioni (1-4) sia la nostra $f(x)$. Classicamente, dovremmo eseguire la funzione due volte — una per $x=0$, una per $x=1$. Ma vediamo se possiamo fare meglio con un circuito quantistico. Possiamo apprendere informazioni sulla funzione con il seguente gate:

Qui, il gate $U_f$ calcola $f(x)$, dove $x$ è lo stato del qubit 0, e lo applica al qubit 1. Quindi lo stato risultante, $|x\rangle|y\oplus f(x)\rangle$, diventa semplicemente $|x\rangle|f(x)\rangle$ quando $|y\rangle = |0\rangle$. Questo contiene tutte le informazioni necessarie per conoscere la funzione $f(x)$: il qubit 0 ci dice cosa è $x$, e il qubit 1 ci dice cosa è $f(x)$. Quindi, se inizializziamo $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, lo stato finale di entrambi i qubit sarà: $|y\rangle|x\rangle = \frac{1}{\sqrt{2}}(|f(0)\rangle|0\rangle+|f(1)\rangle|1\rangle)$. Ma come accediamo a queste informazioni?

2.1. Provalo su Qiskit:

Usando Qiskit selezioneremo casualmente una delle quattro funzioni possibili sopra indicate ed eseguiremo il circuito. Il tuo compito è usare le misurazioni del circuito quantistico per apprendere la funzione nel minor numero di esecuzioni possibile.

In questo primo esperimento e per tutto il modulo, utilizzeremo un framework per l'informatica quantistica noto come "Qiskit patterns", che suddivide i flussi di lavoro nei seguenti passaggi:

• Passaggio 1: Mappare gli input classici su un problema quantistico
• Passaggio 2: Ottimizzare il problema per l'esecuzione quantistica
• Passaggio 3: Eseguire usando i Primitivi di Qiskit Runtime
• Passaggio 4: Post-elaborazione e analisi classica

Iniziamo caricando alcuni pacchetti necessari, incluse le primitive di Qiskit Runtime. Selezioneremo anche il computer quantistico meno occupato disponibile.

Di seguito è presente del codice per salvare le credenziali al primo utilizzo. Assicurati di eliminare queste informazioni dal notebook dopo averle salvate nel tuo ambiente, in modo che le tue credenziali non vengano condivise accidentalmente quando condividi il notebook. Consulta Configura il tuo account IBM Cloud e Inizializza il servizio in un ambiente non attendibile per ulteriori indicazioni.

# Load the Qiskit Runtime service
from qiskit_ibm_runtime import QiskitRuntimeService

# Load the Runtime primitive and session
from qiskit_ibm_runtime import SamplerV2 as Sampler

# Syntax for first saving your token.  Delete these lines after saving your credentials.
# QiskitRuntimeService.save_account(channel='ibm_quantum_platform', instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

# Use the least busy backend, or uncomment the loading of a specific backend like "ibm_brisbane".
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_brisbane")
print(backend.name)

sampler = Sampler(mode=backend)

ibm_brisbane

La cella sottostante ti permetterà di passare dall'uso del simulatore all'hardware reale nel notebook. Ti consigliamo di eseguirla ora:

# Load the backend sampler
from qiskit.primitives import BackendSamplerV2

# Load the Aer simulator and generate a noise model based on the currently-selected backend.
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel

# Alternatively, load a fake backend with generic properties and define a simulator.

noise_model = NoiseModel.from_backend(backend)

# Define a simulator using Aer, and use it in Sampler.
backend_sim = AerSimulator(noise_model=noise_model)
sampler_sim = BackendSamplerV2(backend=backend_sim)

# You could also define a simulator-based sampler using a generic backend:
# backend_gen = GenericBackendV2(num_qubits=18)
# sampler_gen = BackendSamplerV2(backend=backend_gen)

Ora che abbiamo caricato i pacchetti necessari, possiamo procedere con il flusso di lavoro dei Qiskit patterns. Nel passaggio di mappatura qui sotto, creiamo prima una funzione che seleziona tra le quattro possibili funzioni che mappano un singolo bit in un altro singolo bit.

# Step 1: Map

from qiskit import QuantumCircuit

qc = QuantumCircuit(2)

def twobit_function(case: int):
    """
    Generate a valid two-bit function as a `QuantumCircuit`.
    """
    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

# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the circuit is too large to display
# blackbox = twobit_function(2).to_gate()  # you may edit the number inside "twobit_function()" to select among the four valid functions
# blackbox.label = "$U_f$"

qc.h(0)
qc.barrier()
qc.compose(twobit_function(2), inplace=True)
qc.measure_all()

qc.draw("mpl")

Nel circuito sopra, il gate di Hadamard "H" porta il qubit 0, che si trova inizialmente nello stato $|0\rangle$, allo stato di sovrapposizione $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. Quindi, $U_f$ valuta la funzione $f(x)$ e la applica al qubit 1.

Ora dobbiamo ottimizzare e traspilare il circuito per eseguirlo sul computer quantistico:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

Infine, eseguiamo il nostro circuito traspilato sul computer quantistico e visualizziamo i risultati:

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.meas.get_counts()

# Step 4: Visualize and analyze results

## Analysis
from qiskit.visualization import plot_histogram

plot_histogram(counts)

Sopra è mostrato un istogramma dei nostri risultati. A seconda del numero di shots scelti per eseguire il circuito nel passaggio 3 sopra, potresti vedere una o due barre, che rappresentano gli stati misurati dei due qubit in ogni shot. Come sempre con Qiskit e in questo notebook, usiamo la notazione "little endian", il che significa che gli stati dei qubit da 0 a n sono scritti in ordine crescente da destra a sinistra, quindi il qubit 0 si trova sempre all'estrema destra.

Quindi, poiché il qubit 0 era in uno stato di sovrapposizione, il circuito ha valutato la funzione per entrambi $x=0$ e $x=1$ allo stesso tempo — qualcosa che i computer classici non possono fare! Ma il problema emerge quando vogliamo apprendere informazioni sulla funzione $f(x)$ — quando misuriamo i qubit, il loro stato collassa. Se selezioni "shots = 1" per eseguire il circuito una sola volta, vedrai solo una barra nell'istogramma sopra e le tue informazioni sulla funzione saranno incomplete.

Verifica la tua comprensione

Leggi la/le domanda/e qui sotto, pensa alla tua risposta, poi clicca sul triangolo per rivelare la soluzione.

Quante volte dobbiamo eseguire l'algoritmo sopra per apprendere la funzione $f(x)$? È migliore del caso classico? Preferiresti avere un computer classico o quantistico per risolvere questo problema?

Risposta:

Poiché la misurazione collassa la sovrapposizione e restituisce un solo valore, dobbiamo eseguire il circuito almeno due volte per ottenere entrambi gli output della funzione $f(0)$ e $f(1)$. Nel migliore dei casi, questo si comporta come il caso classico, in cui calcoliamo sia $f(0)$ che $f(1)$ nelle prime due interrogazioni. Ma c'è la possibilità che dobbiamo eseguirlo più di due volte, poiché la misurazione finale è probabilistica e potrebbe restituire lo stesso valore $f(x)$ le prime due volte. In questo caso preferirei un computer classico.

Quindi, sebbene il parallelismo quantistico possa essere potente se usato nel modo giusto, non è corretto affermare che un computer quantistico funzioni come un enorme processore parallelo classico. L'atto della misurazione fa collassare gli stati quantistici, quindi possiamo accedere solo a un singolo output del calcolo.

L'algoritmo di Deutsch

Sebbene il parallelismo quantistico da solo non ci dia un vantaggio rispetto ai computer classici, possiamo abbinarlo a un altro fenomeno quantistico, l'interferenza, per ottenere un'accelerazione. L'algoritmo oggi noto come "algoritmo di Deutsch" è il primo esempio di algoritmo che riesce in questo intento.

Il problema

Ecco il problema:

Dato un bit di input $x = \{0,1\}$ e una funzione di input $f(x) = \{0,1\}$, determinare se la funzione è bilanciata o costante. Cioè, se è bilanciata, l'output della funzione è 0 metà delle volte e 1 l'altra metà. Se è costante, l'output della funzione è sempre 0 o sempre 1. Ricordiamo la tabella delle quattro possibili funzioni che mappano un singolo bit in un altro singolo bit:

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

La prima e l'ultima funzione, $f_1(x)$ e $f_4(x)$, sono costanti, mentre le due funzioni centrali, $f_2(x)$ e $f_3(x)$, sono bilanciate.

L'algoritmo

Il modo in cui Deutsch ha affrontato questo problema è stato attraverso il "modello a query". Nel modello a query, la funzione di input ($f_i(x)$ sopra) è contenuta in una "scatola nera" — non abbiamo accesso diretto al suo contenuto, ma possiamo interrogare la scatola nera e ci fornirà l'output della funzione. A volte diciamo che un "oracolo" fornisce queste informazioni. Consulta la Lezione 1: Algoritmi a Query Quantistici del corso Fondamenti di Algoritmi Quantistici per saperne di più sul modello a query.

Per determinare se un algoritmo quantistico è più efficiente di uno classico nel modello a query, possiamo semplicemente confrontare il numero di query che dobbiamo fare alla scatola nera in ciascun caso. Nel caso classico, per sapere se la funzione contenuta nella scatola nera fosse bilanciata o costante, dovremmo interrogare la scatola due volte per ottenere sia $f(0)$ che $f(1)$.

Nell'algoritmo quantistico di Deutsch, però, ha trovato un modo per ottenere le informazioni con una sola query! Ha apportato una modifica al circuito del "parallelismo quantistico" sopra, in modo da preparare uno stato di sovrapposizione su entrambi i qubit, anziché solo sul qubit 0. Quindi i due output della funzione, $f(0)$ e $f(1)$, sono interferiti per restituire 0 se erano entrambi 0 o entrambi 1 (la funzione era costante), e restituivano 1 se erano diversi (la funzione era bilanciata). In questo modo, Deutsch poteva distinguere tra una funzione costante e una bilanciata con una singola query.

Ecco un diagramma del circuito dell'algoritmo di Deutsch:

Per capire come funziona questo algoritmo, esaminiamo gli stati quantistici dei qubit nei tre punti indicati nel diagramma sopra. Prova a elaborare gli stati da solo prima di cliccare per visualizzare le risposte:

Verifica la tua comprensione

Leggi le domande qui sotto, pensa alle tue risposte, poi clicca sui triangoli per rivelare le soluzioni.

Qual è lo stato $|\pi_1\rangle$?

Risposta:

Applicare un gate di Hadamard trasforma lo stato $|0\rangle$ in $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ e lo stato $|1\rangle$ in $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Quindi lo stato completo diventa: $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

Qual è lo stato $|\pi_2\rangle$?

Risposta:

Prima di applicare $U_f$, ricordiamo cosa fa. Cambierà lo stato del qubit 1 in base allo stato del qubit 0. Quindi ha senso fattorizzare lo stato del qubit 0: $|\pi_1\rangle = \frac{1}{2} (|0\rangle-|1\rangle)|0\rangle+\frac{1}{2}(|0\rangle-|1\rangle)|1\rangle$. Quindi, se $f(0)=f(1)$, i due termini si trasformeranno nello stesso modo e il segno relativo tra i due termini rimane positivo, ma se $f(0)\neq f(1)$, allora il secondo termine acquisirà un segno meno rispetto al primo termine, cambiando lo stato del qubit 0 da $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ a $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Quindi:

$$|\pi_2\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}] & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle-|1\rangle}{\sqrt{2}}] &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

Qual è lo stato $|\pi_3\rangle$?

Risposta:

Ora, lo stato del qubit 0 è $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ oppure $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$, a seconda della funzione. Applicare il gate di Hadamard produrrà rispettivamente $|0\rangle$ oppure $|1\rangle$.

$$|\pi_3\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|0\rangle & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|1\rangle &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

Esaminando le tue risposte alle domande precedenti, nota che accade qualcosa di sorprendente. Sebbene $U_f$ non faccia nulla esplicitamente allo stato del qubit 0, poiché modifica il qubit 1 in base allo stato del qubit 0, può succedere che questo causi uno sfasamento nel qubit 0. Questo fenomeno è noto come "phase-kickback" e viene discusso in modo più dettagliato nella Lezione 1: Algoritmi a Query Quantistici del corso Fondamenti di Algoritmi Quantistici.

Ora che capiamo come funziona questo algoritmo, implementiamolo con Qiskit.

## Deutsch's algorithm:

## Step 1: Map the problem

# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the circuit is too large to display
blackbox = twobit_function(
    3
).to_gate()  # you may edit the number (1-4) inside "twobit_function()" to select among the four valid functions
blackbox.label = "$U_f$"

qc_deutsch = QuantumCircuit(2, 1)

qc_deutsch.x(1)
qc_deutsch.h(range(2))

qc_deutsch.barrier()
qc_deutsch.compose(twobit_function(2), inplace=True)
qc_deutsch.barrier()

qc_deutsch.h(0)
qc_deutsch.measure(0, 0)

qc_deutsch.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_deutsch)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)
if "1" in counts:
    print("balanced")
else:
    print("constant")

{'1': 1}
balanced

L'algoritmo di Deutsch-Jozsa

L'algoritmo di Deutsch è stato un importante primo passo nel dimostrare come un computer quantistico possa essere più efficiente di uno classico, ma si trattava di un miglioramento modesto: richiedeva una sola query, rispetto alle due del caso classico. Nel 1992, Deutsch e il suo collega Richard Jozsa estesero l'algoritmo originale a due qubit a un numero maggiore di qubit. Il problema rimase lo stesso: determinare se una funzione è bilanciata o costante. Ma questa volta la funzione va da $n$ bit a un singolo bit. La funzione restituisce 0 e 1 un numero uguale di volte (è bilanciata), oppure restituisce sempre 1 o sempre 0 (è costante).

Ecco il diagramma del circuito dell'algoritmo:

Questo algoritmo funziona nello stesso modo dell'algoritmo di Deutsch: il phase kickback consente di leggere lo stato del qubit 0 per determinare se la funzione è costante o bilanciata. È un po' più difficile da vedere rispetto al caso dell'algoritmo di Deutsch a due qubit, poiché gli stati includeranno somme sugli $n$ qubit; pertanto, il calcolo di questi stati è lasciato come esercizio facoltativo per te alla fine del modulo. L'algoritmo restituirà una stringa di bit composta da tutti 0 se la funzione è costante, e una stringa di bit contenente almeno un 1 se la funzione è bilanciata.

Per vedere come funziona l'algoritmo in Qiskit, dobbiamo prima generare il nostro oracolo: la funzione casuale che è garantita essere o costante o bilanciata. Il codice seguente genererà una funzione bilanciata il 50% delle volte e una funzione costante il restante 50%. Non preoccuparti se non capisci completamente il codice — è complicato e non è necessario per la nostra comprensione dell'algoritmo quantistico.

from qiskit import QuantumCircuit
import numpy as np

def dj_function(num_qubits):
    """
    Create a random Deutsch-Jozsa function.
    """

    qc_dj = QuantumCircuit(num_qubits + 1)
    if np.random.randint(0, 2):
        # Flip output qubits with 50% chance
        qc_dj.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance.
        return qc_dj

    # If the "if" statement above was "TRUE" then we've returned the constant
    # function and the function is complete. If not, we proceed in creating our
    # balanced function. Everything below is to produce the balanced function:

    # select half of all possible states at random:
    on_states = np.random.choice(
        range(2**num_qubits),  # numbers to sample from
        2**num_qubits // 2,  # number of samples
        replace=False,  # makes sure states are only sampled once
    )

    def add_cx(qc_dj, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc_dj.x(qubit)
        return qc_dj

    for state in on_states:
        # qc_dj.barrier()  # Barriers are added to help visualize how the functions are created. They can safely be removed.
        qc_dj = add_cx(qc_dj, f"{state:0b}")
        qc_dj.mcx(list(range(num_qubits)), num_qubits)
        qc_dj = add_cx(qc_dj, f"{state:0b}")

    # qc_dj.barrier()

    return qc_dj

n = 3  # number of input qubits

oracle = dj_function(n)

display(oracle.draw("mpl"))

Questa è la funzione oracolo, che può essere bilanciata o costante. Guardandola, riesci a capire se l'output sull'ultimo qubit dipende dai valori inseriti per i primi $n$ qubit? Se l'output dell'ultimo qubit dipende dai primi $n$ qubit, riesci a dire se quell'output dipendente è bilanciato o no?

Possiamo capire se la funzione è bilanciata o costante osservando il circuito precedente, ma ricorda: ai fini di questo problema, la consideriamo come una "scatola nera". Non possiamo sbirciare all'interno della scatola per vedere il diagramma del circuito. Dobbiamo invece interrogare la scatola.

Per interrogare la scatola, usiamo l'algoritmo di Deutsch-Jozsa e determiniamo se la funzione è costante o bilanciata:

blackbox = oracle.to_gate()
blackbox.label = "$U_f$"

qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(blackbox, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))

qc_dj.decompose().decompose()

qc_dj.draw("mpl")

# Step 1: Map the problem

qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(oracle, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))

qc_dj.decompose().decompose()

qc_dj.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_dj)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)

if (
    "0" * n in counts
):  # The D-J algorithm returns all zeroes if the function was constant
    print("constant")
else:
    print("balanced")  # anything other than all zeroes means the function is balanced.

{'110': 1}
balanced

Sopra, la prima riga dell'output è la stringa di bit dei risultati di misura. La seconda riga indica se la stringa di bit implica che la funzione fosse bilanciata o costante. Se la stringa di bit conteneva tutti zeri, allora era costante; altrimenti era bilanciata. Quindi, con una singola esecuzione del circuito quantistico precedente, possiamo determinare se la funzione è costante o bilanciata!

Verifica la tua comprensione

Leggi le domande seguenti, pensa alle tue risposte, poi clicca sui triangoli per scoprire le soluzioni.

Quante query sarebbero necessarie a un computer classico per determinare con il 100% di certezza se una funzione è costante o bilanciata? Ricorda: classicamente, una singola query ti consente di applicare la funzione a una sola stringa di bit.

Risposta:

Ci sono $2^n$ possibili stringhe di bit da verificare e, nel caso peggiore, occorre testarne $2^n/2+1$. Ad esempio, se la funzione fosse costante e continuassi a misurare "1" come output della funzione, non potresti essere certo che sia davvero costante finché non hai controllato più della metà dei risultati. Prima di quel momento, potresti semplicemente essere stato molto sfortunato a misurare continuamente "1" su una funzione bilanciata. È come lanciare una moneta più e più volte e ottenere sempre testa. È improbabile, ma non impossibile.

In che modo cambierebbe la tua risposta precedente se dovessi solo misurare finché un esito (bilanciato o costante) è più probabile dell'altro? Quante query sarebbero necessarie in questo caso?

Risposta:

In questo caso, potresti misurare solo due volte. Se le due misurazioni sono diverse, sai che la funzione è bilanciata. Se le due misurazioni sono uguali, potrebbe essere bilanciata o costante. La probabilità che sia bilanciata con questo insieme di misurazioni è: $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$. Questo valore è inferiore a 1/2, quindi in questo caso è più probabile che la funzione sia costante.

Quindi, l'algoritmo di Deutsch-Jozsa ha dimostrato un'accelerazione esponenziale rispetto a un algoritmo classico deterministico (uno che restituisce la risposta con il 100% di certezza), ma nessuna accelerazione significativa rispetto a uno probabilistico (uno che restituisce un risultato che è probabile sia la risposta corretta).

Il problema di Bernstein-Vazirani

Nel 1997, Ethan Bernstein e Umesh Vazirani usarono l'algoritmo di Deutsch-Jozsa per risolvere un problema più specifico e ristretto rispetto al problema di Deutsch-Jozsa. Invece di cercare semplicemente di distinguere tra due diverse classi di funzioni, come nel caso D-J, Bernstein e Vazirani usarono l'algoritmo di Deutsch-Jozsa per apprendere effettivamente una stringa codificata in una funzione. Ecco il problema:

La funzione $f:\{0,1\}^n \rightarrow \{0,1\}$ riceve ancora una stringa di $n$ bit e restituisce un singolo bit. Ma ora, invece di promettere che la funzione è bilanciata o costante, ci viene promesso che la funzione è il prodotto scalare tra la stringa di input $x$ e una stringa segreta $s$ di $n$ bit, modulo 2. (Questo prodotto scalare modulo 2 è chiamato "prodotto scalare binario".) Il problema è capire quale sia la stringa segreta di $n$ bit.

In altri termini, ci viene data una funzione a scatola nera $f: {0,1}^n \rightarrow {0,1}$ che soddisfa $f(x) = s \cdot x$ per qualche stringa $s$, e vogliamo scoprire la stringa $s$.

Vediamo come l'algoritmo D-J risolve questo problema:

1. Prima, un gate di Hadamard viene applicato agli $n$ qubit di input, e un gate NOT più un Hadamard vengono applicati al qubit di output, portando allo stato:

$$|\Psi\rangle = |-\rangle_{n} \otimes |+\rangle_{n-1} \otimes |+\rangle_{n-2} \otimes ... \otimes |+\rangle_0$$

Lo stato dei qubit da 1 a $n$ può essere scritto più semplicemente come una somma su tutti i $2^n$ stati base a $n$ qubit $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$. Chiamiamo l'insieme di questi stati base $\Sigma^n$. (Vedi Fundamentals of Quantum Algorithms per maggiori dettagli.)

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{|x\rangle}$$

2. Successivamente, il gate $U_f$ viene applicato ai qubit. Questo gate prenderà i primi n qubit come input (che si trovano ora in un'uguale sovrapposizione di tutte le possibili stringhe di n bit) e applica la funzione $f(x)=s \cdot x$ al qubit di output, in modo che questo qubit si trovi ora nello stato: $|- \oplus f(x)\rangle$. Grazie al meccanismo di phase kickback, lo stato di questo qubit rimane invariato, ma alcuni termini nello stato del qubit di input acquisiscono un segno meno:

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{(-1)^{f(x)}|x\rangle}$$

3. Ora viene applicato il successivo insieme di gate di Hadamard ai qubit da 0 a $n-1$. Tenere traccia dei segni meno in questo caso può essere complicato. È utile sapere che applicare uno strato di gate di Hadamard a $n$ qubit in uno stato base standard $|x\rangle$ può essere scritto come:

$$H^{\otimes n} |x\rangle = \frac{1}{\sqrt{2^n}}\sum\limits_{y \in \Sigma^n}{(-1)^{x \cdot y}|y\rangle}$$

Quindi lo stato diventa:

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{2^n}\sum\limits_{x \in \Sigma^n}\sum\limits_{y \in \Sigma^n}{(-1)^{(s \cdot x) + (x \cdot y)}|y\rangle}$$

4. Il passo successivo è misurare i primi $n$ bit. Ma cosa misureremo? Si scopre che lo stato precedente si semplifica in: $|\Psi\rangle = |-\rangle \otimes |s\rangle$, ma questo è tutt'altro che ovvio. Se vuoi seguire la matematica, vedi il corso di John Watrous Fundamentals of Quantum Algorithms. Il punto cruciale è che il meccanismo di phase kickback porta i qubit di input allo stato $|s\rangle$. Quindi, per scoprire qual era la stringa segreta $s$, devi semplicemente misurare i qubit!

Verifica la tua comprensione

Leggi le domande seguenti, pensa alle tue risposte, poi clicca sui triangoli per scoprire le soluzioni.

Verifica che lo stato del Passo 3 precedente sia effettivamente lo stato $|s\rangle$ nel caso speciale di $n=1$.

Risposta:

Quando scrivi esplicitamente le due sommatorie, dovresti ottenere uno stato con quattro termini (omettiamo lo stato di output $|-\rangle$ per questo):

$$|\Psi\rangle = \frac{1}{2}[|0\rangle + (-1)^s |0\rangle + |1\rangle + (-1)^{(s+1)} |1\rangle]$$

Se $s=0$, i primi due termini si sommano costruttivamente e gli ultimi due si cancellano, lasciandoci con $|\Psi\rangle = |0\rangle$. Se $s=1$, gli ultimi due termini si sommano costruttivamente e i primi due si cancellano, lasciandoci con $|\Psi\rangle = |1\rangle$. Quindi, in entrambi i casi, $|\Psi\rangle = |s\rangle$. Speriamo che questo caso più semplice ti dia un'idea di come funziona il caso generale con $n$ qubit: tutti i termini che non sono $|s\rangle$ interferiscono e si annullano, lasciando solo lo stato $|s\rangle$.

Come può lo stesso algoritmo risolvere sia il problema di Bernstein-Vazirani che quello di Deutsch-Jozsa? Per capirlo, pensa alle funzioni di Bernstein-Vazirani, che sono della forma $f(x) = s \cdot x$. Queste funzioni sono anche funzioni di Deutsch-Jozsa? Cioè, determina se le funzioni di questa forma soddisfano la promessa del problema di Deutsch-Jozsa: che siano costanti o bilanciate. In che modo questo ci aiuta a capire come lo stesso algoritmo risolva due problemi diversi?

Risposta:

Ogni funzione di Bernstein-Vazirani della forma $f(x) = s \cdot x$ soddisfa anche la promessa del problema di Deutsch-Jozsa: se s=00...00, allora la funzione è costante (restituisce sempre 0 per ogni stringa x). Se s è qualsiasi altra stringa, allora la funzione è bilanciata. Quindi, applicando l'algoritmo di Deutsch-Jozsa a una di queste funzioni si risolvono entrambi i problemi simultaneamente! Restituisce la stringa e, se quella stringa è 00...00, sappiamo che è costante; se c'è almeno un "1" nella stringa, sappiamo che è bilanciata.

Possiamo anche verificare che questo algoritmo risolva con successo il problema di Bernstein-Vazirani testandolo sperimentalmente. Prima, creiamo la funzione B-V che vive all'interno della scatola nera:

# Step 1: Map the problem

def bv_function(s):
    """
    Create a Bernstein-Vazirani function from a string of 1s and 0s.
    """
    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc

display(bv_function("1000").draw("mpl"))

string = "1000"  # secret string that we'll pretend we don't know or have access to
n = len(string)

qc = QuantumCircuit(n + 1, n)
qc.x(n)
qc.h(range(n + 1))
qc.barrier()
# qc.compose(oracle, inplace = True)
qc.compose(bv_function(string), inplace=True)
qc.barrier()
qc.h(range(n))
qc.measure(range(n), range(n))

qc.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)

{'0000': 1}

Quindi, con una sola query, l'algoritmo di Deutsch-Jozsa restituirà la stringa $s$ usata nella funzione: $f(x)=x \cdot s$ quando lo applichiamo al problema di Bernstein-Vazirani. Con un algoritmo classico, sarebbero necessarie $n$ query per risolvere lo stesso problema.

Conclusione

Speriamo che esaminando questi semplici esempi ti abbiamo dato una migliore intuizione su come i computer quantistici riescano a sfruttare la sovrapposizione, l'entanglement e l'interferenza per ottenere la loro potenza rispetto ai computer classici.

L'algoritmo di Deutsch-Jozsa ha un'enorme importanza storica perché fu il primo a dimostrare qualsiasi accelerazione rispetto a un algoritmo classico, ma si trattava solo di un'accelerazione polinomiale. L'algoritmo di Deutsch-Jozsa è solo l'inizio della storia.

Dopo aver usato l'algoritmo per risolvere il loro problema, Bernstein e Vazirani lo utilizzarono come base per un problema più complicato e ricorsivo chiamato il problema del campionamento di Fourier ricorsivo. La loro soluzione offriva un'accelerazione super-polinomiale rispetto agli algoritmi classici. E anche prima di Bernstein e Vazirani, Peter Shor aveva già elaborato il suo famoso algoritmo che permetteva ai computer quantistici di fattorizzare grandi numeri in modo esponenzialmente più veloce rispetto a qualsiasi algoritmo classico. Questi risultati, collettivamente, mostrarono la promessa entusiasmante dei futuri computer quantistici e spinsero fisici e ingegneri a rendere reale questo futuro.

Domande

Gli insegnanti possono richiedere versioni di questi notebook con le chiavi delle risposte e indicazioni sul posizionamento nei curricula più comuni compilando questo breve sondaggio su come vengono utilizzati i notebook.

Concetti fondamentali

• Gli algoritmi di Deutsch e Deutsch-Jozsa usano il parallelismo quantistico combinato con l'interferenza per trovare la risposta a un problema più velocemente di quanto possa fare un computer classico.
• Il meccanismo di phase kickback è un fenomeno quantistico controintuitivo che trasferisce operazioni su un qubit alla fase di un altro qubit. Gli algoritmi di Deutsch e Deutsch-Jozsa utilizzano questo meccanismo.
• L'algoritmo di Deutsch-Jozsa offre un'accelerazione polinomiale rispetto a qualsiasi algoritmo classico deterministico.
• L'algoritmo di Deutsch-Jozsa può essere applicato a un problema diverso, chiamato il problema di Bernstein-Vazirani, per trovare una stringa nascosta codificata in una funzione.

Vero/falso

1. V/F L'algoritmo di Deutsch è un caso speciale dell'algoritmo di Deutsch-Jozsa in cui l'input è un singolo qubit.
2. V/F Gli algoritmi di Deutsch e Deutsch-Jozsa usano la sovrapposizione quantistica e l'interferenza per raggiungere la loro efficienza.
3. V/F L'algoritmo di Deutsch-Jozsa richiede più valutazioni della funzione per determinare se una funzione è costante o bilanciata.
4. V/F L'"algoritmo di Bernstein-Vazirani" è in realtà lo stesso dell'algoritmo di Deutsch-Jozsa, applicato a un problema diverso.
5. V/F L'algoritmo di Bernstein-Vazirani può trovare più stringhe segrete simultaneamente.

Risposta breve

1. Quanto tempo impiegherebbe un algoritmo classico per risolvere il problema di Deutsch-Jozsa nel caso peggiore?

2. Quanto tempo impiegherebbe un algoritmo classico per risolvere il problema di Bernstein-Vazirani? Quale accelerazione offre l'algoritmo DJ in questo caso?

3. Descrivi il meccanismo di phase kickback e come funziona per risolvere i problemi di Deutsch-Jozsa e Bernstein-Vazirani.

Problema avanzato

1. L'algoritmo di Deutsch-Jozsa: Ricorda che sopra ti è stato chiesto di calcolare gli stati intermedi dei qubit $\pi_1$ e $\pi_2$ dell'algoritmo di Deutsch. Fai lo stesso per gli stati intermedi a $n+1$ qubit $\pi_1$ e $\pi_2$ dell'algoritmo di Deutsch-Jozsa, per il caso specifico di $n=2$. Poi, verifica che $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$, ancora, per il caso specifico di $n=2$.