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

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 Vs Code'un Web'de açılması.
  • Azure Quantum Development Kit uzantısının en son sürümü. Yükleme ayrıntıları için bkz . VS Code'da QDK'yi yükleme.

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:

1. 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. $r\neq0$ ve $r$ $M/x$ değerinin geri kalanıysa $$f_M(x)=1[r],$$ işlevi 1[r]=1$ $r=1[r]=0$ işlevi oluşturarak tamsayı çarpanlaştırma sorununu Grover'ın görevine dönüştürebilirsiniz. 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.
2. Grover görevinin işlevini kuantum kahini 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.
3. Görevi çözmek için grover algoritmasını kahininizle birlikte kullanın. Kuantum kahininiz olduktan sonra sorunu çözmek ve çıkışı yorumlamak için grover'ınızın algoritma uygulamasına takabilirsiniz.

Grover algoritması

Arama sorunu için $N=2^n$ uygun öğeler olduğunu ve her öğeye $0$ olan bir tamsayı atanarak $N-1$ olarak dizine alındıklarını varsayalım. Algoritmanın adımları şunlardır:

1. $\ket{0}$ durumunda başlatılan $n$ kubitlerin bir yazmaç ile başlayın.
2. Yazmaçtaki her kubite $H$ uygulayarak kaydı tekdüzen bir süper konuma hazırlayın: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
3. Aşağıdaki işlemleri yazmaç $N_{\text{optimal}}$ kez uygulayın:
   1. Çözüm öğeleri için $-1$ koşullu aşama değişimi uygulayan aşama 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.
4. Çok yüksek olasılıkla çözüm olan bir öğenin dizinini elde etmek için yazmaç değerini ölçün.
5. 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 Q#

Bu bölümde, içinde algoritmanın Q#nasıl uygulanılacağı 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 kahini de 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, outputQubit$X$ ve $H$ geçitleri uygulanarak $\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$ durumunda başlatılan yardımcı bir kubit 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, yalnızca tüm giriş kubitleri işaretli durumdaki $\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ı yinelemeye devam etmek, $2 N_{\text{optimal}}$ yinelemesinde neredeyse sıfır başarı olasılığına ulaşana kadar bu olasılığı azaltmaya başlar. 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 nQubits : Intyazmaçtaki kubit sayısı. Bu kayıt, belirsiz çözümü arama sorununa kodlar. İş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, GroverSearch $\ket{0}$ durumundaki $n$ kubitlerin bir kaydını başlatır, yazmacı tekdüzen bir süper pozisyona hazırlar ve ardından Grover algoritmasını belirtilen sayıda yineleme için uygular. Aramanın kendisi, işaretlenen durum ve başlangıç durumu hakkında sürekli olarak yansıtılmasından oluşur ve bunu for döngüsü olarak yazabilirsiniz Q# . Son olarak, yazmaç ölçer ve sonucu döndürür.

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

All-zeros durumundaki bir yazmaç verüldüğünde, PrepareUniform işlem tüm temel durumlara göre tekdüzen bir süper konum hazırlar.

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

''ReflectAboutAllOnes' işlemi all-one durumu hakkında yansıtır.

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

İşlem ReflectAboutUniform , tekdüzen süper konum durumu hakkında yansıtır. İlk olarak, tekdüzen süper pozisyonu sıfıra 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ü bir durumunu yansıtır. tekdüzen süper konum durumu hakkında vektör alanında bir yansıma olarak geometrik olarak yorumlanabildiği için işlem çağrılır ReflectAboutUniform .

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. İşlemi tamamlamak Main için kubit sayısını ve yineleme sayısını belirterek sorunu ayarlar

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

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 bkz . Azure Quantum'u keşfetme.

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

2. 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

1. Bellek içi Simülatörü'ne tıklayın.
2. Çalıştırılacak çekim sayısını seçin ve Çalıştır'ı seçin.
3. Sonuçlar histogramda ve Sonuçlar alanlarında görüntülenir.
4. Copilot'un kodu size açıklamasını istemesi için Kodu açıkla'ya tıklayın.

Quantinuum H Serisi Öykünücüsü kullanarak programı çalıştırma

Programınızı ücretsiz Quantinuum H Serisi Öykünücüsü'ne de gönderebilirsiniz. Öykünücü, 20 kubitli bir kuantum bilgisayarın simülasyonunu oluşturur.

1. Bellek İçi Simülatör açılan listesini seçin ve Quantinuum H Serisi Öykünücüsü'ne tıklayın.
2. Çekim sayısını seçin (şu anda 20 ile sınırlıdır) ve Çalıştır'ı seçin.

Visual Studio Code

1. Visual Studio Code'u açın ve Yeni Metin Dosyası Oluştur'u > seçerek yeni bir dosya oluşturun.

2. Dosyayı GroversAlgorithm.qs olarak kaydedin. Bu dosya, programınızın kodunu içerir Q# .

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

4. Programı çalıştırmadan önce profilin Sınırsız olarak ayarlandığından target emin olun. Görünüm - Komut Paleti'ni seçin, QIR'yi arayın, öğesini seçinQ#: Azure Quantum QIR target profilini ayarlayın ve ardından : sınırsız'ı seçinQ#.>

5. Programınızı çalıştırmak için işlemin üst Main kısmındaki komut listesinde Çalıştır'ı seçin veya 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 .

6. Çıkışınız terminaldeki hata ayıklama konsolunda görünür.

Not

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

İlgili içerik

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 aynı anda öğretmeyi amaçlayan kendi hızındaki öğreticiler ve Q# programlama alıştırmalarıdır.