{{announcement.body}}
{{announcement.title}}

Grover's Algorithm in Q#

DZone 's Guide to

Grover's Algorithm in Q#

In this article, we discuss how to implement Grover's Algorithm in Q# better understand how searching works in unstructured databases.

· Web Dev Zone ·
Free Resource

Grover’s Algorithm is related to searching an unstructured database with entries. Classical algorithms for searching n entries will be O(n) queries. The Grover's algorithm (Quantum Algorithm ) requires only the order of square root of n. Bohmian mechanics based nonlocal hidden quantum computer can perform the search in the order of the cube root of n queries.

The algorithm is implemented in Q#. Q# is Microsoft's quantum computing language. The driver's class is written in C#. A Q# project and solution are created in Visual Studio Code. Visual  Studio Code is used to open the project. The project will have two files, Driver.cs (C# driver class) and QuantumCode.qs (Q# ). The Operations.qs is renamed as QuantumCode.qs.

The code snippet below shows QuantumCode.qs after adding the operation SetValue and StateValueTest.

You may also like: The Data Structures and Algorithms Learning Problem.

Let us look at QuantumCode.qs.

Q




x
269


 
1
namespace GroverAlgo
2
 
          
3
{
4
    open Microsoft.Quantum.Primitive;
5
    open Microsoft.Quantum.Canon;
6
 
          
7
    // GetDataFromInts Operation 
8
    /// # Summary
9
    /// Database oracle `D` constructed from classical database.
10
    /// 
11
 
          
12
    /// # Parameters
13
    /// ## markedElements
14
    /// Indices to marked elements in database.
15
    /// ## markedQubit
16
 
          
17
    /// Qubit that indicated whether database element is marked.
18
    /// ## databaseRegister
19
    /// A register of n qubits initially in the |00…0〉 state.
20
    /// 
21
 
          
22
    operation GetDataFromInts(markedElements : Int[],  markedQubit: Qubit, databaseRegister: Qubit[]) : Unit
23
    {
24
        body(...) {
25
            let nMarked = Length(markedElements);
26
            for (idxMarked in 0..nMarked - 1) {
27
                // Note: As X accepts a Qubit, and ControlledOnInt only 
28
                // accepts Qubit[], we use ApplyToEachCA(X, _) which accepts 
29
                // Qubit[] even though the target is only 1 Qubit.
30
                (ControlledOnInt(markedElements[idxMarked], ApplyToEachCA(X, _)))(databaseRegister, [markedQubit]);
31
 
          
32
            }
33
 
          
34
        }    
35
 
          
36
        adjoint auto;
37
        controlled auto;
38
        adjoint controlled auto;
39
    }
40
 
          
41
    // SetupGroverStateOracle Operation
42
    /// # Summary
43
    /// Preparation of start state from database oracle and oracle `U` that 
44
    /// creates a uniform superposition over database indices.
45
    /// 
46
 
          
47
    /// # Parameters
48
    /// ## markedElements
49
    /// Indices to marked elements in database.
50
    /// ## idxMarkedQubit
51
 
          
52
    /// Index to `MarkedQubit`.
53
    /// ## startQubits
54
    /// The collection of the n+1 qubits `MarkedQubit` and `databaseRegister`
55
    /// initially in the |00…0〉 state.
56
    /// 
57
 
          
58
    operation SetupGroverStateOracleImpl(markedElements : Int[], idxMarkedQubit: Int , startQubits: Qubit[]) : Unit
59
 
          
60
    {
61
        body(...) {
62
            let flagQubit = startQubits[idxMarkedQubit];
63
            let databaseRegister = Exclude([idxMarkedQubit], startQubits);
64
 
          
65
            ApplyToEachCA(H, databaseRegister);      
66
            GetDataFromInts(markedElements, flagQubit, databaseRegister);
67
             }
68
 
          
69
        adjoint auto;
70
        controlled auto;
71
        adjoint controlled auto;
72
    }
73
 
          
74
    /// # Summary
75
    /// `StateOracle` type for the preparation of a start state that has a 
76
    /// marked qubit entangled with some desired state in the database 
77
    /// register.
78
    ///
79
 
          
80
    /// # Parameters
81
    /// ## markedElements
82
    /// Indices to marked elements in database.
83
    ///
84
 
          
85
    /// # Returns
86
    /// A `StateOracle` type with signature 
87
    /// ((Int, Qubit[]) => (): Adjoint, Controlled).
88
 
          
89
    function SetupGroverStateOracle(markedElements : Int[]) : StateOracle
90
 
          
91
    {
92
        return StateOracle(SetupGroverStateOracleImpl(markedElements, _, _));
93
 
          
94
    }
95
 
          
96
    // Execute Search function
97
    /// # Summary
98
    /// Grover's search algorithm using library functions.
99
    ///
100
    /// # Parameters
101
    /// ## markedElements
102
    /// Indices to marked elements in database.
103
    /// ## nIterations
104
    /// Number of iterations of the Grover iteration to apply.
105
    /// ## idxMarkedQubit
106
    /// Index to `MarkedQubit`.
107
    ///
108
 
          
109
    /// # Returns
110
    /// Unitary implementing Grover's search algorithm.
111
    ///
112
 
          
113
    function ExecuteSearch( markedElements: Int[], nIterations: Int, idxMarkedQubit: Int) : (Qubit[] => Unit : Adjoint, Controlled)
114
 
          
115
    {
116
        return AmpAmpByOracle(nIterations, SetupGroverStateOracle(markedElements), idxMarkedQubit);
117
    }
118
 
          
119
 
          
120
    // ExecuteGroversAlgorithm Operation
121
    /// # Summary
122
    /// Performs quantum search for the marked elements and returns an index
123
    /// to the found element in integer format. 
124
    ///
125
 
          
126
    /// # Parameters
127
    /// ## markedElements
128
    /// Indices to marked elements in database.
129
    /// ## nIterations
130
    /// Number of applications of the Grover iterate (RS · RM).
131
    /// ## nDatabaseQubits
132
    /// Number of qubits in the database register. 
133
    ///
134
 
          
135
    /// # Returns
136
    /// Measurement outcome of marked Qubit and measurement outcomes of 
137
    /// the database register converted to an integer.
138
 
          
139
    operation ExecuteGroversAlgorithm( markedElements: Int[], nIterations : Int, nDatabaseQubits : Int) : (Result,Int) {
140
 
          
141
        body(...){            
142
            mutable resultSuccess = Zero;
143
            mutable numberElement = 0;            
144
 
          
145
            using (qubits = Qubit[nDatabaseQubits+1]) {                       
146
                let markedQubit = qubits[0];                
147
                let databaseRegister = qubits[1..nDatabaseQubits];  
148
 
          
149
                (ExecuteSearch( markedElements, nIterations, 0))(qubits);                
150
                set resultSuccess = M(markedQubit);
151
                               let resultElement = MultiM(databaseRegister);
152
                set numberElement = PositiveIntFromResultArr(resultElement);
153
                               ResetAll(qubits);
154
            }
155
 
          
156
            return (resultSuccess, numberElement);
157
        }
158
    }
158
    }
