{{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

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

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.

Topics:
quantum computing

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Opinions expressed by DZone contributors are their own.