Öğretici: içinde Grover arama algoritmasını uygulama Q#

2025-04-02

Bu öğreticide, arama tabanlı sorunları çözmek için Grover Q# algoritması uygulayacaksınız. Grover algoritmasının arkasındaki teorinin derinlemesine açıklaması için grover algoritması teorisine bakın.

Bu öğreticide şunları yaptınız:

Bir arama sorunu için Grover algoritmasını tanımlama
uygulamasında Grover algoritmasını uygulama Q#

İpucu

Kuantum bilişim yolculuğunuzu hızlandırmak istiyorsanız Azure Quantum web sitesinin benzersiz bir özelliği olan Azure Quantum ile kod bölümüne bakın. Burada yerleşik Q# örnekleri veya kendi Q# programlarınızı çalıştırabilir, istemlerinizden yeni Q# kod oluşturabilir, kodunuzu tek tıklamayla Web için VS Code'da açıp çalıştırabilir ve Copilot'a kuantum bilişimi hakkında sorular sorabilirsiniz.

Önkoşullar

Kod örneğini Azure Quantum'daki Copilot'ta çalıştırmak için:
- Microsoft (MSA) e-posta hesabı.
Visual Studio Code'da kod örneğini geliştirmek ve çalıştırmak için:
- Visual Studio Code'un en son sürümü veya Web'de VS Code'u açın.
- Azure Quantum Development Kit uzantısının en son sürümü. Yükleme ayrıntıları için bkz. QDK uzantısını ayarlama.

Sorunu tanımlama

Grover algoritması, kuantum bilişimindeki en ünlü algoritmalardan biridir. Çözdüğü sorunun türü genellikle "veritabanında arama" olarak adlandırılır, ancak bunu arama sorunu açısından düşünmek daha doğru olur.

Herhangi bir arama sorunu, $x$ $x arama öğelerini kabul eden bir soyut işlev $f(x)$ ile matematiksel olarak formüle edilebilir. $x$ öğesi arama sorununun çözümüyse $f(x)=1$. $x$ öğesi bir çözüm değilse $f(x)=0$. Arama sorunu, $f(x_0)=1$ gibi $x_0$ herhangi bir öğeyi bulmaktan oluşur.

Bu nedenle, herhangi bir arama sorununu şu şekilde formüle edebilirsiniz: klasik bir işlev $f(x):\{0,1\}^n \rightarrow\{0,1\}$, burada $n$, arama alanının bit boyutu olduğunda, $f(x_0)=1$ için bir giriş $x_0$ bulun.

Grover algoritmasını kullanarak arama sorununu çözmek için şunları yapmanız gerekir:

Sorunu Grover'ın görevi biçimine dönüştürün. Örneğin Grover algoritmasını kullanarak bir tamsayı $M$ faktörlerini bulmak istediğinizi varsayalım. Tamsayı çarpanlaştırma problemini, $f_M(x)=1[r]$ işlevi oluşturarak Grover'ın görevine dönüştürebilirsiniz; burada $1[r]=1$ eğer $r=0$ ise ve $1[r]=0$ eğer $r\neq0$ ise, $r$ de $M/x$'in kalanıdır. Bu şekilde, $f_M(x_i)=1$ değerini oluşturan $x_i$ tamsayıları $M$ faktörlerini oluşturur ve sorunu Grover'ın görevine dönüştürmüş olursunuz.
Grover görevinin işlevini bir kuantum kehaneti olarak uygulayın. Grover algoritmasını uygulamak için Grover'ınızın görevinin $f(x)$ işlevini kuantum kahini olarak uygulamanız gerekir.
Görevi çözmek için grover algoritmasını kahininizle birlikte kullanın. Bir kuantum kâhininiz olduğunda, sorunu çözmek ve çıkışı yorumlamak için Grover algoritmanızın uygulamasına takabilirsiniz.

Grover algoritması

Arama sorunu için $N=2^n$ uygun öğe olduğunu ve her öğeye $0$ ile $N-1$ arasında bir tamsayı atanarak indekslendiklerini varsayalım. Algoritmanın adımları şunlardır:

Başlangıçta, $\ket{0}$ durumunda başlatılan $n$ kubitlik bir yazmaç kullanın.
Yazmaçtaki her kubite $H$ uygulayarak yazmacı tekdüze bir süperpozisyona hazırlayın: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
Aşağıdaki işlemleri yazmaç $N_{\text{optimal}}$ kez uygulayın:
1. Çözüm öğeleri için $-1$ koşullu faz kayması uygulayan faz kahini $O_f$ .
2. Yazmaçtaki her kubite $H$ uygulayın.
3. $\ket{0}$ dışındaki her hesaplama temeli durumuna $-1$ koşullu faz kaydırması olan $-O_0$ uygulayın.
4. Yazmaçtaki her kubite $H$ uygulayın.
Çok yüksek olasılıkla çözüm olan bir öğenin dizinini elde etmek için yazmaç değerini ölçün.
Geçerli bir çözüm olup olmadığını görmek için öğeyi denetleyin. Aksi takdirde yeniden başlayın.

