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

  • Articolo
  • 16 minuti per la lettura

Questa esercitazione descrive come implementare l'algoritmo di Grover in Q# per risolvere i problemi basati sulla ricerca.

L'algoritmo di Grover è uno degli algoritmi più famosi del calcolo quantistico. Il problema che risolve viene spesso definito "ricerca in un database", ma è più accurato pensarlo 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$.

Nota

Questa esercitazione è destinata a utenti che hanno già acquisito familiarità con l'algoritmo di Grover e vogliono imparare a implementarlo in Q#. Per un'esercitazione più introduttiva, vedere il modulo Learn Risolvere i problemi di colorazione del grafo usando la ricerca di Grover. 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:

  • Creare un oracolo quantistico che implementi le funzioni classiche in un computer quantistico.
  • Scrivere un programma Q# che usa l'algoritmo di Grover per trovare i fattori di un numero intero.

Prerequisiti

Nota

Per usare la procedura facoltativa Extra: Verificare le statistiche con Python, è necessario un ambiente di sviluppo Python per la configurazione di Q#. Per altre informazioni, vedere Configurare un ambiente Q# e Python.

Attività e background dell'algoritmo di Grover

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, è 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.

Revisione rapida dell'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}}$ 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.
  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, avviare di nuovo.

Scrivere il codice per l'algoritmo di Grover

Questa sezione descrive come implementare l'algoritmo in Q#.

Operatore di diffusione di Grover

Scrivere, innanzitutto, un'operazione che applichi i passaggi b, c e d dal ciclo precedente. Insieme, questi passaggi sono noti anche come operatore di diffusione di Grover $-H^{\otimes n} O_0 H^{\otimes n}$

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {

    within {
        ApplyToEachA(H, inputQubits);
        ApplyToEachA(X, inputQubits);
    } apply {
        Controlled Z(Most(inputQubits), Tail(inputQubits));
    }

}

Questa operazione usa l'istruzione within-apply che implementa la coniugazione automatica delle operazioni che si verificano nell'operatore di diffusione di Grover.

Nota

Per altre informazioni sulle coniugazioni in Q#, vedere Coniugazioni nella guida al linguaggio Q#.

Un buon esercizio per comprendere il codice e le operazioni è verificare con carta e penna che l'operazione ReflectAboutUniform applichi l'operatore di diffusione di Grover. A tale scopo, si noti che l'operazione Controlled Z(Most(inputQubits),Tail(inputQubits)) ha un effetto diverso dall'identità se, e solo se, tutti i qubit sono nello stato $\ket{1}$.

L'operazione viene chiamata ReflectAboutUniform perché può essere interpretata geometricamente come una reflection nello spazio vettoriale sullo stato di sovrapposizione uniforme.

Number of iterations

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

Le iterazioni eseguite oltre il numero ottimale iniziano a ridurre la probabilità fino a raggiungere una probabilità di successo pari quasi a zero nell'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}}$.

Completare l'operazione di Grover

A questo punto, è possibile scrivere un'operazione Q# per l'algoritmo di ricerca di Grover. Avrà tre input:

  • Una matrice di qubit register : Qubit[] che deve essere inizializzata nell'intero stato Zero. Questo registro codifica la soluzione provvisoria al problema di ricerca. Dopo l'operazione verrà misurata.
  • Un'operazione phaseOracle : (Qubit[]) => Unit is Adj che rappresenta l'oracolo della fase per l'attività di Grover. Questa operazione applica una trasformazione unitaria su un registro di qubit generico.
  • Un intero iterations : Int che rappresenta le iterazioni dell'algoritmo.
operation RunGroversSearch(register : Qubit[], phaseOracle : (Qubit[]) => Unit is Adj, iterations : Int) : Unit {
    // Prepare register into uniform superposition.
    ApplyToEach(H, register);
    // Start Grover's loop.
    for _ in 1 .. iterations {
        // Apply phase oracle for the task.
        phaseOracle(register);
        // Apply Grover's diffusion operator.
        ReflectAboutUniform(register);
    }
}

Suggerimento

