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:

Definire l'algoritmo di Grover per un problema di ricerca
Implementare l'algoritmo di Grover in Q#

Prerequisiti

Per sviluppare ed eseguire l'esempio di codice in Visual Studio Code (VS Code), è necessario installare gli strumenti seguenti:

La versione più recente di VS Code o aprire VS Code per il Web.
La versione più recente dell'estensione (QDK)Microsoft Quantum Development Kit. Per informazioni dettagliate sull'installazione, vedere Configurare QDK.

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 qualsiasi problema di ricerca come: data una funzione classica $f(x):\{0,1\}^n \rightarrow\{0,1\}$, dove $n$ è la dimensione in 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:

Trasforma il problema nella forma 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.
Implementare la funzione del compito di Grover come oracolo quantistico. Per implementare l'algoritmo di Grover, è necessario implementare la funzione $f(x)$ dell'attività di Grover come oracolo quantistico.
Usare l'algoritmo di Grover con l'oracolo per risolvere il compito. 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:

Iniziare con un registro di $n$ qubit inizializzati nello stato $\ket{0}$.
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$$
Applicare le operazioni seguenti al registro $N_{\text{optimal}}$ volte.
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.
Misurare il registro per ottenere l'indice di un elemento che è una soluzione con probabilità molto elevata.
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 sullo stato di base contrassegnato da segni alternati di zeri e uni. A tale scopo, applica 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 illustrata in precedenza 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 per il problema di ricerca e viene misurata dopo l'operazione.
Numero di iterazioni ottimali, iterations : Int.
Un'operazione, phaseOracle : Qubit[] => Unit) : Result[], che rappresenta l'oracolo di fase per il compito di Grover. Questa operazione applica una trasformazione unitaria su un registro 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 in modo iterativo sullo stato contrassegnato e sullo stato iniziale, che può essere scritto 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 riflessione nello spazio vettoriale rispetto allo 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

In VS Code aprire il menu File e scegliere Nuovo file di testo per creare un nuovo file.
Salvare il file come GroversAlgorithm.qs. Questo file contiene il codice Q# per il programma.

Copiare il codice seguente nel file GroversAlgorithm.qs.


import Std.Convert.*;
import Std.Math.*;
import Std.Arrays.*;
import Std.Measurement.*;
import Std.Diagnostics.*;


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;
}

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

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;
}

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

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

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

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
    within {
        // Transform the uniform superposition to all-zero.
        Adjoint PrepareUniform(inputQubits);
        // Transform the all-zero state to all-ones
        for q in inputQubits {
            X(q);
        }
    } apply {
        // Now that we've transformed the uniform superposition to the
        // all-ones state, reflect about the all-ones state, then let the
        // within/apply block transform us back.
        ReflectAboutAllOnes(inputQubits);
    }
}

Per eseguire il programma, scegliere Esegui dal menu per l'operazione Main oppure premere CTRL+F5. Per impostazione predefinita, il compilatore esegue l'operazione o la Main funzione nel simulatore predefinito.
L'output viene visualizzato nella console di debug nel terminale.

Nota

Se il profilo QIR target non è impostato su Senza restrizioni, viene visualizzato un errore quando si esegue il programma. Per questo programma, il compilatore imposta automaticamente il target profilo su Senza restrizioni , a meno che non si imposti il profilo manualmente.

Esplora altri tutorial di 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 autogestiti volti a insegnare gli elementi del calcolo quantistico e della programmazione contemporaneamente.

Commenti e suggerimenti

Questa pagina è stata utile?

Last updated on 2026-05-19