Kurz: Implementace Groverova vyhledávacího algoritmu v Q#

V tomto kurzu implementujete Groverův algoritmus Q# k řešení problémů založených na vyhledávání. Podrobné vysvětlení teorie groverova algoritmu najdete v teorii Groverova algoritmu.

V tomto kurzu se naučíte:

• Definování Groverova algoritmu pro problém hledání
• Implementace Groverova algoritmu v Q#

Tip

Pokud chcete urychlit cestu k kvantovému computingu, podívejte se na kód s Využitím Azure Quantum, která je jedinečnou funkcí webu Azure Quantum. Tady můžete spouštět předdefinované Q# ukázky nebo vlastní Q# programy, vygenerovat nový Q# kód z výzev, otevřít a spustit kód ve VS Code pro web jedním kliknutím a pokládat Copilot jakékoli otázky týkající se kvantového computingu.

Požadavky

• Spuštění ukázky kódu v Copilotu v Azure Quantum:

  • E-mailový účet Microsoft (MSA).

• Vývoj a spuštění ukázky kódu v editoru Visual Studio Code:

  • Nejnovější verze editoru Visual Studio Code nebo otevření editoru VS Code na webu
  • Nejnovější verze rozšíření AzureQuantum Development Kit. Podrobnosti o instalaci najdete v tématu Instalace sady QDK ve VS Code.

Definování problému

Groverův algoritmus je jedním z nejznámějších algoritmů v kvantových výpočtech. Typ problému, který řeší, se často označuje jako "vyhledávání v databázi", ale je přesnější si ho představit z hlediska problému hledání.

Jakýkoli problém hledání lze matematicky formulovat pomocí abstraktní funkce $f(x)$, která přijímá položky hledání $x$. Pokud je položka $x$ řešením problému hledání, $f(x)=1$. Pokud položka $x$ není řešení, $f(x)=0$. Problém hledání se skládá z vyhledání libovolné položky $x_0$, aby $f(x_0)=1$.

Jakýkoli problém hledání tedy můžete formulovat takto: vzhledem k klasické funkci $f(x):\{0,1\}^n \rightarrow\{0,1\}$, kde $n$ je bitová velikost vyhledávacího prostoru, vyhledejte vstupní $x_0$, pro který $f(x_0)=1$.

Pokud chcete implementovat Groverův algoritmus pro řešení problému hledání, musíte:

1. Transformujte problém na formu Groverova úkolu. Předpokládejme například, že chcete najít faktory celočíselného $M$ pomocí Groverova algoritmu. Problém celočíselného faktorizace můžete transformovat na úkol Grovera tak, že vytvoříte funkci $$f_M(x)=1[r],$$ kde $1[r]=1$ pokud $r=0$ a $1[r]=0$, pokud $r\neq0$ a $r$ je zbytek $M/x$. Tímto způsobem jsou celá čísla $x_i$, které $f_M(x_i)=1$ jsou faktory $M$ a transformovali jste problém na groverův úkol.
2. Implementujte funkci groverova úkolu jako kvantové orákulum. Pokud chcete implementovat Groverův algoritmus, musíte implementovat funkci $f(x)$ úlohy Groveru jako kvantové orákulum.
3. K vyřešení úkolu použijte Groverův algoritmus s orákulumem. Jakmile máte kvantový orákulum, můžete ho připojit k implementaci groverova algoritmu, abyste vyřešili problém a interpretovali výstup.

Groverův algoritmus

Předpokládejme, že existuje $N=2^n$ způsobilých položek pro problém hledání a indexují se tak, že každé položce přiřadíte celé číslo od $0$ k $N-1$. Kroky algoritmu jsou:

1. Začněte registrem qubitů $n$ inicializovaných ve stavu $\ket{0}$.
2. Připravte registr do jednotné superpozice použitím $H$ u každého qubitu v registru: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
3. Při registraci použijte následující operace $N_{\text{optimal}}$ krát:
   1. Orákula fáze $O_f$, která používá pro položky řešení posun podmíněné fáze $-1$.
   2. Použijte $H$ na každý qubit v registru.
   3. Použijte $-O_0$, podmíněný posun fáze $-1$ na každý výpočetní základní stav s výjimkou $\ket{0}$.
   4. Použijte $H$ na každý qubit v registru.
