Esercitazione: Implementare l'algoritmo di ricerca di Grover in Q#

In questa esercitazione si implementa l'algoritmo di Grover in Q# per risolvere i problemi basati sulla ricerca. Per una spiegazione approfondita della teoria alla base dell'algoritmo di Grover, vedere Teoria dell'algoritmo di ricerca di Grover.

In questa esercitazione:

Prerequisiti

• Per eseguire l'esempio di codice in Copilot in Azure Quantum:

  • Un account di posta elettronica Microsoft (MSA).

• Per sviluppare ed eseguire l'esempio di codice in Visual Studio Code:

  • La versione più recente di Visual Studio Code o aprire VS Code sul Web.
  • Versione più recente dell'estensione di AzureQuantum Development Kit. Per informazioni dettagliate sull'installazione, vedere Installazione di QDK in VS Code.

Definire il problema

L'algoritmo di Grover è uno degli algoritmi più famosi del calcolo quantistico. Il tipo di problema risolto viene spesso definito "ricerca in un database", ma è più accurato considerarlo in termini di problema di ricerca.

Qualsiasi problema di ricerca può essere formulato matematicamente con una funzione astratta $f(x)$ che accetta elementi di ricerca $x$. Se l'elemento $x$ è una soluzione al problema di ricerca, allora $f(x)=1$. Se l'elemento $x$ non è una soluzione, allora $f(x)=0$. Il problema di ricerca consiste nel trovare qualsiasi elemento $x_0$ in modo che $f(x_0)=1$.

Pertanto, è possibile formulare il problema di ricerca come: dato una funzione classica $f(x):\{0,1\}^n \rightarrow\{0,1\}$, dove $n$ è la dimensione bit dello spazio di ricerca, trovare un input $x_0$ per cui $f(x_0)=1$.

Per implementare l'algoritmo di Grover per risolvere un problema di ricerca, è necessario:

1. Trasformare il problema nel formato di un'attività di Grover. Si supponga, ad esempio, di voler trovare i fattori di un numero intero $M$ usando l'algoritmo di Grover. È possibile trasformare il problema di fattorizzazione dei numeri interi in un'attività di Grover creando una funzione $$f_M(x)=1[r],$$ dove $1[r]=1$ se $r=0$ e $1[r]=0$ se $r\neq0$ e $r$ è il resto di $M/x$. In questo modo, i numeri interi $x_i$ che rendono $f_M(x_i)=1$ sono i fattori di $M$ e il problema è stato trasformato in un'attività di Grover.
2. Implementare la funzione dell'attività di Grover come oracolo quantistico. Per implementare l'algoritmo di Grover, è necessario implementare la funzione $f(x)$ dell'attività di Grover come oracolo quantistico.
3. Usare l'algoritmo di Grover con l'oracolo per risolvere l'attività. Dopo aver creato un oracolo quantistico, è possibile collegarlo all'implementazione dell'algoritmo di Grover per risolvere il problema e interpretare l'output.

Algoritmo di Grover

Si supponga che siano presenti $N=2^n$ elementi idonei per il problema di ricerca e che siano indicizzati assegnando a ogni elemento un numero intero compreso tra $0$ e $N-1$. I passaggi dell'algoritmo sono:

1. Iniziare con un registro di $n$ qubit inizializzati nello stato $\ket{0}$.
2. Preparare il registro in una sovrapposizione uniforme applicando $H$ a ogni qubit nel registro: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
3. Applicare le operazioni seguenti al registro $N_{\text{optimal}}$ times:
   1. L'oracolo della fase $O_f$ che applica uno spostamento di fase condizionale di $-1$ per gli elementi della soluzione.
   2. Applicare $H$ a ogni qubit nel registro.
   3. Applicare $-O_0$, uno spostamento di fase condizionale di $-1$ a ogni stato di base computazionale ad eccezione di $\ket{0}$.
   4. Applicare $H$ a ogni qubit nel registro.
