Öğretici: Q# dilinde Grover arama algoritmasını uygulama

Bu öğreticide, Q# Arama tabanlı sorunları çözümlemek için ' de Grover 'in algoritmasını uygulamayı öğreneceksiniz.

Grover 'in algoritması, hisse bilgi işlem için en çok kullanılan algoritmalardan biridir. Çözdüğü sorun genellikle "veritabanı arama" olarak adlandırılır, ancak bunu arama sorunu açısından düşünmek daha doğru olur.

Herhangi bir arama görevi, $x $ arama öğelerini kabul eden $f (x) $ soyut işleviyle matematiksel olarak formül oluşturabilir. $X $ öğesi, arama görevinin bir çözümüdür ve $f (x) = 1 $. $X $ öğesi bir çözüm değilse, $f (x) = 0 $. Arama sorunu, $f (x_0) = 1 $ gibi $x _0 $ öğesini bulmayı içerir.

Önkoşullar

• Tercih ettiğiniz dil ve geliştirme ortamınızı kullanarak hisse geliştirme setini (QDK) yükler .
• Zaten QDK yüklüyse, en son sürüme güncelleştirdiğinizden emin olun.
• Bir Q# Q# uygulamaiçin bir Python ana bilgisayar programıylaveya bir C# ana bilgisayar programıylabir proje oluşturun.

Bu öğreticide aşağıdakilerin nasıl yapılacağını öğreneceksiniz:

Grover 'in algoritma görevi

Klasik bir işlev $f (x): \ {0, 1 \ } ^ n \sağtarrow \ {0, 1 \ } $, burada $n $, arama alanının bit boyutunda, $f (x_0) = 1 $ için bir giriş $x _0 $ bulur.

Bir sorunu çözmek için Grover 'in algoritmasını uygulamak için şunları yapmanız gerekir:

1. Sorunu bir Grover görevi biçimine dönüştürün: Örneğin, Grover 'in algoritmasını kullanarak $M bir tamsayı çarpanları bulmak istediğimizde düşünün. $ $F _M (x) = 1 [r], $ $ $1 [r] = 1 $ if $r = $0 ve $1 [r] = 0 $, $r\neq0 $ ve $r $ $M/x $ ' in geri kalanı bir işlev oluşturarak tamsayı bir görevi bir Grover görevine dönüştürebilirsiniz. Bu şekilde, $f _M (x_i) = 1 $ olan _i $ $x tamsayılar $M $ faktörlerdir ve sorunu bir Grover görevine dönüştürüyoruz.
2. Grover 'in görevinin fonksiyonunu bir hisse Oracle olarak uygulayın: Grover 'in algoritmasını uygulamak Için, Grover 'in görevinin $f (x) $ işlevini bir hisse Oracleolarak uygulamanız gerekir.
3. Görevi çözmek için, Oracle Ile Grover 'in algoritmasını kullanın: bir hisse bir Oracle 'niz olduktan sonra, sorunu çözmek ve çıktıyı yorumlamak Için onu Grover 'in algoritma uygulamasına ekleyebilirsiniz.

Grover 'in algoritmasına hızlı genel bakış

Arama görevi için $N = 2 ^ N $ uygun öğe olduğunu ve her öğe $0 $ ' den $N-$1 ' e bir tamsayı atayarak dizinlendiğini varsayalım. Algoritmanın adımları şunlardır:

1. $ \Tus$ durumunda başlatılan bir $n $ qubits kaydı ile başlayın {0} .
2. Kayıttaki her bir qubit 'e $H $ uygulayarak kaydı bir Tekdüzen üst konumuna hazırlayın: $ $ | \psı\rangle = \frac {1} {N ^ {1/2}} \ sum_ {x = 0} ^ {N-1} | x\rangle $ $
3. Register $N _ {\Text{optimize mal}} $ kez şu işlemleri uygulayın:
   1. Oracle $O _f $ ' nin, çözüm öğeleri için $-$1 Koşullu aşama kaydırması uygulayan aşaması.
   2. Kayıttaki her bir qubit 'e $H $ uygulayın.
   3. $-O_0 $, $-$1 $/Tus$ hariç her hesaplama tabanlı duruma $-' a bir koşullu aşama SHIFT 'i uygulayın {0} .
   4. Kayıttaki her bir qubit 'e $H $ uygulayın.
4. Çok yüksek olasılığa sahip bir çözüm olan bir öğenin dizinini almak için kaydı ölçün.
5. Geçerli bir çözüm olup olmadığını denetleyin. Aksi takdirde, yeniden başlatın.