4. Změřte registr a získejte index položky, která je řešením s velmi vysokou pravděpodobností.
5. Zkontrolujte položku a zkontrolujte, jestli se jedná o platné řešení. Pokud ne, začněte znovu.

Napsání kódu pro Groverův algoritmus v Q#

Tato část popisuje, jak implementovat algoritmus v Q#. Při implementaci Groverova algoritmu je potřeba vzít v úvahu několik věcí. Musíte definovat, pro jaký je váš označený stav, jak ho odrážet a kolik iterací se má algoritmus spustit. Musíte také definovat orákulum, který implementuje funkci úlohy Grovera.

Definování označeného stavu

Nejprve definujete, jaký vstup se pokoušíte najít ve vyhledávání. Uděláte to tak, že napíšete operaci, která použije kroky b, c a d z Groverova algoritmu.

Tyto kroky se také označují jako Groverův operátor difúze $-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);
    }
}

Operace ReflectAboutMarked odráží základní stav označený střídavými nulami a nulami. Provede to použitím operátoru Groverova difuzního operátoru na vstupní qubity. Operace používá pomocný qubit, outputQubitkterý se inicializuje ve stavu $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ použitím bran $X$ a $H$. Operace pak použije bránu $X$ na každý druhý qubit v registru, který překlopí stav qubitu. Nakonec použije kontrolovanou bránu $X$ na pomocný qubit a vstupní qubity. Tato operace překlopí pomocný qubit, pokud jsou všechny vstupní qubity ve stavu $\ket{1}$, což je označený stav.

Definování počtu optimálních iterací

Groverovo hledání má optimální počet iterací, které poskytují nejvyšší pravděpodobnost měření platného výstupu. Pokud problém obsahuje $N=2^n$ možné způsobilé položky a $M$ z nich jsou řešení problému, je optimální počet iterací:

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

Pokračování iterace po optimálním počtu iterací začne snižovat pravděpodobnost, dokud nedosáhnete téměř nulové pravděpodobnosti úspěchu při iteraci $2 N_{\text{optimal}}$. Potom se pravděpodobnost znovu zvětšuje až do $3 N_{\text{optimal}}$ atd.

V praktických aplikacích obvykle nevíte, kolik řešení váš problém má, než ho vyřešíte. Efektivní strategií pro řešení tohoto problému je "odhadovat" počet řešení $M$ postupným zvýšením odhadu v mocninách dvou (tj. $1, 2, 4, 8, 16, ..., 2^n$). Jeden z těchto odhadů bude dostatečně blízko, aby algoritmus stále našel řešení s průměrným počtem iterací kolem $\sqrt{\frac{N}{M}}$.

Následující Q# funkce vypočítá optimální počet iterací pro daný počet qubitů v registru.

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

Funkce CalculateOptimalIterations použije výše uvedený vzorec k výpočtu počtu iterací a potom ho zaokrouhlí na nejbližší celé číslo.

Definování operace Groveru

Operace Q# groverova vyhledávacího algoritmu má tři vstupy:

• Počet qubitů, nQubits : Intv registru qubitů. Tento registr zakóduje nezávazné řešení problému hledání. Po operaci se bude měřit.
• Počet optimálních iterací, iterations : Int.
• Operace, phaseOracle : Qubit[] => Unit) : Result[]která představuje orákulum fáze pro Groverův úkol. Tato operace používá jednotkovou transformaci u obecného qubitového registru.

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

Operace GroverSearch inicializuje registr qubitů $n$ ve stavu $\ket{0}$, připraví registr do jednotné superpozice a pak použije Groverův algoritmus pro zadaný počet iterací. Samotné hledání se skládá z opakovaného vyjádření o označeném stavu a počátečním stavu, ve kterém můžete psát Q# jako smyčku for. Nakonec měří registr a vrátí výsledek.

Kód používá tři pomocné operace: PrepareUniform, ReflectAboutUniforma ReflectAboutAllOnes.

Při registraci ve stavu PrepareUniform all-zeros připraví operace jednotnou superpozici pro všechny základní stavy.

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

Operace ReflectAboutAllOnes odráží stav all-ones.

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