Questo codice è generico, ovvero può essere usato per risolvere qualsiasi problema di ricerca. L'oracolo quantistico, l'unica operazione che si basa sulla conoscenza dell'istanza del problema da risolvere, viene passato come parametro al codice di ricerca.

Scrivere il codice per implementare l'oracolo

Una delle proprietà principali che rende l'algoritmo di Grover più rapido è la capacità dei computer quantistici di eseguire calcoli non solo su singoli input ma anche sulle sovrapposizioni di input. È necessario calcolare la funzione $f(x)$ che descrive l'istanza di un problema di ricerca usando solo operazioni quantistiche. In questo modo, può essere calcolato su una sovrapposizione di input.

Sfortunatamente non esiste un modo automatico per convertire le funzioni classiche in operazioni quantistiche. Si tratta di un campo di ricerca aperto in ambito informatico, denominato computazione reversibile.

Esistono tuttavia alcune linee guida che possono essere utili per convertire la funzione $f(x)$ in un oracolo quantistico:

  1. Suddividere la funzione classica in piccoli blocchi facili da implementare. Ad esempio, è possibile provare a scomporre la funzione $f(x)$ in una serie di operazioni aritmetiche o porte logiche booleane.
  2. Usare i blocchi predefiniti di livello superiore della libreria Q# per implementare le operazioni intermedie. Ad esempio, se la funzione è stata scomposta in una combinazione di semplici operazioni aritmetiche, è possibile usare la libreria per il calcolo numerico per implementare le operazioni intermedie.

La tabella di equivalenza seguente potrebbe risultare utile quando si implementano funzioni booleane in Q#.

Porta logica classica Operazione Q#
$NOT$ X
$XOR$ CNOT
$AND$ CCNOT con un qubit ausiliario

Creare un'operazione quantistica per verificare se un numero è un divisore

Importante

Questa esercitazione consente di fattorizzare un numero usando l'algoritmo di ricerca di Grover come esempio didattico per illustrare come convertire un semplice problema matematico in un'attività di Grover. Tuttavia, l'algoritmo di Grover non è un algoritmo efficiente per risolvere il problema della fattorizzazione dei numeri interi. Per esplorare un algoritmo quantistico che risolva il problema di fattorizzazione dei numeri interi più velocemente di qualsiasi algoritmo classico, vedere l'esempio dell'algoritmo di Shor.

L'esempio seguente illustra come esprimere la funzione $f_M(x)=1[r]$ del problema di fattorizzazione come operazione quantistica in Q#.

Seguendo un approccio classico, si calcola il resto della divisione $M/x$ e si verifica se è uguale a zero. In caso affermativo, il programma restituisce 1 e, in caso contrario, restituisce 0. È necessario:

  • Calcolare il resto della divisione.
  • Applicare un'operazione controllata sul bit di output in modo che sia 1 se il resto è 0.

È necessario calcolare una divisione di due numeri con un'operazione quantistica. Fortunatamente, non è necessario scrivere il circuito che implementa la divisione da zero. È invece possibile usare l'operazione DivideI dalla libreria di calcolo numerico.

Esaminando la descrizione di DivideI, si afferma che sono necessari tre registri di qubit: il dividendo $n$-bit xs, il divisore $n$-bit ys e $n$-bit result che deve essere inizializzato nello stato Zero. L'operazione è Adj + Ctl, quindi è possibile coniugarla e usarla nelle istruzioni within-apply. Inoltre, la descrizione esplicita che il dividendo nel registro di input xs viene sostituito dal resto. Questo è perfetto, poiché si è interessati esclusivamente al resto e non al risultato dell'operazione.

È quindi possibile compilare un'operazione quantistica che esegue le operazioni seguenti:

  1. Accetta tre input:
    • Il dividendo, number : Int. Ovvero $M$ in $f_M(x)$.
    • Una matrice qubit che codifica il divisore, divisorRegister : Qubit[]. Ovvero $x$ in $f_M(x)$, possibilmente in uno stato di sovrapposizione.
    • Un qubit di destinazione, target : Qubit, che si inverte se l'output di $f_M(x)$ è $1$.
  2. Calcola la divisione $M/x$ usando solo operazioni quantistiche reversibili e inverte lo stato di target se, e solo se, il resto è zero.
  3. Ripristina tutte le operazioni ad eccezione dell'inversione di target, in modo da restituire i qubit ausiliari usati allo stato zero senza introdurre operazioni irreversibili, ad esempio la misurazione. Questo passaggio è importante per mantenere l'entanglement e la sovrapposizione durante il processo.