Grover algoritmasının kodunu yazın Q#

Bu bölümde, Q# içinde algoritmanın nasıl uygulanacağı açıklanır. Grover algoritması uygulanırken dikkate alınması gereken birkaç şey vardır. İşaretli durumunuzun ne olduğunu, bu durumu nasıl yansıtabileceğinizi ve algoritmayı çalıştıracak yineleme sayısını tanımlamanız gerekir. Grover görevinin işlevini uygulayan oraklı da tanımlamanız gerekir.

İşaretli durumu tanımlama

İlk olarak, aramada bulmaya çalıştığınız girişi tanımlarsınız. Bunu yapmak için Grover algoritmasından b, c ve d adımlarını uygulayan bir işlem yazın.

Bu adımlar birlikte Grover'ın $-H^{\otimes n} O_0 H^{\otimes n}$ difüzyon işleci olarak da bilinir.

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

İşlem, ReflectAboutMarked değişen sıfırlar ve birlerle işaretlenmiş temel durumu yansıtır. Bunu yapmak için Grover'ın difüzyon işlecini giriş kubitlerine uygular. İşlem, $X$ ve $H$ kapıları uygulanarak $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ durumunda başlatılan outputQubit adlı yardımcı bir kubiti kullanır. İşlem daha sonra $X$ geçidini yazmaçtaki diğer tüm kubitlere uygular ve bu da kubitin durumunu çevirir. Son olarak, kontrollü $X$ geçidini yardımcı kubite ve giriş kubitlerine uygular. Bu işlem, ancak ve ancak tüm giriş kubitleri işaretli durum olan $\ket{1}$ durumundaysa yardımcı kubiti çevirir.

En uygun yineleme sayısını tanımlama

Grover'ın araması, geçerli bir çıkışı ölçme olasılığı en yüksek olan en iyi yineleme sayısına sahiptir. Sorun $N=2^n$ olası uygun öğelere sahipse ve bunların $M$ değeri soruna çözümse, en iyi yineleme sayısı şu şekildedir:

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

En uygun yineleme sayısını aşarak yinelemeye devam etmek, olasılığı azaltmaya başlar ve $2 N_{\text{optimal}}$ yinelemesinde neredeyse sıfır başarı olasılığına ulaşılır. Bundan sonra, olasılık $3 N_{\text{optimal}}$ gibi bir değere kadar yeniden büyür.

Pratik uygulamalarda genellikle probleminizi çözene kadar kaç farklı çözümü olabileceği hakkında bilginiz olmaz. Bu sorunu ele almak için etkili bir strateji, iki güçteki tahminleri aşamalı olarak artırarak (1, 2, 4, 8, 16, ..., 2^n$) $M$ çözüm sayısını "tahmin etmek"tir. Bu tahminlerden biri, algoritmanın $\sqrt{\frac{N}{M}}$ civarında ortalama yineleme sayısına sahip çözümü bulmaya devam edeceği kadar yakın olacaktır.

Aşağıdaki Q# işlev, bir yazmaçtaki belirli bir kubit sayısı için en uygun yineleme sayısını hesaplar.

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

İşlev, CalculateOptimalIterations yineleme sayısını hesaplamak için yukarıdaki formülü kullanır ve ardından en yakın tamsayıya yuvarlar.

Grover'ın işlemini tanımlama

Q# Grover arama algoritmasının işlemi üç girişe sahiptir:

Kubit yazmacındaki kubit sayısı, nQubits : Int. Bu kayıt, arama probleminin geçici çözümünü kodlayacaktır. İşlemden sonra ölçülür.
En uygun yineleme sayısı, iterations : Int.
Grover görevi için aşama kahini temsil eden bir işlem phaseOracle : Qubit[] => Unit) : Result[]. Bu işlem, genel bir kubit yazmaç üzerinde birimsel dönüştürme uygular.

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

İşlem, $n$ kubitlik bir yazmacı $\ket{0}$ durumunda başlatır, yazmacı eşit olasılıklı bir süperpozisyona hazırlar ve ardından Grover algoritmasını belirtilen sayıdaki yinelemeler için uygular. Aramanın kendisi, işaretlenen durum ve başlangıç durumu hakkında tekrar tekrar düşünmekten oluşur ve bunu Q# içinde bir for döngüsü olarak yazabilirsiniz. Son olarak yazmaç ölçülür ve sonuç döndürülür.

Kod üç yardımcı işlemi kullanır: PrepareUniform, ReflectAboutUniformve ReflectAboutAllOnes.