Grover 'in algoritması için kodu yazın

Şimdi de algoritmanın nasıl uygulanacağını görelim Q# .

Grover 'in yayılma işleci

İlk olarak, yukarıdaki döngüden b, c ve d adımlarını uygulayan bir işlem yazın. Birlikte, bu adımlar aynı zamanda Grover dağılımı işleci $-H ^ {\otimes n} O_0 H ^ {\otimes n} $ olarak da bilinir

operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {

    within {
        ApplyToEachA(H, inputQubits);
        ApplyToEachA(X, inputQubits);
    } apply {
        Controlled Z(Most(inputQubits), Tail(inputQubits));
    }

}

Bu işlem, Grover 'in diffwııo işleci içinde gerçekleşen işlemlerin otomatik olarak bir kısmını uygulayan ın-Apply ifadesini kullanır.

Kodu anlamak için iyi bir uygulamadır ve işlemler, işlemin ReflectAboutUniform Grover işlecinin diffoperator uyguladığı kalem ve kağıt ile kontrol edilir. Bunu görmek için, yalnızca Controlled Z(Most(inputQubits),Tail(inputQubits)) ve yalnızca tüm qubitleri $ \gre$ durumunda olduğunda işlemin yalnızca bir etkiye sahip olduğunu unutmayın {1} .

API belgelerine bakarak, kullanılan işlemlerin ve işlevlerin ne kadar olduğunu kontrol edebilirsiniz:

• ApplyToEachA
• Most
• Tail

İşlem, ReflectAboutUniform Tekdüzen üst konum durumu hakkında vektör alanında bir yansıma olarak, geometrik olarak yorumlanabileceğinden çağrılır.

Yineleme sayısı

Grover 'in aramasında geçerli bir çıktıyı ölçmenin en yüksek olasılığını veren en iyi sayıda yineleme vardır. Soruna $N = 2 ^ N $ uygun öğeler varsa ve bunların $M $, soruna çözüm varsa, en iyi yineleme sayısı:

$ $N _ {\Text{optimal}}\approx\frac{\pi} {4} \Sqrt{\frac{n}{m}} $ $

Bu sayının yinelemeye devam edilmesi, $2 N_ {\Text{opmal}} $ yineleme üzerinde neredeyse sıfır başarı olasılığını yapana kadar bu olasılığı azaltmaya başlar. Bundan sonra, olasılık $3 tekrar artar N_ {\Text{opmal}} $ ve bu şekilde devam eder.

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 üsde tahminin (örn. $1, 2, 4, 8, 16,..., 2 ^ n $) tahminlerini aşamalı olarak artırarak $M çözüm sayısını "tahmin etme" aşamasında. Bu tahminlerden biri, algoritmanın $ \sqrt{\frac{N}{M}} $ etrafında Ortalama sayıda yinelemeyle çözüm bulacağımızı yeterince kapatacaktır.

Grover 'in işlemini Tamam

Artık Q# Grover 'in arama algoritması için bir işlem yazmaya hazırsınız. Üç girişe sahip olacaktır:

• register : Qubit[]Her durumda başlatılması gereken bir qubit dizisi Zero . Bu kayıt, geçici çözümü arama sorununa kodlayacaktır. İşlem sonrasında ölçülecektir.
• phaseOracle : (Qubit[]) => Unit is AdjGrover 'in görevi için Oracle aşamasını temsil eden bir işlem. Bu işlem, genel qubit kayıt üzerinde bir Unitary dönüştürmesi uygular.
• iterations : IntAlgoritmanın yinelemelerini temsil eden bir tamsayı.

operation RunGroversSearch(register : Qubit[], phaseOracle : (Qubit[]) => Unit is Adj, iterations : Int) : Unit {
    // Prepare register into uniform superposition.
    ApplyToEach(H, register);
    // Start Grover's loop.
    for _ in 1 .. iterations {
        // Apply phase oracle for the task.
        phaseOracle(register);
        // Apply Grover's diffusion operator.
        ReflectAboutUniform(register);
    }
}

Oracle 'ı uygulama

Grover 'in algoritmasını daha hızlı hale getiren temel özelliklerden biri, hisse maların yalnızca tek girişler üzerinde değil, girişlerin üst konumlarında de hesaplamalar gerçekleştirme yeteneğidir. Yalnızca hisse türlerini kullanarak bir arama sorununun örneğini açıklayan $f (x) $ işlevini hesaplamanız gerekir. Bu şekilde, girişlerin bir üst konumundan hesaplanabilir.

