Tutorial: Menerapkan algoritme pencarian Grover dalam Q#

Artikel
04/17/2024

Catatan

Microsoft Quantum Development Kit (QDK Klasik) tidak akan lagi didukung setelah 30 Juni 2024. Jika Anda adalah pengembang QDK yang sudah ada, kami sarankan Anda beralih ke Azure Quantum Development Kit baru (Modern QDK) untuk terus mengembangkan solusi kuantum. Untuk informasi selengkapnya, lihat Memigrasikan kode Anda Q# ke QDK Modern.

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

Dialam tutorial ini, Anda akan:

Tentukan algoritma Grover untuk masalah pencarian.
Terapkan algoritma Grover di Q#.

Tip

Jika Anda ingin mempercepat perjalanan komputasi kuantum Anda, lihat Kode dengan Azure Quantum, fitur unik situs web Azure Quantum. Di sini, Anda dapat menjalankan sampel bawaan Q# atau program Anda sendiri Q# , menghasilkan kode baru Q# dari perintah Anda, membuka dan menjalankan kode Anda di Visual Studio Code untuk Web dengan satu klik, dan mengajukan pertanyaan apa pun tentang komputasi kuantum.

Prasyarat

Untuk menjalankan sampel kode di Copilot di Azure Quantum:
- Akun email Microsoft (MSA).
Untuk mengembangkan dan menjalankan sampel kode di Visual Studio Code:
- Versi terbaru Visual Studio Code atau buka Visual Studio Code di Web.
- Versi terbaru ekstensi Azure Quantum Development Kit . Untuk detail penginstalan, lihat Menginstal QDK Modern di Visual Studio Code.

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)$ 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$ yang menerapkan pergeseran fase kondisional $-1$ untuk item solusi.
2. Terapkan $H$ ke setiap qubit dalam register.
3. Terapkan $-O_0$, pergeseran fase kondisional $-1$ ke setiap status dasar komputasi kecuali $\ket{0}$.
4. Terapkan $H$ ke 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 menentukan status yang ditandai, cara merefleksikannya, dan berapa banyak iterasi untuk menjalankan algoritma. Anda juga perlu menentukan oracle yang mengimplementasikan fungsi tugas Grover.

Tentukan status yang ditandai

Pertama, Anda menentukan input apa yang ingin 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 diffusion 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 tentang status dasar yang ditandai dengan bergantian nol dan yang bergantian. Hal ini dilakukan dengan menerapkan operator diffusion Grover ke qubit input. Operasi ini menggunakan kubit tambahan, , outputQubityang 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 membalik status qubit. Akhirnya, ini menerapkan gerbang $X$ yang dikontrol ke kubit tambahan dan qubit input. Operasi ini membalik 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 optimal mulai mengurangi probabilitas tersebut sampai Anda mencapai probabilitas keberhasilan hampir-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 ini CalculateOptimalIterations menggunakan rumus di atas untuk menghitung jumlah perulangan, lalu membulatkannya ke bilangan bulat terdekat.

Menentukan operasi Grover

Q# Operasi untuk algoritma pencarian Grover memiliki tiga input:

Jumlah qubit, nQubits : Int, dalam qubit register. Register ini akan menyandikan solusi tentatif untuk masalah pencarian. Setelah operasi, operasi akan diukur.
Jumlah iterasi optimal, iterations : Int.
Operasi, phaseOracle : Qubit[] => Unit) : Result[], yang mewakili fase oracle untuk tugas Grover. Operasi ini menerapkan transformasi kesatuan 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 $n$ qubits di negara bagian $\ket{0}$, menyiapkan register ke dalam superposisi seragam, dan kemudian menerapkan algoritma Grover untuk jumlah iterasi yang ditentukan. Pencarian itu sendiri terdiri dari berulang kali mencerminkan tentang status yang ditandai dan status mulai, yang dapat Anda tulis sebagai Q# untuk perulangan. Akhirnya, ia mengukur register dan mengembalikan hasilnya.

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

Mengingat register dalam status all-zeros, PrepareUniform operasi menyiapkan superposisi seragam di semua status dasar.

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

Operasi ''ReflectAboutAllOnes' mencerminkan tentang status 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, ini mengubah status all-zero menjadi all-ones. Akhirnya, itu mencerminkan tentang status 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 menyelesaikannya Main , operasi menyiapkan masalah dengan menentukan jumlah kubit dan jumlah perulangan

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

Anda dapat menguji kode Anda Q# dengan Copilot di Azure Quantum secara gratis - yang Anda butuhkan hanyalah akun email Microsoft (MSA). Untuk informasi selengkapnya tentang Copilot di Azure Quantum, lihat Menjelajahi Azure Quantum.

Buka Copilot di Azure Quantum di browser Anda.

Salin dan tempel kode berikut ke editor kode.

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

Tip

Dari Copilot di Azure Quantum, Anda dapat membuka program Di Visual Studio Code untuk Web dengan mengklik tombol logo Visual Studio Code di sudut kanan editor kode.

Jalankan program menggunakan simulator dalam memori

Pilih Simulator dalam memori.
Pilih jumlah bidikan yang akan dijalankan, dan klik Jalankan.
Hasilnya ditampilkan dalam histogram dan di bidang Hasil .
Klik Jelaskan kode untuk meminta Copilot untuk menjelaskan kode kepada Anda.

Jalankan program menggunakan Emulator Quantinuum H-Series

Anda juga dapat mengirimkan program Anda ke Emulator Quantinuum H-Series gratis. Emulator mensimulasikan komputer kuantum dengan 20 qubit.

Pilih menu dropdown Simulator Dalam Memori dan pilih Emulator Quantinuum H-Series.
Pilih jumlah bidikan (saat ini dibatasi hingga 20) dan pilih Jalankan.

Buka Visual Studio Code dan pilih File > Teks Baru untuk membuat file baru.
Simpan file sebagai GroversAlgorithm.qs. File ini akan berisi Q# kode untuk program Anda.

Salin kode berikut dalam GroversAlgorithm.qs file.

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

Sebelum menjalankan program, Anda perlu mengatur profil ke targetTidak Dibatasi. Pilih Lihat -> Palet Perintah, cari QIR, pilih Q#: Atur profil QIR target Azure Quantum, lalu pilih Q#: tidak dibatasi.
Untuk menjalankan program Anda, pilih Jalankan Q# File dari menu drop-down ikon putar di kanan atas, atau tekan Ctrl+F5. Program menjalankan operasi atau fungsi yang ditandai dengan @EntryPoint() atribut pada simulator default.
Output Anda akan muncul di konsol debug.