All-zeros durumundaki bir yazmaç verildiğinde, PrepareUniform işlemi tüm temel durumlar üzerinde tekdüzen bir süperpozisyon hazırlar.

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

'ReflectAboutAllOnes' işlemi tümü bir olan durum üzerine yansıtır.

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

İşlem ReflectAboutUniform , tekdüzen süperpozisyon durumunu yansıtır. İlk olarak, tekdüzen süper pozisyonu tamamen sıfır durumuna dönüştürür. Ardından sıfır durumunu tümü bire bir durumuna dönüştürür. Son olarak, tüm birler durumunu yansıtır. Tekdüzen süperpozisyon durumu etrafında vektör uzayında bir yansıma olarak geometrik olarak yorumlanabildiği için, işlem ReflectAboutUniform olarak adlandırılır.

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

Son kodu çalıştırma

Artık Grover arama algoritmasının belirli bir örneğini uygulamak ve faktöring sorununu çözmek için tüm bileşenlere sahipsiniz. Main işlemi, kubit sayısını ve yineleme sayısını belirleyerek sorunu hazırlar ve tamamlanır.

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

Programı çalıştırma

Programınızı çalıştırmak için istediğiniz platformu seçin.

Azure Quantum'da Copilot
Visual Studio Code

Kodunuzu Azure Quantum'da Copilot ile ücretsiz olarak test Q# edebilirsiniz. Tek ihtiyacınız bir Microsoft (MSA) e-posta hesabıdır. Azure Quantum'daki Copilot hakkında daha fazla bilgi için Azure Quantum'u Keşfedin'e bakın.

Tarayıcınızda Azure Quantum'da Copilot'i açın.

Aşağıdaki kodu kopyalayıp kod düzenleyicisine yapıştırın.

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

İpucu

Azure Quantum'daki Copilot'tan, kod düzenleyicisinin sağ köşesindeki VS Code logosu düğmesini seçerek programınızı Web için VS Code'da açabilirsiniz.

Bellek içi simülatörü kullanarak programı çalıştırma

Bellek içi Simülatörü'ne tıklayın.
Çalıştırılacak çekim sayısını seçin ve Çalıştır'ı seçin.
Sonuçlar histogramda ve Sonuçlar alanlarında görüntülenir.
Kodu açıkla'yı seçin, böylece Copilot kodu size açıklasın.

Quantinuum Öykünücüsünü kullanarak programı çalıştırın

Ayrıca programınızı ücretsiz Quantinuum Öykünücüsünesunabilirsiniz. Öykünücü, 20 kuantum bitine sahip bir kuantum bilgisayarını simüle eder.

In-Memory Simülatörü açılan listeden seçin ve Quantinuum Öykünücüsüseçin.
Çekim sayısını seçin (şu anda 20 ile sınırlıdır) ve Çalıştır'ı seçin.

Visual Studio Code'u açın ve Yeni Metin Dosyası Oluştur'u > seçerek yeni bir dosya oluşturun.
Dosyayı GroversAlgorithm.qs olarak kaydedin. Bu dosya, programınızın kodunu içerir Q# .

Aşağıdaki kodu dosyaya GroversAlgorithm.qs kopyalayın.


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

Programı çalıştırmadan önce target profilin Sınırsız olarak ayarlandığından emin olun. Görünüm - Komut Paleti'ni seçin, QIR'yi arayın, Azure Quantum QIR profilini ayarla: sınırsız seçeneğini seçin.
Programınızı çalıştırmak için işlemin üst kısmındaki komut listesinde Çalıştır'ıMainveya Ctrl+F5 tuşlarına basın. Varsayılan olarak, derleyici işlemi veya işlevi varsayılan simülatörde çalıştırır Main .
Çıkışınız terminaldeki hata ayıklama konsolunda görünür.

Dikkat

target Profil Sınırsız olarak ayarlanmamışsa, programı çalıştırdığınızda bir hata alırsınız.

Diğer Q# öğreticileri keşfedin:

Kuantum dolanıklığı , kubitleri işleyen ve ölçen ve süper pozisyon ile dolanıklığın etkilerini gösteren bir Q# programın nasıl yazıldığını gösterir.
Kuantum rastgele sayı oluşturucu , süper pozisyondaki kubitlerden rastgele sayılar oluşturan bir Q# programın nasıl yazıldığını gösterir.
Quantum Fourier Transform , belirli kubitleri doğrudan ele alan bir Q# programın nasıl yazıldığını keşfeder.
Kuantum Kataları, kuantum bilişimi ve programlama öğelerini eş zamanlı olarak öğretmeyi amaçlayan, kendi hızınıza göre ilerleyebileceğiniz öğreticiler ve programlama alıştırmalarıdır.