Ne yazık ki, klasik işlevleri hisse işleme dönüştürmek için otomatik bir yol yoktur. Bu, bilgisayar bilimi ile geri döndürülebilir bilgi işlem adlı bir araştırma alanıdır.

Ancak, işlevinizi $f (x) $ ' i bir hisse Oracle 'a çevirmenizi sağlayacak bazı yönergeler vardır:

1. Klasik işlevi uygulaması kolay yapı taşlarına ayırma. Örneğin, $f (x) $ işlevinizi aritmetik işlemler veya Boole Logic Gates dizisine ayırmayı deneyebilirsiniz.
2. Ara işlemleri uygulamak için kitaplığın daha yüksek düzey yapı taşlarını kullanın Q# . Örneğin, işlevinizi basit aritmetik işlemler birleşimine göre oluşturduysanız, ara işlemleri uygulamak için Numerics kitaplığını kullanabilirsiniz.

Aşağıdaki denklik tablosu, ' de Boole işlevleri uygularken yararlı olabilir Q# .

Örnek: bir sayının bölen olup olmadığını denetlemek için hisse işlemi

Örnek olarak, içinde düzenleme sorununun $f _M (x) = 1 [r] $ işlevini nasıl ifade ettireceğinizi görelim Q# .

Genel olarak, $M/x $ bölümünün kalanını hesaplar ve sıfıra eşit olup olmadığını kontrol edersiniz. Eğer ise program çıkışlar olur ve yoksa 1 Program çıkış olur 0 . Şunları yapmanız gerekir:

• Bölümün kalanını hesaplar.
• Geri kalan ise, çıkış biti üzerinde denetimli bir işlem uygulayın 1 0 .

Bu nedenle, bir hisse miktarı ile iki sayının bir bölümünü hesaplamanız gerekir. Neyse ki, bölümü sıfırdan uygulayan devreyi yazmanız gerekmez, DivideI bunun yerine Numerics kitaplığındaki işlemi kullanabilirsiniz.

Açıklamasına bakarak DivideI , üç qubit kayıt olduğunu belirtir: $n $ bit bölünen xs , $n $ bit bölen ys ve result durumunda başlatılması gereken $n $-bit Zero . Bu işlem, Adj + Ctl eşlenebilmemiz ve uygulama içi deyimlerde kullanabiliriz. Ayrıca, açıklamada, giriş kaydındaki bölünün xs geri kalanı tarafından değiştirildiğini söyleyerek. Bu, işlemin sonucunda değil, yalnızca geri kalanı ilgilentireceğiz için mükemmeldir.

Daha sonra aşağıdakileri yapan bir hisse işlemi oluşturabilirsiniz:

1. Üç giriş alır:
   • Bölünen, number : Int . Bu, $f _M (x) $ $M $ ' dir.
   • Böleni kodlamalı bir qubit dizisi divisorRegister : Qubit[] . Bu, büyük olasılıkla bir üst konum durumunda olan $f _M (x) $ $x.
   • target : Qubit$F _m (x) $ ' in çıkışı $1 $ ise ters bir hedef qubit.
2. Yalnızca ters çevrilebilir hisse operasyonlarını kullanarak $M/x $ bölümünü hesaplar ve target yalnızca geri kalan sıfır ise, ve ' nin durumunu çevirir.
3. , target Kullanılan yardımcı qubits 'i, ölçüm gibi geri alınamaz işlemlere yönelik olarak sıfır durumuna döndürmek için, öğesinin, ' i hariç tüm işlemleri geri alır. Bu adım işlem sırasında entanglement ve superposition ' i korumak için önemlidir.

Bu hisse işleme uygulanacak kod şu şekilde yapılır:

operation MarkDivisor (
    dividend : Int,
    divisorRegister : Qubit[],
    target : Qubit
) : Unit is Adj + Ctl {
    // Calculate the bit-size of the dividend.
    let size = BitSizeI(dividend);
    // Allocate two new qubit registers for the dividend and the result.
    use dividendQubits = Qubit[size];
    use resultQubits = Qubit[size];
    // Create new LittleEndian instances from the registers to use DivideI
    let xs = LittleEndian(dividendQubits);
    let ys = LittleEndian(divisorRegister);
    let result = LittleEndian(resultQubits);

    // Start a within-apply statement to perform the operation.
    within {
        // Encode the dividend in the register.
        ApplyXorInPlace(dividend, xs);
        // Apply the division operation.
        DivideI(xs, ys, result);
        // Flip all the qubits from the remainder.
        ApplyToEachA(X, xs!);
    } apply {
        // Apply a controlled NOT over the flipped remainder.
        Controlled X(xs!, target);
        // The target flips if and only if the remainder is 0.
    }
}

