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

  • Cikk

Megjegyzés

A Microsoft Quantum Development Kit (klasszikus QDK) 2024. június 30. után már nem támogatott. Ha Ön már QDK-fejlesztő, javasoljuk, hogy váltson az új Azure-ra Quantum Development Kit (Modern QDK) a kvantummegoldások fejlesztésének folytatásához. További információ: A kód migrálása Q# a modern QDK-ba.

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áért lásd a Grover-algoritmus elméletét.

Ebben az oktatóanyagban a következőket fogja használni:

  • Definiálja a Grover algoritmusát egy keresési problémához.
  • Implementálja a Grover algoritmusát a alkalmazásban Q#.

Tipp

Ha fel szeretné gyorsítani a kvantum-számítástechnika folyamatát, tekintse meg a Code with Azure Quantum (Kód az Azure Quantum használatával) című témakört, amely az Azure Quantum webhelyének egyedülálló funkciója. Itt futtathat beépített mintákat vagy saját Q# programokat, új Q# kódot hozhat létre az üzeneteiből, megnyithatja és futtathatja a kódot a WEBES VS Code-banQ# egy kattintással, és kérdéseket tehet fel a Copilotnak a kvantum-számítástechnikával kapcsolatban.

Előfeltételek

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ármely 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 a $x$ elem 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éma megoldásához a következőket kell elvégeznie:

  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 egy $$f_M(x)=1[r],$$ függvény létrehozásával alakíthatja át groveri feladattá, ahol $1[r]=1$ ha $r=0$ és $1[r]=0$ ha $r\neq0$ és $r$ az $M/x$ fennmaradó része. Ily módon a $f_M(x_i)=1$ értéket $x_i$ egész számokkal $M$ tényezővé alakítva, és a problémát groveri feladattá alakította át.
  2. Implementálja a Grover feladatának függvényét kvantumorákulumként. A Grover algoritmusának 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ákulummal. Ha már rendelkezik kvantumorákulumtal, 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 vannak $N=2^n$ jogosult elemek a keresési problémára, és indexelhetők úgy, hogy minden egyes elemet 0$ és $N-1$ közötti egész számként rendelnek hozzá. Az algoritmus lépései a következők:

  1. Kezdje a $\ket{0}$ állapotban inicializált $n$ qubitek regiszterével.
  2. Készítse elő a regisztrációt egy egységes szuperpozícióba úgy, hogy $H$ értéket alkalmaz a regiszterben lévő összes qubitre: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
  3. Alkalmazza a következő műveleteket a regisztrációs $N_{\text{optimal}}$ időpontokra:
    1. A fázis oracle $O_f$ , amely a megoldáselemekhez $-1$ feltételes fáziseltolást alkalmaz.
    2. Alkalmazza $H$ értéket a regiszterben lévő összes qubitre.
    3. Alkalmazza a $-O_0$-t, amely egy $-1$ feltételes fáziseltolás minden számítási alapállapotra, kivéve a $\ket{0}$ értéket.
    4. Alkalmazza $H$ értéket 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-e a megoldás. Ha nem, kezdje újra.

Írja be a Grover-algoritmus kódját a következőbe: Q#

Ez a szakasz az algoritmus implementálását ismerteti a következőben Q#: . A Grover algoritmusának megvalósításakor néhány szempontot figyelembe kell 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 algoritmus futtatásához. Meg kell határoznia azt az orákulumot is, amely a Grover feladatának függvényét valósítja meg.

A megjelölt állapot meghatározása

Először meg kell adnia, hogy milyen bemenetet szeretne keresni a keresésben. Ehhez írjon be egy műveletet, amely a Grover-algoritmusb, c és d lépéseit alkalmazza.

Ezek a lépések együttesen a Grover diffúziós operátoraké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ák és azok által megjelö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 a $X$ kaput alkalmazza a regiszterben lévő összes többi qubitre, amely a qubit állapotát tükrözi. Végül a szabályozott $X$ kaput alkalmazza a kiegészítő qubitekre és a bemeneti qubitekre. Ez a művelet akkor és csak akkor váltja ki a kiegészítő qubitet, 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, amely a legnagyobb valószínűséggel méri az érvényes kimenetet. Ha a probléma $N=2^n$ lehetséges jogosult tételekkel rendelkezik, és $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 mindaddig csökkenti ezt a valószínűséget, amíg el nem éri a 2$ N_{\text{optimal}}$ iteráció közel nulla sikerességi valószínűségét. Ezt követően a valószínűség újra nő, 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, hogy "kitalálja" a megoldások számát $M$ azáltal, hogy fokozatosan növeli a két hatványú becslést (pl. $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 átlagosan $\sqrt{\frac{N}{M}}$ körüli iterációkkal.

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 regisztráció 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 egy 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 megméri a nyilvántartást, és visszaadja az eredményt.

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

A minden nullás állapotban lévő regiszter alapján 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 az all-zero állapotot minden-egyre. Végül az összes állapotot tükrözi. A műveletet azért hívjuk 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 összetevővel rendelkezik, hogy implementálja a Grover keresési algoritmusának egy adott példányát, és megoldja a faktorálási problémát. 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

A Q# kódot ingyenesen tesztelheti a Copilottal az Azure Quantum-ban – mindössze egy Microsoft(MSA) e-mail-fiókra van szüksége. További információ az Azure Quantum Copilotjáról: Az Azure Quantum felfedezése.

  1. Nyissa meg a Copilot az Azure Quantum-ban a böngészőben.

  2. Másolja és illessze be a következő kódot a kódszerkesztőbe.

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

Tipp

Az Azure Quantum-ban a Copilotban megnyithatja a programot a VS Code for the Web alkalmazásban a kódszerkesztő jobb sarkában található VS Code embléma gombra kattintva.

A program futtatása a memórián belüli szimulátor használatával

  1. Válassza a Memórián belüli szimulátor lehetőséget.
  2. Jelölje ki a futtatandó felvételek számát, majd kattintson a Futtatás gombra.
  3. Az eredmények a hisztogramban és az Eredmények mezőkben jelennek meg.
  4. A Kód magyarázata gombra kattintva kérje meg a Copilototot, hogy magyarázza el Önnek a kódot.

Futtassa a programot a Quantinuum H-Series Emulator használatával

A programot az ingyenes Quantinuum H-Series Emulatorba is elküldheti. Az emulátor 20 qubittel szimulál egy kvantumszámítógépet.

  1. Válassza a Memóriaszimulátor legördülő menüt, és válassza a Quantinuum H-Series Emulator lehetőséget.
  2. Válassza ki a felvételek számát (jelenleg 20-ra korlátozott), és válassza a Futtatás lehetőséget.

Következő lépések

Ismerkedjen meg más Q# oktatóanyagokkal:

  • A kvantum-összefonódás bemutatja, hogyan írhat olyan Q# programot, amely a qubiteket manipulálja és méri, é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.