Il codice per implementare questa operazione quantistica è:

operation MarkDivisor (
    dividend : Int,
    divisorRegister : Qubit[],
    target : Qubit
) : Unit is Adj + Ctl {
    // Calculate the bit-size of the dividend.
    let size = BitSizeI(dividend);
    // Allocate two new qubit registers for the dividend and the result.
    use dividendQubits = Qubit[size];
    use resultQubits = Qubit[size];
    // Create new LittleEndian instances from the registers to use DivideI
    let xs = LittleEndian(dividendQubits);
    let ys = LittleEndian(divisorRegister);
    let result = LittleEndian(resultQubits);

    // Start a within-apply statement to perform the operation.
    within {
        // Encode the dividend in the register.
        ApplyXorInPlace(dividend, xs);
        // Apply the division operation.
        DivideI(xs, ys, result);
        // Flip all the qubits from the remainder.
        ApplyToEachA(X, xs!);
    } apply {
        // Apply a controlled NOT over the flipped remainder.
        Controlled X(xs!, target);
        // The target flips if and only if the remainder is 0.
    }
}

Nota

Il programma sfrutta l'istruzione within-apply per ottenere il passaggio 3. In alternativa, è possibile scrivere in modo esplicito gli elementi adiacenti di ogni operazione all'interno del blocco within dopo l'inversione controllata di target. L'istruzione within-apply esegue questa operazione, rendendo il codice più breve e leggibile. Uno degli obiettivi principali di Q# è semplificare la scrittura e la lettura dei programmi quantistici.

Trasformare l'operazione in un oracolo della fase

L'operazione è nota come oracolo di MarkDivisorcontrassegno, poiché contrassegna gli elementi validi con un qubit ausiliario con entanglement ().target Tuttavia, l'algoritmo di Grover richiede un oracolo della fase, ovvero un oracolo che applica uno spostamento di fase condizionale di $-1$ per gli elementi della soluzione. Questo non rappresenta un problema, l'operazione precedente non è stata scritta invano. È molto semplice passare da un tipo di oracolo all'altro in Q#.

È possibile applicare qualsiasi oracolo di contrassegno come oracolo di fase con l'operazione seguente:

operation ApplyMarkingOracleAsPhaseOracle(
    markingOracle : (Qubit[], Qubit) => Unit is Adj,
    register : Qubit[]
) : Unit is Adj {
    use target = Qubit();
    within {
        X(target);
        H(target);
    } apply {
        markingOracle(register, target);
    }
}

Questa trasformazione è spesso nota come contraccolpo di fase ed è ampiamente usata in molti algoritmi di calcolo quantistico. È possibile trovare una spiegazione dettagliata di questa tecnica in questo modulo di Learn.

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. Il codice finale avrà un aspetto simile al seguente:

namespace GroversTutorial {
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Arithmetic;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Preparation;

    @EntryPoint()
    operation FactorizeWithGrovers(number : Int) : Unit {

        // Define the oracle that for the factoring problem.
        let markingOracle = MarkDivisor(number, _, _);
        let phaseOracle = ApplyMarkingOracleAsPhaseOracle(markingOracle, _);
        // Bit-size of the number to factorize.
        let size = BitSizeI(number);
        // Estimate of the number of solutions.
        let nSolutions = 4;
        // The number of iterations can be computed using the formula.
        let nIterations = Round(PI() / 4.0 * Sqrt(IntAsDouble(size) / IntAsDouble(nSolutions)));

        // Initialize the register to run the algorithm
        use (register, output) = (Qubit[size], Qubit());
        mutable isCorrect = false;
        mutable answer = 0;
        // Use a Repeat-Until-Succeed loop to iterate until the solution is valid.
        repeat {
            RunGroversSearch(register, phaseOracle, nIterations);
            let res = MultiM(register);
            set answer = BoolArrayAsInt(ResultArrayAsBoolArray(res));
            // See if the result is a solution with the oracle.
            markingOracle(register, output);
            if MResetZ(output) == One and answer != 1 and answer != number {
                set isCorrect = true;
            }
            ResetAll(register);
        } until isCorrect;

        // Print out the answer.
        Message($"The number {answer} is a factor of {number}.");

    }

