Tutorial: Menerapkan algoritme pencarian Grover dalam Q#

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

Di tutorial ini, Anda akan:

• Tentukan algoritma Grover untuk masalah pencarian
• Menerapkan algoritma Grover di Q#

Tip

Jika Anda ingin mempercepat perjalanan komputasi kuantum Anda, lihat Kode dengan Azure Quantum, fitur unik dari 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 Code di Web.
  • Versi terbaru ekstensi AzureQuantum Development Kit. Untuk detail penginstalan, lihat Menginstal QDK 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:

1. 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.
2. Menerapkan fungsi tugas Grover sebagai oracle kuantum. Untuk menerapkan algoritme Grover, Anda perlu menerapkan fungsi $f(x)$ tugas Grover Anda sebagai oracle kuantum.
3. 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:

1. Mulailah dengan register qubit $n$ yang diinisialisasi dalam status $\ket{0}$.
2. 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$$
3. 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.
4. Ukur register untuk mendapatkan indeks item yang merupakan solusi dengan peluang yang sangat tinggi.
5. 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 mencerminkannya, 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 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 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 nol dan yang 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, ini menerapkan gerbang $X$ yang dikontrol ke qubit tambahan dan qubit input. 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 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 menggunakan CalculateOptimalIterations rumus di atas untuk menghitung jumlah iterasi, lalu membulatkannya ke bilangan bulat terdekat.

Tentukan operasi Grover

Q# Operasi untuk algoritma pencarian Grover memiliki tiga input:

• Jumlah qubit, nQubits : Int, dalam register qubit. 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 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 mencerminkan tentang status yang ditandai dan status mulai, yang dapat Anda tulis Q# sebagai untuk perulangan. Akhirnya, ia mengukur register dan mengembalikan hasilnya.

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

Mengingat register dalam status all-zeros, PrepareUniform operasi menyiapkan superposisi seragam atas 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, mengubah status all-zero menjadi all-ones. Akhirnya, ini mencerminkan tentang status semua orang. 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 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

Pilih platform yang diinginkan untuk menjalankan program Anda.

Copilot di Azure Quantum

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

1. Buka Copilot di Azure Quantum di browser Anda.

2. Salin dan tempel kode berikut ke editor kode.

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

Tip

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

Jalankan program menggunakan simulator dalam memori

1. Pilih Simulator dalam memori.
2. Pilih jumlah bidikan yang akan dijalankan, dan pilih Jalankan.
3. Hasilnya ditampilkan dalam histogram dan di bidang Hasil .
4. Pilih 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.

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

Visual Studio Code

1. Buka Visual Studio Code dan pilih File > Teks Baru untuk membuat file baru.

2. Simpan file sebagai GroversAlgorithm.qs. File ini akan berisi Q# kode untuk program Anda.

3. Salin kode berikut ke dalam file GroversAlgorithm.qs.

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

4. Sebelum menjalankan program, pastikan target profil diatur ke Tidak Dibatasi. Pilih Tampilkan -> Palet Perintah, cari QIR, pilihQ# : Atur profil QIR target Azure Quantum, lalu pilih Q#: tidak dibatasi.

5. Untuk menjalankan program Anda, pilih Jalankan dari daftar perintah di atas Main operasi, atau tekan Ctrl+F5. Secara default, pengkompilasi menjalankan Main operasi atau fungsi pada simulator default.

6. Output Anda akan muncul di konsol debug di terminal.

Catatan

target Jika profil tidak diatur ke Tidak Dibatasi, Anda akan mendapatkan kesalahan saat menjalankan program.

Konten terkait

Jelajahi tutorial Q# lainnya:

• Entanglemen kuantum menunjukkan cara menulis Q# program yang memanipulasi dan mengukur qubit dan menunjukkan efek superposisi dan entanglemen.
• Generator 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.