Oktatóanyag: A Grover keresési algoritmusának implementálása Q#

Ebben az oktatóanyagban Q# a Grover algoritmusát implementálja a keresésalapú problémák megoldásához. A Grover-algoritmus mögötti elmélet részletes magyarázatát lásd a Grover-algoritmus elméletében.

Az oktatóanyag során az alábbi lépéseket fogja végrehajtani:

Előfeltételek

• A kódminta futtatása a Copilotban az Azure Quantumban:

  • Egy Microsoft (MSA) e-mail-fiók.

• A kódminta fejlesztése és futtatása a Visual Studio Code-ban:

  • A Visual Studio Code legújabb verziója, vagy nyissa meg a VS Code-ot a weben.
  • Az Azure-bővítmény Quantum Development Kitlegújabb verziója. A telepítés részleteiért lásd: QDK-bővítmény beállítása.

A probléma meghatározása

Grover algoritmusa a kvantum-számítástechnika egyik leghíresebb algoritmusa. A megoldandó probléma típusát gyakran "adatbázis-keresésnek" is nevezik, de pontosabb a keresési probléma szempontjából.

Bármilyen keresési probléma matematikailag fogalmazható meg egy absztrakt $f(x)$ függvénysel, amely elfogadja a keresési elemeket $x$. Ha az elem $x$ megoldás a keresési problémára, akkor $f(x)=1$. Ha az elem $x$ nem megoldás, akkor $f(x)=0$. A keresési probléma az olyan elemek $x_0$ kereséséből áll, amelyek $f(x_0)=1$.

Így bármilyen keresési problémát úgy fogalmazhat meg, mint: egy klasszikus $f(x):\{0,1\}^n \rightarrow\{0,1\}$, ahol $n$ a keresési terület bitmérete, keressen egy bemeneti $x_0$ értéket, amelyhez $f(x_0)=1$.

A Grover algoritmusának a keresési problémák megoldásához a következőkre van szükség:

1. Alakítsa át a problémát Egy Grover-feladat formájára. Tegyük fel például, hogy egy $M$ egész szám tényezőit szeretné megtalálni a Grover algoritmusával. Az egész szám faktorizációs problémáját groveri feladattá alakíthatja úgy, hogy létrehoz egy $$f_M(x)=1[r],$$ függvényt, ahol $1[r]=1$ ha $r=0$ és $1[r]=0$ ha $r\neq0$ és $r$ a $M/x$ fennmaradó része. Ily módon a $f_M(x_i)=1$ értékre $x_i$ egész számok a $M$ tényezői, és a problémát Grover-feladattá alakította át.
2. Implementálja a Grover feladatának függvényét kvantumorákulumként. A Grover-algoritmus implementálásához kvantumorákulumként kell implementálnia a Grover-feladat $f(x)$ függvényét.
3. A feladat megoldásához használja a Grover algoritmusát az orákulumával. Ha már rendelkezik kvantumorákulumsal, csatlakoztathatja a Grover-algoritmus implementációjához a probléma megoldásához és a kimenet értelmezéséhez.

A Grover algoritmusa

Tegyük fel, hogy a keresési problémához $N=2^n$ jogosult elem tartozik, és a rendszer indexeli őket úgy, hogy az egyes elemeket 0$ értékről $N-1$ egész számra rendeli. Az algoritmus lépései a következők:

1. Kezdje a $\ket{0}$ állapotban inicializált $n$ qubitek nyilvántartásával.
2. Készítse elő a regisztert egy egységes szuperpozícióba, ha $H$ értéket alkalmaz a regiszter minden qubitére: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
3. Alkalmazza a következő műveleteket a $N_{\text{optimal}}$ regiszterre:
   1. A fázis oracle $O_f$, amely a megoldáselemekhez $-1$ feltételes fáziseltolást alkalmaz.
   2. Alkalmazza a $H$ elemet a regiszterben lévő összes qubitre.
   3. Alkalmazza a $-O_0$, egy $-1$ feltételes fázisváltást minden számítási alapállapotra a $\ket{0}$ kivételével.
   4. Alkalmazza a $H$ elemet a regiszterben lévő összes qubitre.
4. Mérje meg a regisztert egy nagyon nagy valószínűségű megoldásnak számító elem indexének lekéréséhez.
5. Ellenőrizze az elemet, hogy érvényes megoldás-e. Ha nem, kezdje újra.

A Grover-algoritmus kódjának írása Q#

Ez a szakasz azt ismerteti, hogyan implementálhatja az algoritmust a következőben Q#: . A Grover-algoritmus implementálásakor néhány dolgot érdemes figyelembe venni. Meg kell határoznia, hogy mi a megjelölt állapot, hogyan tükrözze azt, és hány iterációt kell futtatnia az algoritmushoz. Meg kell határoznia azt az orákulumot is, amely megvalósítja a Grover feladatának funkcióját.

A megjelölt állapot meghatározása

Először határozza meg, hogy milyen bemenetet szeretne keresni a keresésben. Ehhez írjon egy műveletet, amely a Grover-algoritmus b, c és d lépéseit alkalmazza.

Ezek a lépések együttesen a Grover's diffúziós operátorként is ismertek: $-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);
    }
}