    operation MarkDivisor (
        dividend : Int,
        divisorRegister : Qubit[],
        target : Qubit
    ) : Unit is Adj+Ctl {
        let size = BitSizeI(dividend);
        use (dividendQubits, resultQubits) = (Qubit[size], Qubit[size]);
        let xs = LittleEndian(dividendQubits);
        let ys = LittleEndian(divisorRegister);
        let result = LittleEndian(resultQubits);
        within{
            ApplyXorInPlace(dividend, xs);
            DivideI(xs, ys, result);
            ApplyToEachA(X, xs!);
        }
        apply{
            Controlled X(xs!, target);
        }
    }

    operation PrepareUniformSuperpositionOverDigits(digitReg : Qubit[]) : Unit is Adj + Ctl {
        PrepareArbitraryStateCP(ConstantArray(10, ComplexPolar(1.0, 0.0)), LittleEndian(digitReg));
    }

    operation ApplyMarkingOracleAsPhaseOracle(
        markingOracle : (Qubit[], Qubit) => Unit is Adj,
        register : Qubit[]
    ) : Unit is Adj {
        use target = Qubit();
        within {
            X(target);
            H(target);
        } apply {
            markingOracle(register, target);
        }
    }

    operation RunGroversSearch(register : Qubit[], phaseOracle : ((Qubit[]) => Unit is Adj), iterations : Int) : Unit {
        ApplyToEach(H, register);
        for _ in 1 .. iterations {
            phaseOracle(register);
            ReflectAboutUniform(register);
        }
    }

    operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
        within {
            ApplyToEachA(H, inputQubits);
            ApplyToEachA(X, inputQubits);
        } apply {
            Controlled Z(Most(inputQubits), Tail(inputQubits));
        }
    }
}

Usare il programma per trovare un fattore di 21. Per semplificare il codice, si supponga di conoscere il numero di elementi validi, $M$. In questo caso, $M=4$, poiché esistono due fattori, 3 e 7, più 1 e 21.

Eseguire il programma con Visual Studio o Visual Studio Code

Il programma descritto in precedenza eseguirà l'operazione o la funzione contrassegnata con l'attributo @EntryPoint() in un simulatore o in un'utilità di stima delle risorse, a seconda della configurazione del progetto e delle opzioni della riga di comando.

Questa esercitazione richiede la libreria Microsoft.Quantum.Numerics. Per altre informazioni, seguire la procedura per installare librerie quantistiche aggiuntive al progetto.

In generale, l'esecuzione di un programma Q# in Visual Studio è semplice come premere Ctrl + F5. Prima di tutto, tuttavia, è necessario fornire al programma gli argomenti della riga di comando necessari.

Gli argomenti della riga di comando possono essere configurati tramite la pagina di debug delle proprietà del progetto. Per altre informazioni, è possibile visitare la guida di riferimento di Visual Studio oppure seguire questa procedura:

  1. A destra in Esplora soluzioni fare clic con il pulsante destro del mouse sul nome del progetto (nodo del progetto, un livello sotto la soluzione) e scegliere Proprietà.

  2. Dalla nuova finestra visualizzata passare alla schedaDebug.

  3. Nel campo Argomenti applicazione è possibile immettere gli argomenti da passare al punto di ingresso del programma. Immettere --number 21 nel campo degli argomenti.

Premere Ctrl + F5 per eseguire il programma.

In entrambi gli ambienti, dovrebbe essere visualizzato il messaggio seguente nel terminale:

The number 7 is a factor of 21.

Extra: Verificare le statistiche con Python

Come è possibile verificare che l'algoritmo funzioni correttamente? Ad esempio, se si sostituisce l'algoritmo di Grover con un generatore di numeri casuali nell'esempio di codice precedente, è possibile che troverà comunque un fattore (dopo ~$N$ tentativi).

