Q# Grover search

Jednym z głównych powodów dlaczego komputery kwantowe rozbudzają wyobraźnie i nadzieje wielu osób na całym świecie jest możliwość znacznego zwiększenia prędkości wykonywanych obliczeń w porównaniu do komputerów klasycznych. Niestety zanim ujrzymy komputery kwantowe w codziennym życiu minie zapewne wiele lat. Niemniej już teraz istnieją algorytmy które potrafią wykonywać określone zadania szybciej niż klasyczne komputery. Jednym z takich algorytmów jest Grover search algorythm.

Grover search algorythm został stworzony w 1996 roku przez Lov Grovera. Algorytm ten pozwala wyszukiwaniu wyników w nieustrukturyzowanej zestawie danych. Różnica zaś szybkości wyszukiwania jest znacząca bowiem przy wykorzystywaniu klasycznych komputerów zwykle aby znaleźć obiekt w nieuporządkowanej liście musimy wykonać średnio N/2 wyszukań a jeśli mamy pecha przeszukać całą listę czyli sprawdzić wszystkie N możliwości. W przypadku algorytmu Grovera konieczne jest wykonanie jedynie √N operacji.
 
Grover search algorythm składa się głównie z dwóch elementów są nimi wyrocznia oraz technika amplitudę amplification.
 
Wyrocznia to algorytm mający na celu określenie/oznaczenie wyszukiwanego elementu. W zależności od tego jaki problem chcemy rozwiązać konieczne jest stworzenie odpowiedniej wyroczni która wyszuka dla nas odpowiedni element.
 
Dla dwóch kubitów istnieje możliwość wystąpienia czterech wartości |00>, |01> |10> |11>. W przykładowym programie będziemy się starali znaleźć wartość |11> dla dwóch kubitów dlatego algorytm wyroczni będzie składał się jedynie z bramki CZ.
Po przejściu przez taką bramkę spin (amplituda) tylko dla wartości |11> będzie odwrócona. Łatwo to zauważyć w w notacji matematycznej którą można by zapisać w następujący sposób.
 
[0.5+0j, 0.5+0j, 0.5+0j, -0.5+0j]
 
Element z ujemną wartością (odwróconym spinem) to poszukiwany przez nas element.
 
Amplitude amplification technika mająca na celu zwiększenie prawdopodobieństwa dla wybranego elementu oraz zmniejszenie prawdopodobieństwa wystąpienia innych wyników. Składa się on z następujących bramek kwantowych:
 

 
Cały układ zaś prezentuję się następująco:
 

 
Pozostaje jedynie przenieść to na język maszynowy:
 
Host:

using Microsoft.Quantum.Simulation.Simulators;
using Quantum.QuantumDreamLibrary;

namespace QuantumDream
{
    static class Program
    {
        static void Main(string[] args)
        {
            using (var sim = new QuantumSimulator())
            {
                for (int i = 0; i < 10; i++)
                {
                    var result = GroverSearch.Run(sim).Result;
                    var (result1, result2) = result;
                    Console.WriteLine(result1 + "" + result2);
                }

                Console.WriteLine("Press any key to continue");
                Console.ReadKey();
            }
        }
    }
}

Bibloteka Q#:

 
namespace Quantum.QuantumDreamLibrary {

    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Intrinsic;

    @EntryPoint()
    operation GroverSearch()  : (Result, Result) {
        use (q1, q2) = (Qubit(), Qubit());   
        H(q1);
        H(q2);
        
        //oracle
        CZ(q1,q2);

        //amplitude amplification
        H(q1);
        H(q2);
        Z(q1);
        Z(q2);
        CZ(q1,q2);
        H(q1);
        H(q2);

        //Measure
        let m1 = M(q1);
        let m2 = M(q2);
        
        return (m1, m2);
    }
}

 
Po uruchomieniu algorytmu uda nam się za każdym razem znaleźć szukaną wartość |11>
 

 
Projekt dostępny jest do pobrania tutaj