forked from microsoft/QuantumKatas
-
Notifications
You must be signed in to change notification settings - Fork 0
/
ReferenceImplementation.qs
224 lines (175 loc) · 7.24 KB
/
ReferenceImplementation.qs
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
// 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.
//////////////////////////////////////////////////////////////////////
namespace Quantum.Kata.UnitaryPatterns {
open Microsoft.Quantum.Arrays;
open Microsoft.Quantum.Intrinsic;
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Convert;
// Task 1. Main diagonal
operation MainDiagonal_Reference (qs : Qubit[]) : Unit {}
// Task 2. All-non-zero matrix
operation AllNonZero_Reference (qs : Qubit[]) : Unit {
ApplyToEach(H, qs);
}
// Task 3. Block diagonal matrix
operation BlockDiagonal_Reference (qs : Qubit[]) : Unit {
H(Head(qs));
}
// Task 4. Quarters
operation Quarters_Reference (qs : Qubit[]) : Unit {
ApplyToEach(H, Most(qs));
}
// Task 5. Even chessboard pattern
operation EvenChessPattern_Reference (qs : Qubit[]) : Unit {
ApplyToEach(H, Rest(qs));
}
// Task 6. Odd chessboard pattern
operation OddChessPattern_Reference (qs : Qubit[]) : Unit {
ApplyToEach(H, Rest(qs));
X(Head(qs));
}
// Task 7. Anti-diagonal
operation Antidiagonal_Reference (qs : Qubit[]) : Unit {
ApplyToEach(X, qs);
}
// Task 8. 2⨯2 chessboard pattern
operation ChessPattern2x2_Reference (qs : Qubit[]) : Unit {
H(Head(qs));
for (i in 2 .. Length(qs) - 1) {
H(qs[i]);
}
}
// Task 9. Two patterns
operation TwoPatterns_Reference (qs : Qubit[]) : Unit {
// bottom right quarter is obtained by applying Controlled AllNonZero
ApplyToEach(Controlled H([Tail(qs)], _), Most(qs));
// top left quarter is obtained by applying 0-controlled Antidiagonal
ApplyToEach((ControlledOnInt(0, X))([Tail(qs)], _), Most(qs));
}
// Task 10. Increasing blocks
operation IncreasingBlocks_Reference (qs : Qubit[]) : Unit is Adj + Ctl {
let N = Length(qs);
// for N = 1, we need an identity
if (N > 1) {
// do the bottom-right quarter
ApplyToEachCA(Controlled H([Tail(qs)], _), Most(qs));
// do the top-left quarter by calling the same operation recursively
(ControlledOnInt(0, IncreasingBlocks_Reference))([Tail(qs)], Most(qs));
}
}
// Task 11. X-Wing fighter
operation XWing_Fighter_Reference (qs : Qubit[]) : Unit {
ApplyToEach(CNOT(qs[0], _), qs[1...]);
H(qs[0]);
ApplyToEach(CNOT(qs[0], _), qs[1...]);
}
// Task 12. Rhombus
operation Rhombus_Reference (qs : Qubit[]) : Unit {
XWing_Fighter_Reference(qs);
X(Tail(qs));
}
// Task 13. TIE fighter
// Helper operation: decrement a little-endian register
operation Decrement (qs : Qubit[]) : Unit {
X(qs[0]);
for (i in 1..Length(qs)-1) {
Controlled X(qs[...i-1], qs[i]);
}
}
// Helper operation: antidiagonal
operation Reflect (qs : Qubit[]) : Unit is Adj + Ctl {
ApplyToEachCA(X, qs);
}
// Main operation for Task 13
operation TIE_Fighter_Reference (qs : Qubit[]) : Unit {
let n = Length(qs);
(ControlledOnInt(0, Reflect))([qs[n-1]], qs[...(n-2)]);
Decrement(qs[...(n-2)]);
H(qs[n-1]);
Controlled Reflect([qs[n-1]], qs[...(n-2)]);
}
// Task 14. Creeper
operation Creeper_Reference (qs : Qubit[]) : Unit {
// We observe that a Hadamard transform on 2 qubits already produces the block structure that is
// required for the 4 "corners" of the unitary matrix. The rest of the pattern is a suitable
// permutation of a additional block, where this block contains the Hadamard transform on 1 qubit.
// The permutation producing the corners can be constructed from a CNOT from middle qubit to most
// significant qubit. The permutation producing the pattern in the center can be produced by
// applying a cyclic shift of the quantum register. This can be accomplished using a CNOT and a CCNOT.
CNOT(qs[1], qs[2]);
CNOT(qs[2], qs[0]);
CCNOT(qs[0], qs[2], qs[1]);
(ControlledOnInt(0, H))([qs[2]], qs[1]);
H(qs[0]);
CNOT(qs[1], qs[2]);
}
// Task 15. Hessenberg matrices
// Helper function for Embedding_Perm: finds first location where bit strings differ.
function FirstDiff (bits1 : Bool[], bits2 : Bool[]) : Int {
for (i in 0 .. Length(bits1)-1) {
if (bits1[i] != bits2[i]) {
return i;
}
}
return -1;
}
// Helper function for Embed_2x2_Operator: performs a Clifford to implement a base change
// that maps basis states index1 to 111...10 and index2 to 111...11 (in big endian notation, i.e., LSB in qs[n-1])
operation Embedding_Perm (index1 : Int, index2 : Int, qs : Qubit[]) : Unit is Adj {
let n = Length(qs);
let bits1 = IntAsBoolArray(index1, n);
let bits2 = IntAsBoolArray(index2, n);
// find the index of the first bit at which the bit strings are different
let diff = FirstDiff(bits1, bits2);
// we care only about 2 inputs: basis state of bits1 and bits2
// make sure that the state corresponding to bits1 has qs[diff] set to |0⟩
if (bits1[diff]) {
X(qs[diff]);
}
// iterate through the bit strings again, setting the final state of qubits
for (i in 0..n-1) {
if (bits1[i] == bits2[i]) {
// if two bits are the same, set both to 1 using X or nothing
if (not bits1[i]) {
X(qs[i]);
}
} else {
// if two bits are different, set both to 1 using CNOT
if (i > diff) {
if (not bits1[i]) {
(ControlledOnInt(0,X))([qs[diff]], qs[i]);
}
if (not bits2[i]) {
CNOT(qs[diff], qs[i]);
}
}
}
}
// move the differing bit to the last qubit
if (diff < n-1) {
SWAP(qs[n-1], qs[diff]);
}
}
// Helper function: apply the 2⨯2 unitary operator at the sub-matrix given by indices for 2 rows/columns
operation Embed_2x2_Operator (U : (Qubit => Unit is Ctl), index1 : Int, index2 : Int, qs : Qubit[]) : Unit {
within {
Embedding_Perm(index1, index2, qs);
}
apply {
Controlled U(Most(qs), Tail(qs));
}
}
// Putting everything together: the target pattern is produced by a sequence of controlled H gates.
operation Hessenberg_Matrix_Reference (qs : Qubit[]) : Unit {
let n = Length(qs);
for (i in 2^n - 2 .. -1 .. 0) {
Embed_2x2_Operator(H, i, i+1, qs);
}
}
}