İşlemi Oracle aşamasına Dönüştür

Bu işlem, MarkDivisor bir entangled yardımcı qubit () ile geçerli öğeleri işaretlediği için, Oracle işaretlemesi olarak bilinir target . Ancak, Grover 'in algoritması bir Oracle, diğer bir deyişle, çözüm öğeleri için $-$1 Koşullu aşama kaydırma uygular. Ancak, yukarıdaki işlem VAIN 'da yazılmadı. Bir Oracle türünden diğerine geçiş yapmak çok kolaydır Q# .

Oracle 'ı bir aşama olarak, aşağıdaki işlem ile uygulayabilirsiniz:

operation ApplyMarkingOracleAsPhaseOracle(
    markingOracle : (Qubit[], Qubit) => Unit is Adj,
    register : Qubit[]
) : Unit is Adj {
    use target = Qubit();
    within {
        X(target);
        H(target);
    } apply {
        markingOracle(register, target);
    }
}

Bu sık kullanılan dönüşüm, genellikle aşama olarak bilinir ve çok sayıda hisse bilgi işlem algoritmalarında yaygın olarak kullanılır. Bu Microsoft Learn modülündebu tekniğin ayrıntılı bir açıklamasını bulabilirsiniz.

Grover araması ile düzenleme sayılar

Artık, bir Grover 'in arama algoritmasından oluşan belirli bir örneği uygulamak ve düzenleme sorununu çözmek için tüm malzemeleri vardır.

21 ' in bir faktörünü bulmak için aşağıdaki programı kullanalım. Kodu basitleştirmek için, geçerli öğelerin $M $ sayısını belirteceğimizi varsayalım. Bu durumda, 3 ve 7 ve 1 ile 21 arasında olmak üzere iki etken olduğundan $M = $4.

namespace GroversTutorial {
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Arithmetic;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Preparation;

    @EntryPoint()
    operation FactorizeWithGrovers(number : Int) : Unit {

        // Define the oracle that for the factoring problem.
        let markingOracle = MarkDivisor(number, _, _);
        let phaseOracle = ApplyMarkingOracleAsPhaseOracle(markingOracle, _);
        // Bit-size of the number to factorize.
        let size = BitSizeI(number);
        // Estimate of the number of solutions.
        let nSolutions = 4;
        // The number of iterations can be computed using the formula.
        let nIterations = Round(PI() / 4.0 * Sqrt(IntAsDouble(size) / IntAsDouble(nSolutions)));

        // Initialize the register to run the algorithm
        use (register, output) = (Qubit[size], Qubit());
        mutable isCorrect = false;
        mutable answer = 0;
        // Use a Repeat-Until-Succeed loop to iterate until the solution is valid.
        repeat {
            RunGroversSearch(register, phaseOracle, nIterations);
            let res = MultiM(register);
            set answer = BoolArrayAsInt(ResultArrayAsBoolArray(res));
            // Check that if the result is a solution with the oracle.
            markingOracle(register, output);
            if MResetZ(output) == One and answer != 1 and answer != number {
                set isCorrect = true;
            }
            ResetAll(register);
        } until isCorrect;

        // Print out the answer.
        Message($"The number {answer} is a factor of {number}.");

    }

    operation MarkDivisor (
        dividend : Int,
        divisorRegister : Qubit[],
        target : Qubit
    ) : Unit is Adj+Ctl {
        let size = BitSizeI(dividend);
        use (dividendQubits, resultQubits) = (Qubit[size], Qubit[size]);
        let xs = LittleEndian(dividendQubits);
        let ys = LittleEndian(divisorRegister);
        let result = LittleEndian(resultQubits);
        within{
            ApplyXorInPlace(dividend, xs);
            DivideI(xs, ys, result);
            ApplyToEachA(X, xs!);
        }
        apply{
            Controlled X(xs!, target);
        }
    }

    operation PrepareUniformSuperpositionOverDigits(digitReg : Qubit[]) : Unit is Adj + Ctl {
        PrepareArbitraryStateCP(ConstantArray(10, ComplexPolar(1.0, 0.0)), LittleEndian(digitReg));
    }

    operation ApplyMarkingOracleAsPhaseOracle(
        markingOracle : (Qubit[], Qubit) => Unit is Adj,
        register : Qubit[]
    ) : Unit is Adj {
        use target = Qubit();
        within {
            X(target);
            H(target);
        } apply {
            markingOracle(register, target);
        }
    }

