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

Articolo
04/17/2024

Nota

Microsoft Quantum Development Kit (QDK classico) non sarà più supportato dopo il 30 giugno 2024. Se si è uno sviluppatore QDK esistente, è consigliabile passare al nuovo azure Quantum Development Kit (QDK moderno) per continuare a sviluppare soluzioni quantistiche. Per altre informazioni, vedere Eseguire la Q# migrazione del codice a QDK moderno.

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 si apprenderà come:

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

Suggerimento

Per accelerare il percorso di calcolo quantistico, vedere Codice con Azure Quantum, una funzionalità univoca del sito Web di Azure Quantum. In questo caso, è possibile eseguire esempi predefiniti Q# o programmi personalizzati Q# , generare nuovo Q# codice dalle richieste, aprire ed eseguire il codice in VS Code per il Web con un solo clic e porre a Copilot eventuali domande sul calcolo quantistico.

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.
- La versione più recente dell'estensione Di Azure Quantum Development Kit . Per informazioni dettagliate sull'installazione, vedere Installazione di QDK moderno 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: 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:

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.
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.
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:

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, avviare di nuovo.

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 ddall'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 e zeri alternati. Lo fa applicando l'operatore di diffusione di Grover ai qubit di input. L'operazione usa un qubit ausiliario, outputQubit, inizializzato nello stato $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ applicando il $X$ e $H$ gate. 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 inverte 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 esito positivo 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 al numero 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 di inizio, 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-zeros, 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 di tutti.

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 tutti gli stati. Infine, riflette sullo stato di tutti. 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 terminare, 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;
}

È possibile testare il Q# codice con copilot in Azure Quantum gratuitamente. È sufficiente un account di posta elettronica Microsoft (MSA). Per altre informazioni sul Copilot in Azure Quantum, vedere Esplorare Azure Quantum.

Aprire Copilot in Azure Quantum nel browser.

Copiare e incollare il codice seguente nell'editor di codice.

namespace GroversTutorial {
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Diagnostics;

    @EntryPoint()
    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);
        }
    }
}

Suggerimento

Da Copilot in Azure Quantum è possibile aprire il programma in VS Code per il Web facendo clic sul pulsante logo di VS Code nell'angolo destro dell'editor di codice.

Eseguire il programma usando il simulatore in memoria

Selezionare Simulatore in memoria.
Selezionare il numero di scatti da eseguire e fare clic su Esegui.
I risultati vengono visualizzati nell'istogramma e nei campi Risultati .
Fare clic su Spiega codice per richiedere a Copilot di spiegare il codice.

Eseguire il programma usando l'emulatore Quantinuum H-Series

È anche possibile inviare il programma all'emulatore gratuito Quantinuum H-Series. L'emulatore simula un computer quantistico con 20 qubit.

Selezionare l'elenco a discesa Simulatore in memoria e selezionare Quantinuum H-Series Emulator (Emulatore serie H quantinuum).
Selezionare il numero di scatti (attualmente limitati a 20) e selezionare Esegui.

Aprire Visual Studio Code e selezionare File > nuovo file di testo per creare un nuovo file.
Salvare il file come GroversAlgorithm.qs. Questo file conterrà il Q# codice per il programma.

Copiare il codice seguente nel GroversAlgorithm.qs file .

namespace GroversTutorial {
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Diagnostics;

    @EntryPoint()
    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);
        }
    }
}

Prima di eseguire il programma, è necessario impostare il target profilo su Senza restrizioni. Selezionare Visualizza -> Riquadro comandi, cercare QIR, selezionare Q#: Impostare il profilo di Azure Quantum QIR targete quindi selezionare Q#: senza restrizioni.
Per eseguire il programma, selezionare Esegui Q# file dall'icona di riproduzione nell'elenco a discesa in alto a destra oppure premere CTRL+F5. Il programma esegue l'operazione o la funzione contrassegnata con l'attributo @EntryPoint() nel simulatore predefinito.
L'output verrà visualizzato nella console di debug.