QuantumKatas/GroversAlgorithm/ReferenceImplementation.qs at main · microsoft/QuantumKatas · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT license.

//////////////////////////////////////////////////////////////////////
// This file contains reference solutions to all tasks.
// The tasks themselves can be found in Tasks.qs file.
// We recommend that you try to solve the tasks yourself first,
// but feel free to look up the solution if you get stuck.
//////////////////////////////////////////////////////////////////////

namespaceQuantum.Kata.GroversAlgorithm {

openMicrosoft.Quantum.Arrays;
openMicrosoft.Quantum.Intrinsic;
openMicrosoft.Quantum.Canon;
openMicrosoft.Quantum.Math;


//////////////////////////////////////////////////////////////////
// Part I. Oracles for Grover's Search
//////////////////////////////////////////////////////////////////

// Task 1.1. The |11...1⟩ oracle
operationOracle_AllOnes_Reference (queryRegister : Qubit[], target : Qubit) : UnitisAdj {
ControlledX(queryRegister, target);
 }


// Task 1.2. The |1010...⟩ oracle
operationOracle_AlternatingBits_Reference (queryRegister : Qubit[], target : Qubit) : Unit
isAdj {

within {
// flip the bits in odd (0-based positions),
// so that the condition for flipping the state of the target qubit is "query register is in 1...1 state"
foriin1..2..Length(queryRegister) -1 {
X(queryRegister[i]);
 }
 }
apply {
ControlledX(queryRegister, target);
 }
 }


// Task 1.3. Arbitrary bit pattern oracle
operationOracle_ArbitraryPattern_Reference (queryRegister : Qubit[], target : Qubit, pattern : Bool[]) : UnitisAdj {
 (ControlledOnBitString(pattern, X))(queryRegister, target);
 }


// Task 1.4*. Oracle converter
operationOracleConverterImpl_Reference (markingOracle : ((Qubit[], Qubit) =>UnitisAdj), register : Qubit[]) : UnitisAdj {
usetarget=Qubit();
within {
// Put the target into the |-⟩ state
X(target);
H(target);
 } apply {
// Apply the marking oracle; since the target is in the |-⟩ state,
// flipping the target if the register satisfies the oracle condition will apply a -1 factor to the state
// (phase kickback trick)
markingOracle(register, target);
 }
 }


functionOracleConverter_Reference (markingOracle : ((Qubit[], Qubit) =>UnitisAdj)) : (Qubit[] =>UnitisAdj) {
returnOracleConverterImpl_Reference(markingOracle, _);
 }


//////////////////////////////////////////////////////////////////
// Part II. The Grover iteration
//////////////////////////////////////////////////////////////////

// Task 2.1. The Hadamard transform
operationHadamardTransform_Reference (register : Qubit[]) : UnitisAdj {

ApplyToEachA(H, register);

// ApplyToEach is a library routine that is equivalent to the following code:
// for (qubit in register) {
// H(qubit);
// }
 }


// Task 2.2. Conditional phase flip
operationConditionalPhaseFlip_Reference (register : Qubit[]) : UnitisAdj {
// Define a marking oracle which detects an all zero state
letallZerosOracle=Oracle_ArbitraryPattern_Reference(_, _, [false, size=Length(register)]);

// Convert it into a phase-flip oracle and apply it
letflipOracle=OracleConverter_Reference(allZerosOracle);
flipOracle(register);

// To fix the global phase difference, use the following line :
R(PauliI, 2.0*PI(), register[0]); // Note : We used 2*PI to add a global phase of PI, as R operation rotates qubit by 𝜃/2
// For more details refer to the following Quantum SE question : https://quantumcomputing.stackexchange.com/questions/5973/counting-in-q-number-of-solutions/6446#6446
 }


operationPhaseFlip_ControlledZ (register : Qubit[]) : UnitisAdj {
// Alternative solution, described at https://quantumcomputing.stackexchange.com/questions/4268/how-to-construct-the-inversion-about-the-mean-operator/4269#4269
within {
ApplyToEachA(X, register);
 } apply {
ControlledZ(Most(register), Tail(register));
 }
// To fix the global phase difference, use the following line :
R(PauliI, 2.0*PI(), register[0]); // Note : We used 2*PI to add a global phase of PI, as R operation rotates qubit by 𝜃/2
// For more details refer to the following Quantum SE question : https://quantumcomputing.stackexchange.com/questions/5973/counting-in-q-number-of-solutions/6446#6446
 }


// Task 2.3. The Grover iteration
operationGroverIteration_Reference (register : Qubit[], oracle : (Qubit[] =>UnitisAdj)) : UnitisAdj {
oracle(register);
within {
HadamardTransform_Reference(register);
 } apply {
ConditionalPhaseFlip_Reference(register);
 }
 }


//////////////////////////////////////////////////////////////////
// Part III. Putting it all together: Grover's search algorithm
//////////////////////////////////////////////////////////////////

// Task 3.1. Grover's search
operationGroversSearch_Reference (register : Qubit[], oracle : ((Qubit[], Qubit) =>UnitisAdj), iterations : Int) : UnitisAdj {

letphaseOracle=OracleConverter_Reference(oracle);
HadamardTransform_Reference(register);

foriin1..iterations {
GroverIteration_Reference(register, phaseOracle);
 }
 }

}