4. Misurare il registro per ottenere l'indice di un elemento che è una soluzione con probabilità molto elevata.
5. Controllare l'elemento per verificare se si tratta di una soluzione valida. In caso contrario, ricominciare.

Scrivere il codice per l'algoritmo di Grover in Q#

Questa sezione descrive come implementare l'algoritmo in Q#. Quando si implementa l'algoritmo di Grover, è necessario considerare alcuni aspetti. È necessario definire lo stato contrassegnato, come riflettere su di esso e il numero di iterazioni per cui eseguire l'algoritmo. È anche necessario definire l'oracolo che implementa la funzione dell'attività di Grover.

Definire lo stato contrassegnato

Prima di tutto, definire l'input che si sta tentando di trovare nella ricerca. A tale scopo, scrivere un'operazione che applica i passaggi b, c e d dall'algoritmo di Grover.

Insieme, questi passaggi sono noti anche come operatore di diffusione di Grover $-H^{\otimes n} O_0 H^{\otimes n}$.

operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
    Message("Reflecting about marked state...");
    use outputQubit = Qubit();
    within {
        // We initialize the outputQubit to (|0⟩ - |1⟩) / √2, so that
        // toggling it results in a (-1) phase.
        X(outputQubit);
        H(outputQubit);
        // Flip the outputQubit for marked states.
        // Here, we get the state with alternating 0s and 1s by using the X
        // operation on every other qubit.
        for q in inputQubits[...2...] {
            X(q);
        }
    } apply {
        Controlled X(inputQubits, outputQubit);
    }
}

L'operazione ReflectAboutMarked riflette lo stato di base contrassegnato da zeri alternati e quelli. A tale scopo, applicare l'operatore di diffusione di Grover ai qubit di input. L'operazione usa un qubit ausiliario, , outputQubitche viene inizializzato nello stato $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ applicando i cancelli $X$ e $H$. L'operazione applica quindi il gate $X$ a ogni altro qubit nel registro, che capovolge lo stato del qubit. Infine, applica il gate controllato $X$ al qubit ausiliario e ai qubit di input. Questa operazione capovolge il qubit ausiliario se e solo se tutti i qubit di input si trovano nello stato $\ket{1}$, ovvero lo stato contrassegnato.

Definire il numero di iterazioni ottimali

L'algoritmo di Grover dispone di un numero ottimale di iterazioni che genera la massima probabilità di misurare un output valido. Se il problema ha $N=2^n$ possibili elementi idonei e $M$ di questi sono soluzioni al problema, il numero ottimale di iterazioni è:

$$N_{\text{optimal}}\approx\frac{\pi}{4}\sqrt{\frac{N}{M}}$$

Continuando a eseguire l'iterazione oltre il numero ottimale di iterazioni inizia a ridurre tale probabilità fino a raggiungere la probabilità di successo quasi zero per l'iterazione $2 N_{\text{optimal}}$. Successivamente, la probabilità aumenta di nuovo fino a $3 N_{\text{optimal}}$ e così via.

Nelle applicazioni pratiche in genere non si conosce il numero di soluzioni del problema prima di risolverlo. Una strategia efficiente per gestire questo problema consiste nell'"indovinare" il numero di soluzioni $M$ aumentando progressivamente l'ipotesi in potenze di due (ad esempio $ 1, 2, 4, 8, 16, ..., 2^n$). Una di queste ipotesi sarà così vicina che l'algoritmo troverà comunque la soluzione con un numero medio di iterazioni intorno a $\sqrt{\frac{N}{M}}$.

La funzione seguente Q# calcola il numero ottimale di iterazioni per un determinato numero di qubit in un registro.

function CalculateOptimalIterations(nQubits : Int) : Int {
    if nQubits > 63 {
        fail "This sample supports at most 63 qubits.";
    }
    let nItems = 1 <<< nQubits; // 2^nQubits
    let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
    let iterations = Round(0.25 * PI() / angle - 0.5);
    return iterations;
}