Questo esempio illustra come scrivere un breve script Python per verificare che il programma funzioni come dovrebbe.

Suggerimento

Per informazioni sull'esecuzione Q# di applicazioni con Python, vedere Configurare Quantum Development Kit e Sviluppare con Q# e Python.

Sostituire innanzitutto l'operazione principale, FactorizeWithGrovers, con l'operazione seguente, FactorizeWithGrovers2:

@EntryPoint()
operation FactorizeWithGrovers2(number : Int) : Int {

    let markingOracle = MarkDivisor(number, _, _);
    let phaseOracle = ApplyMarkingOracleAsPhaseOracle(markingOracle, _);
    let size = BitSizeI(number);
    let nSolutions = 4;
    let nIterations = Round(PI() / 4.0 * Sqrt(IntAsDouble(size) / IntAsDouble(nSolutions)));

    use register = Qubit[size] {
        RunGroversSearch(register, phaseOracle, nIterations);
        let res = MultiM(register);
        return ResultArrayAsInt(res);
        // Verify whether the result is correct.
    }

}

Prendere nota delle modifiche rispetto all'operazione originale:

  • Il tipo di output è stato modificato da Unit a Int, che è più utile per il programma Python.
  • Il ciclo di ripetizione fino al completamento è stato rimosso. Viene invece restituito il primo risultato della misurazione dopo l'esecuzione dell'algoritmo di Grover.

Il programma Python è molto semplice: chiama l'operazione FactorizeWithGrovers2 più volte e traccia i risultati in un istogramma.

Salvare il codice seguente come file Python nella cartella del progetto:

import qsharp
qsharp.packages.add("Microsoft.Quantum.Numerics")
qsharp.reload()
from GroversTutorial import FactorizeWithGrovers2
import matplotlib.pyplot as plt
import numpy as np

def main():

    # Instantiate variables
    frequency =  {}
    N_Experiments = 1000
    results = []
    number = 21

    # Run N_Experiments times the Q# operation.
    for i in range(N_Experiments):
        print(f'Experiment: {i} of {N_Experiments}')
        results.append(FactorizeWithGrovers2.simulate(number = number))

    # Store the results in a dictionary
    for i in results:
        if i in frequency:
            frequency[i]=frequency[i]+1
        else:
            frequency[i]=1

    # Sort and print the results
    frequency = dict(reversed(sorted(frequency.items(), key=lambda item: item[1])))
    print('Output,  Frequency' )
    for k, v in frequency.items():
        print(f'{k:<8} {v}')

    # Plot an histogram with the results
    plt.bar(frequency.keys(), frequency.values())
    plt.xlabel("Output")
    plt.ylabel("Frequency of the outputs")
    plt.title("Outputs for Grover's factoring. N=21, 1000 iterations")
    plt.xticks(np.arange(1, 33, 2.0))
    plt.show()

if __name__ == "__main__":
    main()

Nota

La riga from GroversTutorial import FactorizeWithGrovers2 nel programma Python importa il codice Q# scritto in precedenza. Si noti che il nome del modulo Python (GroversTutorial) deve essere identico allo spazio dei nomi dell'operazione che si vuole importare (in questo caso, FactorizeWithGrovers2). Sarà necessario il pacchetto Matplotlib per visualizzare l'istogramma. Per altre informazioni, vedere Matploblib.

Il programma genera l'istogramma seguente:

Istogramma con i risultati dell'esecuzione più volte dell'algoritmo di Grover.

Come si può vedere nell'istogramma, l'algoritmo restituisce le soluzioni al problema di ricerca (1, 3, 7 e 21) con probabilità molto più elevata rispetto alle non soluzioni. È possibile pensare all'algoritmo di Grover come a un generatore casuale quantistico che è intenzionalmente sbilanciato verso gli indici che rappresentano soluzioni al problema di ricerca.

Passaggi successivi

Per altri esempi di codice di Q# che usano l'algoritmo di Grover, vedere la pagina degli esempi di codice o provare a trasformare un problema matematico in un problema di ricerca e risolverlo con Q# e l'algoritmo di Grover.