    operation RunGroversSearch(register : Qubit[], phaseOracle : ((Qubit[]) => Unit is Adj), iterations : Int) : Unit {
        ApplyToEach(H, register);
        for _ in 1 .. iterations {
            phaseOracle(register);
            ReflectAboutUniform(register);
        }
    }

    operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
        within {
            ApplyToEachA(H, inputQubits);
            ApplyToEachA(X, inputQubits);
        } apply {
            Controlled Z(Most(inputQubits), Tail(inputQubits));
        }
    }
}

Visual Studio veya Visual Studio Code ile çalıştırın

Yukarıdaki program, @EntryPoint() Proje yapılandırmasına ve komut satırı seçeneklerine bağlı olarak bir simülatör veya kaynak Estimator üzerinde özniteliğiyle işaretlenmiş işlem veya işlevi çalıştırır.

dotnet build

dotnet run --no-build --number 21

Her iki ortamda da şu iletiyi terminalde görebilirsiniz:

The number 7 is a factor of 21.

Ekstra: Python ile istatistikleri denetleme

Algoritmanın doğru şekilde çalışıp çalışmadığını nasıl kontrol edebilirsiniz? Örneğin, Grover 'in arama 'yı Yukarıdaki kodda rastgele bir sayı üreticisi ile değiştiriyoruz, sonunda $N $ denemeleri de bir faktör bulur.

Programın gerektiği gibi çalışıp çalışmadığını denetlemek için küçük bir Python betiği yazalım.

İlk olarak, Grover 'in arama gerçekleştirildikten sonra ilk ölçüm sonucunun çıktısını almak yerine, yineleme-Until döngüsünden kurtulmak için ana işleminizi değiştirin:

@EntryPoint()
operation FactorizeWithGrovers2(number : Int) : Int {

    let markingOracle = MarkDivisor(number, _, _);
    let phaseOracle = ApplyMarkingOracleAsPhaseOracle(markingOracle, _);
    let size = BitSizeI(number);
    let nSolutions = 4;
    let nIterations = Round(PI() / 4.0 * Sqrt(IntAsDouble(size) / IntAsDouble(nSolutions)));

    use register = Qubit[size] {
        RunGroversSearch(register, phaseOracle, nIterations);
        let res = MultiM(register);
        return ResultArrayAsInt(res);
        // Check whether the result is correct.
    }

}

Çıkış türünün ' dan ' a değiştiği Unit Int , Python programı için yararlı olacağını unutmayın. Python programı çok basittir; yalnızca işlemi FactorizeWithGrovers2 birkaç kez çağırır ve sonuçları bir histogram halinde çizer.

Kod şunlardır:

import qsharp
qsharp.packages.add("Microsoft.Quantum.Numerics")
qsharp.reload()
from GroversTutorial import FactorizeWithGrovers2
import matplotlib.pyplot as plt
import numpy as np

def main():

    # Instantiate variables
    frequency =  {}
    N_Experiments = 1000
    results = []
    number = 21

    # Run N_Experiments times the Q# operation.
    for i in range(N_Experiments):
        print(f'Experiment: {i} of {N_Experiments}')
        results.append(FactorizeWithGrovers2.simulate(number = number))

    # Store the results in a dictionary
    for i in results:
        if i in frequency:c
            frequency[i]=frequency[i]+1
        else:
            frequency[i]=1

    # Sort and print the results
    frequency = dict(reversed(sorted(frequency.items(), key=lambda item: item[1])))
    print('Output,  Frequency' )
    for k, v in frequency.items():
        print(f'{k:<8} {v}')

    # Plot an histogram with the results
    plt.bar(frequency.keys(), frequency.values())
    plt.xlabel("Output")
    plt.ylabel("Frequency of the outputs")
    plt.title("Outputs for Grover's factoring. N=21, 1000 iterations")
    plt.xticks(np.arange(1, 33, 2.0))
    plt.show()

if __name__ == "__main__":
    main()

Program aşağıdaki histogramı üretir:

Histogram ' ta görebileceğiniz gibi, algoritma arama sorununa (1, 3, 7 ve 21) çözüm olmayan çözümlerden çok daha yüksek bir olasılık verir. Grover 'in algoritmasını, arama sorununa çözüm olan bu indeksler için tam olarak taraflı bir şekilde sunan hisse rastgele bir Oluşturucu olarak düşünebilirsiniz.

Sonraki adımlar

Artık Grover 'in algoritmasını nasıl uygulayacağınızı öğrenmiş olduğunuza göre, bir matematiksel sorunu bir arama görevine dönüştürmeyi ve bu dosyayı Q# ve Grover 'in algoritmasıyla çözmeyi deneyin.