Q# Grover search

One of the main reasons why quantum computers arouse the imagination and hopes of many people around the world is the ability to significantly increase the speed of calculations compared to classical computers. Unfortunately, it will probably be many years before we see quantum computers in everyday life. However, there are already algorithms that can perform certain tasks faster than classical computers. One such algorithm is the Grover search algorithm.

The Grover search algorithm was created in 1996 by Lov Grover. This algorithm allows to search for results in an unstructured dataset. The difference in the search speed is significant because when using classic computers, usually to find an object in an unordered list, we need to perform an average of N/2 searches, and if we are unlucky, we need to search the entire list, i.e. check all N possibilities. In the case of Grover’s algorithm, only √N operations are required.
 
The Grover search algorithm consists mainly of two elements: the oracle and the amplitude amplification technique.
 
The Oracle is an algorithm to identify/mark the searched item. Depending on what problem we want to solve, it is necessary to create an appropriate oracle that will find the right element for us.
 
For two qubits, there are four possible values |00>, |01> |10> |11>. In the sample program, we will try to find the value |11> for two qubits, therefore, the oracle algorithm will only consist of a CZ gate.
After passing through such a gate, spin (amplitude) only for |11> will be reversed. This is easy to see in mathematical notation which could be written as follows.
 
[0.5+0j, 0.5+0j, 0.5+0j, -0.5+0j]
 
The element with a negative value (reverse spin) is the element we are looking for.
 
Amplitude amplification A technique to increase the probability of a selected item and decrease the probability of other outcomes. It consists of the following quantum gates:
 

 
The whole circut looks like this:
 

 
All that remains is to translate it into machine language:
 
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();
            }
        }
    }
}

Q# Library:

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

 
After running the algorithm, we will be able to find the value |11>
 

 
The project is available for download here