La CalculateOptimalIterations funzione usa la formula precedente per calcolare il numero di iterazioni e quindi la arrotonda all'intero più vicino.

Definire l'operazione di Grover

L'operazione Q# per l'algoritmo di ricerca di Grover ha tre input:

• Numero di qubit, nQubits : Int, nel registro qubit. Questo registro codifica la soluzione provvisoria al problema di ricerca. Dopo l'operazione, verrà misurata.
• Numero di iterazioni ottimali, iterations : Int.
• Operazione, phaseOracle : Qubit[] => Unit) : Result[], che rappresenta l'oracolo di fase per l'attività di Grover. Questa operazione applica una trasformazione unitaria su un registro di qubit generico.

operation GroverSearch( nQubits : Int, iterations : Int, phaseOracle : Qubit[] => Unit) : Result[] {

    use qubits = Qubit[nQubits];
    PrepareUniform(qubits);

    for _ in 1..iterations {
        phaseOracle(qubits);
        ReflectAboutUniform(qubits);
    }

    // Measure and return the answer.
    return MResetEachZ(qubits);
}

L'operazione GroverSearch inizializza un registro di qubit $n$ nello stato $\ket{0}$, prepara il registro in una sovrapposizione uniforme e quindi applica l'algoritmo di Grover per il numero specificato di iterazioni. La ricerca stessa consiste nel riflettere ripetutamente sullo stato contrassegnato e sullo stato iniziale, che è possibile scrivere in Q# come ciclo for. Infine, misura il registro e restituisce il risultato.

Il codice usa tre operazioni helper: PrepareUniform, ReflectAboutUniforme ReflectAboutAllOnes.

Dato un registro nello stato all-zero, l'operazione PrepareUniform prepara una sovrapposizione uniforme su tutti gli stati di base.

operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
    for q in inputQubits {
        H(q);
    }
}

L'operazione ''ReflectAboutAllOnes' riflette lo stato all-ones.

operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
    Controlled Z(Most(inputQubits), Tail(inputQubits));
}

L'operazione ReflectAboutUniform riflette lo stato di sovrapposizione uniforme. Prima di tutto, trasforma la sovrapposizione uniforme in all-zero. Trasforma quindi lo stato all-zero in all-ones. Infine, riflette sullo stato all-ones. L'operazione viene chiamata ReflectAboutUniform perché può essere interpretata geometricamente come una reflection nello spazio vettoriale sullo stato di sovrapposizione uniforme.

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
    within {
        Adjoint PrepareUniform(inputQubits);
        // Transform the all-zero state to all-ones
        for q in inputQubits {
            X(q);
        }
    } apply {
        ReflectAboutAllOnes(inputQubits);
    }
}

Eseguire il codice finale

A questo punto, sono disponibili tutti gli ingredienti per implementare una particolare istanza dell'algoritmo di ricerca di Grover e risolvere il problema della fattorizzazione. Per completare l'operazione, l'operazione Main configura il problema specificando il numero di qubit e il numero di iterazioni

operation Main() : Result[] {
    let nQubits = 5;
    let iterations = CalculateOptimalIterations(nQubits);
    Message($"Number of iterations: {iterations}");
    
    // Use Grover's algorithm to find a particular marked state.
    let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
    return results;
}

Eseguire il programma

Selezionare la piattaforma desiderata per eseguire il programma.

Contenuto correlato

Esplorare altre esercitazioni su Q#:

• L'entanglement quantistico mostra come scrivere un Q# programma che manipola e misura i qubit e illustra gli effetti della sovrapposizione e dell'entanglement.
• Il generatore di numeri casuali quantistici mostra come scrivere un Q# programma che genera numeri casuali da qubit in sovrapposizione.
• Quantum Fourier Transform illustra come scrivere un Q# programma che punta direttamente a qubit specifici.
• I kata quantistici sono esercitazioni e esercizi di programmazione auto-ritmo volti a insegnare contemporaneamente gli elementi del calcolo quantistico e Q# della programmazione.