A ReflectAboutMarked művelet a váltakozó nullákkal és váltó nullákkal jelölt alapállapotra utal. Ehhez alkalmazza a Grover diffúziós operátorát a bemeneti qubitekre. A művelet egy kiegészítő qubitet használ, outputQubitamely $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ állapotban inicializálódik a $X$ és $H$ kapuk alkalmazásával. A művelet ezután alkalmazza a $X$ kaput a regiszterben lévő összes többi qubitre, ami megfordítja a qubit állapotát. Végül alkalmazza a szabályozott $X$ kaput a kiegészítő qubitekre és a bemeneti qubitekre. Ez a művelet megfordítja a kiegészítő qubitet, ha és csak akkor, ha az összes bemeneti qubit $\ket{1}$ állapotban van, amely a megjelölt állapot.

Az optimális iterációk számának meghatározása

A Grover-keresés optimális számú iterációval rendelkezik, amelyek a legnagyobb valószínűséggel mérik az érvényes kimenetet. Ha a probléma $N=2^n$ lehetséges jogosult elemekkel rendelkezik, és ezek közül $M$ megoldás a problémára, az iterációk optimális száma a következő:

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

Az iterációk optimális számának túllépése elkezdi csökkenteni ezt a valószínűséget, amíg el nem éri a 2$ N_{\text{optimal}}$ iteráció majdnem nulla sikerességi valószínűségét. Ezt követően a valószínűség ismét növekszik, amíg $3 N_{\text{optimal}}$, és így tovább.

A gyakorlati alkalmazásokban általában nem tudhatja, hány megoldása van a problémának, mielőtt megoldaná. A probléma megoldásának hatékony stratégiája a megoldások számának "kitalálása" $M$ azáltal, hogy fokozatosan növeli a két főre (például $1, 2, 4, 8, 16, ..., 2^n$). Az alábbi találgatások egyike elég közel lesz ahhoz, hogy az algoritmus továbbra is megtalálja a megoldást az $\sqrt{\frac{N}{M}}$ körüli iterációk átlagos számával.

Az alábbi Q# függvény kiszámítja az iterációk optimális számát egy adott számú qubithez egy regiszterben.

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

A CalculateOptimalIterations függvény a fenti képletet használja az iterációk számának kiszámításához, majd a legközelebbi egész számra kerekíti.

A Grover műveletének meghatározása

A Q# Grover keresési algoritmusának művelete három bemenettel rendelkezik:

• A qubitek száma a nQubits : Intqubit-regiszterben. Ez a regiszter kódolja a feltételes megoldást a keresési problémára. A művelet után a rendszer megméri.
• Az optimális iterációk száma, iterations : Int.
• Egy művelet, phaseOracle : Qubit[] => Unit) : Result[]amely a Grover-feladat fázisorákulumát jelöli. Ez a művelet egységes átalakítást alkalmaz egy általános qubitregisztráción keresztül.

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

A GroverSearch művelet inicializálja a $\ket{0}$ állapotú $n$ qubitek nyilvántartását, előkészíti a regisztert egy egységes szuperpozícióba, majd alkalmazza a Grover algoritmusát a megadott számú iterációra. Maga a keresés a megjelölt állapot és a kezdő állapot ismételt tükrözéséből áll, amelyet ciklusként írhat be Q# . Végül méri a nyilvántartást, és visszaadja az eredményt.

A kód három segédműveletet használ: PrepareUniform, ReflectAboutUniformés ReflectAboutAllOnes.

Mivel a regiszter az összes nullás állapotban van, a PrepareUniform művelet egységes szuperpozíciót készít elő az összes alapállapotra vonatkozóan.

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

A "ReflectAboutAllOnes" művelet az összes állapotot tükrözi.

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

A művelet ReflectAboutUniform az egységes szuperpozíciós állapotot tükrözi. Először is, átalakítja az egységes szuperpozíciót minden nullára. Ezután átalakítja a teljes nulla állapotot mindenre. Végül az összes állapotot tükrözi. A művelet azért hívható ReflectAboutUniform meg, mert geometriailag értelmezhető az egységes szuperpozíciós állapot vektortérbeli tükröződéseként.

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

A végleges kód futtatása

Most már minden hozzávalóval rendelkezik a Grover keresési algoritmusának egy adott példányának implementálásához és a faktorálási probléma megoldásához. A művelet a Main qubitek számának és az iterációk számának megadásával állítja be a problémát.

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

A program futtatása

Válassza ki a kívánt platformot a program futtatásához.

Kapcsolódó tartalom

További Q# oktatóanyagok:

• A kvantum-összefonódás bemutatja, hogyan írhat olyan Q# programot, amely manipulálja és méri a qubiteket, és bemutatja a szuperpozíció és az összefonódás hatásait.
• A kvantum véletlenszerű számgenerátor bemutatja, hogyan írhat olyan Q# programot, amely véletlenszerű számokat hoz létre qubitből szuperpozícióban.
• A Quantum Fourier Transform azt vizsgálja, hogyan írhat olyan Q# programot, amely közvetlenül kezeli az adott qubiteket.
• A Quantum Katas öngyors oktatóanyagok és programozási gyakorlatok, amelyek célja a kvantum-számítástechnika és Q# a programozás elemeinek egyidejű tanítása.