Operace ReflectAboutUniform odráží stav jednotné superpozice. Nejprve transformuje jednotnou superpozici na nulu. Pak transformuje stav all-zero na všechny. Nakonec se odráží o stavu všech. Operace je volána ReflectAboutUniform , protože ji lze geometricky interpretovat jako odraz ve vektorovém prostoru o jednotném stavu superpozice.

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

Spuštění konečného kódu

Teď máte všechny složky pro implementaci konkrétní instance Groverova vyhledávacího algoritmu a vyřešení problému faktoringu. K dokončení operace Main nastaví problém zadáním počtu qubitů a počtu iterací.

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

Spuštění programu

Vyberte požadovanou platformu pro spuštění programu.

Copilot v Azure Quantum

Svůj Q# kód můžete otestovat pomocí Copilotu v Azure Quantum zdarma – vše, co potřebujete, je e-mailový účet Microsoft (MSA). Další informace o copilotu v Azure Quantum najdete v tématu Prozkoumání Azure Quantum.

1. V prohlížeči otevřete Copilot v Azure Quantum.

2. Zkopírujte a vložte následující kód do editoru kódu.

   import Microsoft.Quantum.Convert.*;
   import Microsoft.Quantum.Math.*;
   import Microsoft.Quantum.Arrays.*;
   import Microsoft.Quantum.Measurement.*;
   import Microsoft.Quantum.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);
       }
   }
   

Tip

Z Copilotu ve službě Azure Quantum můžete program otevřít ve VS Code pro web výběrem tlačítka s logem VS Code v pravém rohu editoru kódu.

Spuštění programu pomocí simulátoru v paměti

1. Vyberte Simulátor v paměti.
2. Vyberte počet snímků, které chcete spustit, a vyberte Spustit.
3. Výsledky se zobrazí v histogramu a v polích Výsledky .
4. Výběrem možnosti Vysvětlit kód zobrazíte výzvu Ke zkopírování, aby vám kód vysvětlil.

Spuštění programu pomocí emulátoru Quantinuum H-Series

Program můžete odeslat také do bezplatného emulátoru Quantinuum H-Series. Emulátor simuluje kvantový počítač s 20 qubity.

1. Vyberte rozevírací seznam Simulátor v paměti a vyberte Emulátor Quantinuum H-Series.
2. Vyberte počet snímků (aktuálně omezený na 20) a vyberte Spustit.

Visual Studio Code

1. Otevřete Visual Studio Code a výběrem možnosti Soubor > nový textový soubor vytvořte nový soubor.

2. Uložte soubor jako GroversAlgorithm.qs. Tento soubor bude obsahovat Q# kód pro váš program.

3. Zkopírujte do GroversAlgorithm.qs souboru následující kód.

   
   import Microsoft.Quantum.Convert.*;
   import Microsoft.Quantum.Math.*;
   import Microsoft.Quantum.Arrays.*;
   import Microsoft.Quantum.Measurement.*;
   import Microsoft.Quantum.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);
       }
   }
   

4. Před spuštěním programu se ujistěte, že target je profil nastavený na Neomezený. Vyberte Zobrazit –> Paleta příkazů, vyhledejte QIR, vyberte Q#: Nastavte profil Azure Quantum QIR target a pak vyberte Q#: neomezený.

5. Pokud chcete program spustit, vyberte Spustit ze seznamu příkazů nad Main operací nebo stiskněte Kombinaci kláves Ctrl+F5. Ve výchozím nastavení kompilátor spustí Main operaci nebo funkci ve výchozím simulátoru.

6. Výstup se zobrazí v konzole ladění v terminálu.

Poznámka:

target Pokud profil není nastavený na Unrestricted, při spuštění programu se zobrazí chyba.

Související obsah

Prozkoumejte další Q# kurzy:

• Kvantové propletení ukazuje, jak napsat Q# program, který manipuluje s qubity a měří je a ukazuje účinky superpozice a propletení.
• Generátor kvantových náhodných čísel ukazuje, jak napsat Q# program, který generuje náhodná čísla z qubitů v superpozici.
• Quantum Fourier Transform zkoumá, jak napsat Q# program, který přímo řeší konkrétní qubity.
• Kvantové katy jsou kurzy a programovací cvičení zaměřená na výuku prvků kvantového computingu a Q# programování současně.