159
}



Let us look at Driver class in C#.

C#
xxxxxxxxxx
1
95
 
1
/////////////////////////////////////////////////////////////////////
2
 
          
3
// This file contains the driver class.
4
 
          
5
//////////////////////////////////////////////////////////////////////
6
 
          
7
using System;
8
using Microsoft.Quantum.Simulation.Core;
9
using Microsoft.Quantum.Simulation.Simulators;
10
 
          
11
namespace GroverAlgo
12
{
13
    class Driver
14
    {
15
        static void Main(string[] args)
16
        {
17
            int successfulCnt = ExecuteSearchAlgorithm(100,20);
18
 
          
19
            successfulCnt = ExecuteSearchAlgorithm(100, 3);
20
            successfulCnt = ExecuteSearchAlgorithm(100, 2);
21
 
          
22
            successfulCnt = ExecuteSearchAlgorithm(100, 1);
23
            successfulCnt = ExecuteSearchAlgorithm(100, 0);
24
        }
25
 
          
26
        static int ExecuteSearchAlgorithm(int repeats, int groverIterations)
27
        {
28
            int successfulCount = 0;
29
 
          
30
            using (var sim = new QuantumSimulator(throwOnReleasingQubitsNotInZeroState: true))
31
            {
32
                int nDatabaseQubits = 8;
33
 
          
34
                var databaseSize = Math.Pow(2.0, nDatabaseQubits);
35
                QArray<long> markedElements = new QArray<long>() {23};
36
 
          
37
                int nIterations = groverIterations;
38
 
          
39
                for (int i = 0; i < repeats; ++i)
40
                {                      
41
                    var task = ExecuteGroversAlgorithm.Run(sim,                markedElements, nIterations, nDatabaseQubits);
42
 
          
43
                    var result = task.Result;
44
 
          
45
                    if (result.Item1 == Result.One)
46
                    {
47
                        successfulCount++;
48
                    }
49
                }
50
            }
51
 
          
52
            Console.WriteLine(
53
                $"Grover-Iterations {groverIterations}: {successfulCount} of {repeats} had the desired result.");
54
 
          
55
            return successfulCount;
56
 
          
57
        }
58
    }
59
}


In the Visual Studio, the code is executed to search the item 23.

Amplitude amplification algorithms are techniques that allow the amplification of a quantum state subspace. These algorithms are a generalization of Grover’s algorithm. Quantum counting is another amplification algorithm used for solving search problems.


Further Reading

Topics:
quantum computing

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}