Oktatóanyag: A Grover keresési algoritmusának implementálása a Q#
Megjegyzés
A Microsoft Quantum Development Kit (klasszikus QDK) 2024. június 30. után már nem támogatott. Ha Ön meglévő QDK-fejlesztő, javasoljuk, hogy váltson át az új Azure-ra Quantum Development Kit (modern QDK) a kvantummegoldások fejlesztésének folytatásához. További információ: 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 tekintse meg a Grover-algoritmus elméletét.
Ebben az oktatóanyagban a következőket fogja végezni:
- Definiálja a Grover-algoritmust egy keresési problémához.
- Implementálja a Grover-algoritmust a következőben 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# egyetlen kattintással, és kérdéseket tehet fel a Copilotnak a kvantum-számítástechnikával kapcsolatban.
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 Kit legújabb verziója. A telepítés részleteiért lásd : A modern QDK telepítése a VS Code-on.
A probléma meghatározása
A Grover-algoritmus 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 pontosabban kell gondolni rá a keresési probléma szempontjából.
Bármilyen keresési probléma matematikailag megfogalmazható egy absztrakt $f(x)$ függvénnyel, amely elfogadja a keresési elemeket $x$. Ha a $x$ elem a keresési probléma megoldása, akkor $f(x)=1$. Ha a $x$ elem nem megoldás, akkor $f(x)=0$. A keresési probléma a $x_0$ olyan elem megkereséséből áll, amely $f(x_0)=1$.
Így bármilyen keresési problémát a következőképpen fogalmazhat meg: 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őket kell végrehajtania:
- Alakítsa át a problémát Egy Grover-feladat formájába. Tegyük fel például, hogy egy $M$ egész szám tényezőit szeretné megtalálni a Grover-algoritmus használatá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$ az $M/x$ fennmaradó része. Ily módon a $f_M(x_i)=1$ értéket $x_i$ egész számok képezik $M$ tényezői, és a problémát Grover-feladattá alakította át.
- Implementálja a Grover-feladat 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.
- A feladat megoldásához használja a Grover-algoritmust 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-algoritmus
Tegyük fel, hogy $N=2^n$ jogosult elem van a keresési problémára, és a rendszer indexeli őket úgy, hogy minden egyes elemet 0$ értékről $N-1$ értékre rendel. Az algoritmus lépései a következők:
- Kezdje a $\ket{0}$ állapotban inicializált $n$ qubitek regiszterével.
- Készítse elő a regisztert egy egységes szuperpozícióba úgy, hogy $H$ értéket alkalmaz a regiszter minden qubitére: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
- Alkalmazza a következő műveleteket a regiszter $N_{\text{optimal}}$ alkalommal:
- A fázisorákulum $O_f$ , amely $-1$ feltételes fáziseltolódást alkalmaz a megoldáselemekre.
- Alkalmazza a $H$ elemet a regiszterben lévő összes qubitre.
- 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.
- Alkalmazza a $H$ elemet a regiszterben lévő összes qubitre.
- Mérje meg a regisztert egy nagyon nagy valószínűséggel megoldásnak számító elem indexének lekéréséhez.
- Ellenőrizze az elemet, hogy érvényes megoldás-e. Ha nem, kezdje újra.
A Grover-algoritmus kódjának írása a következőben: Q#
Ez a szakasz az algoritmus implementálását ismerteti a következőben Q#: . A Grover-algoritmus implementálá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 megvalósítja a Grover-feladat függvényét.
A megjelölt állapot meghatározása
Először meg kell határoznia, hogy milyen bemenetet szeretne keresni a keresésben. Ehhez írjon egy műveletet, amely a Grover-algoritmusb, c és d lépéseit alkalmazza.
Ezek a lépések együttesen a Grover-eloszlási 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 értékekkel 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, outputQubit
amely $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ állapotban van inicializálva 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 megfordítja a qubit állapotát. Végül a szabályozott $X$ kaput alkalmazza a kiegészítő qubitekre és a bemeneti qubitekre. Ez a művelet csak akkor és csak akkor váltja fel 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ér egy érvényes kimenetet. Ha a probléma $N=2^n$ lehetséges jogosult elemekkel 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 optimális iterációk számán túli iterációk tovább haladva elkezdik csökkenteni ezt a valószínűséget, amíg el nem éri a $2 N_{\text{optimal}}$ iteráció sikerességének közel nulla valószínűségét. Ezt követően a valószínűség újra nő, amíg a $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 kezelésére hatékony stratégia a megoldások számának "kitalálása" $M$ a becslés fokozatos növelésével két hatványban (pl. $1, 2, 4, 8, 16, ..., 2^n$). Ezen találgatások egyike elég közel lesz ahhoz, hogy az algoritmus továbbra is megtalálja a megoldást a $\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 regiszter adott számú qubitjéhez.
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 meghatározása
A Q# Grover keresési algoritmusának művelete három bemenettel rendelkezik:
- A qubitek száma a
nQubits : Int
qubit-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 általános qubitregisztrációs regiszterre alkalmaz egy egységes átalakítást.
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 regiszterét, előkészíti a regisztert egy egységes szuperpozícióba, majd alkalmazza a Grover-algoritmust 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 regisztert, és visszaadja az eredményt.
A kód három segédműveletet használ: PrepareUniform
, ReflectAboutUniform
és ReflectAboutAllOnes
.
Mivel a regiszter az all-zeros állapotban van, a PrepareUniform
művelet egy 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 all-ones állapotúvá. Végül az összes állapotot tükrözi. A művelet azért van meghívva ReflectAboutUniform
, 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égső kód futtatása
Most már minden összetevővel 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
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.
Nyissa meg a Copilot az Azure Quantum-ban a böngészőben.
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
- Válassza a Memórián belüli szimulátor lehetőséget.
- Jelölje ki a futtatandó felvételek számát, majd kattintson a Futtatás gombra.
- Az eredmények a hisztogramban és az Eredmények mezőkben jelennek meg.
- 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.
- Válassza a Memóriaszimulátor legördülő menüt, és válassza a Quantinuum H-Series Emulator lehetőséget.
- 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.
Visszajelzés
https://aka.ms/ContentUserFeedback.
Hamarosan elérhető: 2024-ben fokozatosan kivezetjük a GitHub-problémákat a tartalom visszajelzési mechanizmusaként, és lecseréljük egy új visszajelzési rendszerre. További információ:Visszajelzés küldése és megtekintése a következőhöz: