Tutorial: Menerapkan algoritme pencarian Grover dalam Q#

Dalam tutorial ini, Anda mengimplementasikan algoritma Grover di Q# untuk menyelesaikan masalah berbasis pencarian. Untuk penjelasan mendalam tentang teori dibalik algoritme Grover, lihat Algoritme teori Grover.

Di tutorial ini, Anda akan:

Menentukan algoritma Grover untuk masalah pencarian
Menerapkan algoritma Grover di Q#

Prasyarat

Untuk mengembangkan dan menjalankan sampel kode di Visual Studio Code (VISUAL Code), Anda perlu menginstal alat berikut:

Versi terbaru dari VS Code, atau buka VS Code for the Web.
Versi terbaru dari ekstensi Microsoft Quantum Development Kit(QDK). Untuk detail penginstalan, lihat Menyiapkan QDK.

Tentukan masalah

Algoritme Grover adalah salah satu algoritme paling terkenal dalam komputasi kuantum. Jenis masalah yang dipecahkan sering disebut sebagai "mencari database", tetapi lebih akurat untuk memikirkannya dalam hal masalah pencarian.

Setiap masalah pencarian dapat dirumuskan secara matematis dengan fungsi abstrak $f(x)$ yang menerima item pencarian $x$. Jika item $x$ menjadi solusi untuk masalah pencarian, maka $f(x)=1$. Jika item $x$ bukan solusinya, maka $f(x)=0$. Masalah pencarian terdiri dari menemukan item $x_0$ apa pun, sehingga $f(x_0)=1$.

Dengan demikian, Anda dapat merumuskan masalah pencarian apa pun sebagai: mengingat fungsi klasik $f(x):\{0,1\}^n \rightarrow\{0,1\}$, di mana $n$ adalah ukuran bit ruang pencarian, temukan input $x_0$ yang $f(x_0)=1$.

Untuk mengimplementasikan algoritma Grover untuk menyelesaikan masalah pencarian, Anda perlu:

Ubah masalah menjadi bentuk tugas Grover. Misalnya, Anda ingin menemukan faktor-faktor bilangan bulat $M$ menggunakan algoritme Grover. Anda dapat mengubah masalah faktorisasi bilangan bulat menjadi tugas Grover dengan membuat fungsi $$f_M(x)=1[r],$$ di mana $1[r]=1$ jika $r=0$ dan $1[r]=0$ jika $r\neq0$ dan $r$ adalah sisa dari $M/x$. Dengan cara ini, bilangan bulat $x_i$ yang membuat $f_M(x_i)=1$ adalah faktor $M$ dan Anda telah mengubah masalah menjadi tugas Grover.
Menerapkan fungsi tugas Grover sebagai oracle kuantum. Untuk menerapkan algoritme Grover, Anda perlu menerapkan fungsi $f(x)$ dari tugas Grover Anda sebagai oracle kuantum.
Gunakan algoritme Grover dengan oracle Anda untuk menyelesaikan tugas. Setelah Anda memiliki oracle kuantum, Anda dapat menyambungkannya ke implementasi algoritme Grover Anda untuk memecahkan masalah dan menafsirkan output.

Algoritma Grover

Misalkan ada item $N=2^n$ yang memenuhi syarat untuk masalah pencarian dan telah diindeks dengan menetapkan setiap item bilangan bulat dari $0$ ke $N-1$. Langkah-langkah algoritme adalah:

Mulailah dengan register qubit $n$ yang diinisialisasi dalam status $\ket{0}$.
Siapkan register menjadi superposisi seragam dengan menerapkan $H$ ke setiap qubit dalam register: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
Terapkan operasi berikut ke register $N_{\text{optimal}}$ kali:
1. Oracle fase $O_f$ menerapkan pergeseran fase bersyarat sebesar $-1$ pada item-item solusi.
2. Terapkan $H$ pada setiap qubit dalam register.
3. Terapkan $-O_0$, pergeseran fase kondisional $-1$ ke setiap status dasar komputasi kecuali $\ket{0}$.
4. Terapkan $H$ pada setiap qubit dalam register.
Ukur register untuk mendapatkan indeks item yang merupakan solusi dengan peluang yang sangat tinggi.
Periksa item untuk melihat apakah itu solusi yang valid. Jika tidak, mulailah lagi.

Tulis kode untuk algoritma Grover di Q#

Bagian ini membahas cara menerapkan algoritme dalam Q#. Ada beberapa hal yang perlu dipertimbangkan saat menerapkan algoritma Grover. Anda perlu mendefinisikan apa status yang ditandai, bagaimana memikirkannya, dan berapa banyak iterasi yang dijalankan algoritma. Anda juga perlu menentukan oracle yang mengimplementasikan fungsi algoritme Grover.

Tentukan status yang ditandai

Pertama, Anda menentukan input apa yang coba Anda temukan dalam pencarian. Untuk melakukannya, tulis operasi yang menerapkan langkah b, c dan d dari algoritma Grover.

Bersama-sama, langkah-langkah ini juga dikenal sebagai Operator Difusi Grover $-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);
    }
}

Operasi ini ReflectAboutMarked mencerminkan terhadap keadaan dasar yang ditandai dengan pola nol dan satu bergantian. Hal ini dilakukan dengan menerapkan operator diffusion Grover ke qubit input. Operasi ini menggunakan kubit tambahan, outputQubit, yang diinisialisasi dalam status $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ dengan menerapkan gerbang $X$ dan $H$. Operasi kemudian menerapkan gerbang $X$ ke setiap qubit lain dalam register, yang membalikkan status qubit. Terakhir, sistem ini menerapkan gerbang $X$ yang terkontrol ke qubit tambahan dan qubit masukan. Operasi ini membalikkan kubit tambahan jika dan hanya jika semua qubit input berada dalam status $\ket{1}$, yang merupakan status ditandai.

Menentukan jumlah iterasi optimal

Pencarian Grover memiliki jumlah iterasi optimal yang menghasilkan peluang tertinggi untuk mengukur output yang valid. Jika masalahnya memiliki $N=2^n$ kemungkinan item yang memenuhi syarat, dan $M$ merupakan solusi untuk masalah ini, jumlah iterasi yang optimal ialah:

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

Terus melakukan iterasi melewati jumlah perulangan yang optimal mulai mengurangi probabilitas tersebut hingga Anda mencapai probabilitas keberhasilan yang hampir mencapai nol pada iterasi $2 N_{\text{optimal}}$. Setelah itu, probabilitas tumbuh lagi sampai $3 N_{\text{optimal}}$, dan seterusnya.

Dalam aplikasi praktis, Anda biasanya tidak tahu berapa banyak solusi yang dimiliki masalah Anda sebelum Anda menyelesaikannya. Strategi yang efisien untuk menangani masalah ini adalah dengan "menebak" jumlah solusi $M$ dengan secara progresif meningkatkan tebakan dalam kekuatan dua (yaitu $1, 2, 4, 8, 16, ..., 2^n$). Salah satu tebakan ini akan cukup dekat sehingga algoritme masih akan menemukan solusi dengan jumlah rata-rata iterasi sekitar $\sqrt{\frac{N}{M}}$.

Fungsi berikut Q# menghitung jumlah iterasi optimal untuk sejumlah kubit tertentu dalam register.

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

Fungsi CalculateOptimalIterations menggunakan rumus yang diperlihatkan sebelumnya untuk menghitung jumlah perulangan, lalu membulatkannya ke bilangan bulat terdekat.

Definisikan operasi Grover

Q# Operasi untuk algoritma pencarian Grover memiliki tiga input:

Jumlah qubit, nQubits : Int, dalam register qubit. Register ini mengodekan solusi tentatif untuk masalah pencarian, dan diukur setelah operasi.
Jumlah iterasi optimal, iterations : Int.
Operasi, phaseOracle : Qubit[] => Unit) : Result[], yang mewakili orakel fase dalam algoritma Grover. Operasi ini menerapkan transformasi uniter melalui register qubit generik.

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

Operasi ini GroverSearch menginisialisasi daftar kubit $n$ dalam status $\ket{0}$, menyiapkan register ke dalam superposisi seragam, lalu menerapkan algoritma Grover untuk jumlah iterasi yang ditentukan. Pencarian itu sendiri terdiri dari berulang kali merefleksikan tentang status yang ditandai dan status mulai, yang dapat Anda tulis Q# sebagai perulangan for. Akhirnya, ia mengukur register dan mengembalikan hasilnya.

Kode menggunakan tiga operasi pembantu: PrepareUniform, , ReflectAboutUniformdan ReflectAboutAllOnes.

Mengingat register dalam keadaan semua-nol, operasi PrepareUniform menyiapkan superposisi seragam di seluruh keadaan dasar.

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

Operasi ReflectAboutAllOnes mencerminkan keadaan all-ones.

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

Operasi ReflectAboutUniform ini mencerminkan tentang status superposisi seragam. Pertama, mengubah superposisi seragam menjadi all-zero. Kemudian, mengubah status all-zero menjadi all-ones. Akhirnya, ini mencerminkan keadaan semua-satu. Operasi ini disebut ReflectAboutUniform karena dapat ditafsirkan secara geometris sebagai refleksi dalam ruang vektor tentang status superposisi seragam.

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

Jalankan kode terakhir

Sekarang Anda memiliki semua bahan untuk menerapkan contoh tertentu dari algoritme pencarian Grover dan memecahkan masalah pemfaktoran. Untuk menyelesaikan, operasi Main menyiapkan masalah dengan menentukan jumlah qubit dan jumlah iterasi

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

Jalankan program

Di Visual Studio Code, buka menu File dan pilih File Teks Baru untuk membuat file baru.
Simpan file sebagai GroversAlgorithm.qs. File ini berisi kode Q# untuk program Anda.

Salin kode berikut ke dalam file GroversAlgorithm.qs.


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

Untuk menjalankan program Anda, pilih Jalankan dari menu untuk Main operasi, atau tekan Ctrl + F5. Secara default, pengkompilasi menjalankan Main operasi atau fungsi pada simulator default.
Output Anda ditampilkan di konsol debug di terminal.

Catatan

Jika profil QIR target tidak diatur ke Tidak Dibatasi, maka Anda mendapatkan kesalahan saat menjalankan program. Untuk program ini, pengkompilasi secara otomatis mengatur target profil ke Tidak Dibatasi kecuali Anda mengatur profil sendiri.

Jelajahi tutorial Q# lainnya:

Keterikatan kuantum menunjukkan cara menulis Q# program yang memanipulasi dan mengukur qubit serta menunjukkan efek superposisi dan keterikatan.
Penghasil angka acak kuantum menunjukkan cara menulis Q# program yang menghasilkan angka acak dari qubit dalam superposisi.
Quantum Fourier Transform mengeksplorasi cara menulis Q# program yang secara langsung membahas qubit tertentu.
Quantum Katas adalah tutorial dan latihan pemrograman mandiri yang bertujuan untuk mengajarkan elemen komputasi dan Q# pemrograman kuantum secara bersamaan.

Saran dan Komentar

Apakah halaman ini membantu?

Last updated on 2026-05-20