1357.md (24215B)
1 Source: https://codeforces.com/blog/entry/79208 2 3 The contest is over; I hope you enjoyed it and learned something new in the process! 4 5 Here are the solution descriptions. You should also be able to see the solutions of the contest participants, and the discussions in the comments offer a lot of insight. 6 7 ## A: "Distinguishing Unitaries" problems 8 9 ### [1357A1 - Figure out direction of CNOT](/contest/1357/problem/A1 "Microsoft Q Coding Contest - Summer 2020") 10 11 Let's consider the effect of these gates on the 2-qubit basis states, similar to how we did in [1356A5 - Distinguish Z from -Z](/contest/1356/problem/A5 "Microsoft Q Coding Contest - Summer 2020 - Warmup"). We'll see that applying $\text{CNOT}_{12}$ and $\text{CNOT}_{21}$ to any of the basis states other than $|00\rangle$ yields different results. For example, $\text{CNOT}_{12} |01\rangle = |01\rangle$ and $\text{CNOT}_{21} |01\rangle = |11\rangle$. Thus, the easiest solution is: prepare two qubits in the $|01\rangle$ state and apply the unitary to them, then measure the second qubit; if it is still One, the gate is $\text{CNOT}_{12}$, otherwise it's $\text{CNOT}_{21}$. 12 13 ``` 14 operation Solve (unitary : (Qubit[] => Unit is Adj+Ctl)) : Int { 15 // apply to |01⟩ and measure 1st qubit: CNOT₁₂ will do nothing, CNOT₂₁ will change to |11⟩ 16 using (qs = Qubit[2]) { 17 within { X(qs[1]); } 18 apply { unitary(qs); } 19 return MResetZ(qs[0]) == Zero ? 0 | 1; 20 } 21 } 22 ``` 23 24 ### [1357A2 - Distinguish I, CNOTs and SWAP](/contest/1357/problem/A2 "Microsoft Q Coding Contest - Summer 2020") 25 26 In this problem we are allowed to use the given unitary twice, so we can split our decision-making process in two phases: 27 28 1. Apply the unitary to the $|11\rangle$ state; $\text{CNOT}_{12}$ will yield the $|10\rangle$ state, $\text{CNOT}_{21}$ — $|01\rangle$, and both I and SWAP gates will leave the state unchanged. 29 2. Now to distinguish I from SWAP, we can use the $|01\rangle$ state: I gate will leave it unchanged while SWAP will yield $|10\rangle$. 30 31 ``` 32 operation Solve (unitary : (Qubit[] => Unit is Adj+Ctl)) : Int { 33 // first run: apply to |11⟩; CNOT₁₂ will give |10⟩, CNOT₂₁ will give |01⟩, II and SWAP will remain |11⟩ 34 using (qs = Qubit[2]) { 35 X(qs[0]); 36 X(qs[1]); 37 unitary(qs); 38 let ind = MeasureInteger(LittleEndian(qs)); 39 if (ind == 1 or ind == 2) { 40 // respective CNOT 41 return ind; 42 } 43 } 44 // second run: distinguish II from SWAP, apply to |01⟩: II will remain |01⟩, SWAP will become |10⟩ 45 using (qs = Qubit[2]) { 46 X(qs[1]); 47 unitary(qs); 48 let ind = MeasureInteger(LittleEndian(qs)); 49 return ind == 1 ? 3 | 0; 50 } 51 } 52 ``` 53 54 ### [1357A3 - Distinguish H from X](/contest/1357/problem/A3 "Microsoft Q Coding Contest - Summer 2020") 55 56 In this problem again we are allowed to apply the unitary twice. The solution relied on the well-known identity HXH = Z (i.e., Hadamard gate can be used to convert X to Z and vice versa). Applying a sequence of gates "unitary — X — unitary" will be equivalent to XXX = X gate if the unitary was X, and to HXH = Z if the unitary was H. With this observation we need to distinguish X from Z, which can be done using the $|0\rangle$ state: 57 58 ``` 59 operation DistinguishHfromX_Reference (unitary : (Qubit => Unit is Adj+Ctl)) : Int { 60 // apply operation unitary - X - unitary to |0⟩ state and measure: |0⟩ means H, |1⟩ means X 61 // X will end up as XXX = X, H will end up as HXH = Z (does not change |0⟩ state) 62 using (q = Qubit()) { 63 within { 64 unitary(q); 65 } apply { 66 X(q); 67 } 68 return MResetZ(q) == Zero ? 0 | 1; 69 } 70 } 71 ``` 72 73 ### [1357A4 - Distinguish Rz from R1](/contest/1357/problem/A4 "Microsoft Q Coding Contest - Summer 2020") 74 75 As a reminder, 76 77 $Rz(\theta) = \begin{bmatrix} e^{-i\theta/2} & 0 \\ 0 & e^{i\theta/2} \end{bmatrix} \\ R1(\theta) = \begin{bmatrix} 1 & 0 \\ 0 & e^{i\theta} \end{bmatrix} = e^{i\theta/2} Rz(\theta)$ 78 79 We see that these two gates differ by a global phase $e^{i\theta/2}$. In this problem we're free to choose the angle parameter which we'll pass to our gate, so we can choose an angle that make this global phase difference something nice: for $\theta = 2\pi$, $e^{i\theta/2} = -1$, $Rz(\theta) = -I$, and $R1(\theta) = I$. 80 81 With this choice of $\theta$, the solution becomes very similar to [1356A5 - Distinguish Z from -Z](/contest/1356/problem/A5 "Microsoft Q Coding Contest - Summer 2020 - Warmup"). 82 83 ``` 84 operation Solve (unitary : ((Double, Qubit) => Unit is Adj+Ctl)) : Int { 85 using (qs = Qubit[2]) { 86 within { 87 H(qs[0]); 88 } apply { 89 Controlled unitary(qs[0..0], (2.0 * PI(), qs[1])); 90 } 91 return MResetZ(qs[0]) == Zero ? 1 | 0; 92 } 93 } 94 ``` 95 96 ### [1357A5 - Distinguish Rz(θ) from Ry(θ)](/contest/1357/problem/A5 "Microsoft Q Coding Contest - Summer 2020") 97 98 As a reminder, 99 100 $Rz(\theta) = \begin{bmatrix} e^{-i\theta/2} & 0 \\ 0 & e^{i\theta/2} \end{bmatrix} \\ Ry(\theta) = \begin{bmatrix} \cos\frac{\theta}{2} & -\sin\frac{\theta}{2} \\ \sin\frac{\theta}{2} & \cos\frac{\theta}{2} \end{bmatrix}$ 101 102 The key observation here is that Rz is a diagonal matrix and Ry is not, so when applied to the $|0\rangle$ state, the former will leave it unchanged (with an extra phase which is not observable), and the latter will convert it to a superposition $\cos\frac{\theta}{2} |0\rangle + \sin\frac{\theta}{2} |1\rangle$. The trick is how to distinguish those two states if they are not orthogonal (and for most values of $\theta$ they will not be)? 103 104 The statement gave you a big hint on this: it allowed you to use the given unitary unlimited number of times, which pointed to a probabilistic solution (as opposed to deterministic solutions in all previous A problems). Apply the unitary to the $|0\rangle$ state and measure the result; if it is $|1\rangle$, the unitary has to be Ry, otherwise you can repeat the experiment again. After several iterations of measuring $|0\rangle$ you can conclude that with high probability the unitary is Rz. 105 106 To reduce the number of iterations after which you make the decision, you could apply the unitary several times to bring the overall rotation angle closer to $\pi$: in case of Ry gate this would allow you to rotate the state closer to the $|1\rangle$ state, so that you'd detect it with higher probability. 107 108 See [vilim_l](/profile/vilim_l "Candidate Master vilim_l")'s [solution](https://codeforces.com/contest/1357/submission/84346001) for a neat implementation. 109 110 ### [1357A6 - Distinguish four Pauli gates](/contest/1357/problem/A6 "Microsoft Q Coding Contest - Summer 2020") 111 112 At the first glance it might seem impossible to distinguish 4 different unitaries with just one unitary application. However, since the unitaries were chosen carefully (and you're allowed to do unlimited measurements), it is possible. The solution uses the [Bell states](https://en.wikipedia.org/wiki/Bell_state#Bell_basis): the 4 orthogonal states which you can prepare starting with the first of them $\frac{1}{\sqrt2}(|00\rangle + |11\rangle)$ by applying gates I, X, Z and Y, respectively, to the first qubit. Thus the solution becomes: prepare the $\frac{1}{\sqrt2}(|00\rangle + |11\rangle)$ state, apply the unitary and measure the resulting state in Bell basis to figure out which of the Bell states it is ([1001E - Distinguish Bell states](/contest/1001/problem/E "Microsoft Q Coding Contest - Summer 2018 - Warmup")). 113 114 ``` 115 operation Solve(unitary : (Qubit => Unit is Adj+Ctl)) : Int { 116 // apply operation to the 1st qubit of a Bell state and measure in Bell basis 117 using (qs = Qubit[2]) { 118 H(qs[0]); 119 CNOT(qs[0], qs[1]); 120 121 unitary(qs[0]); 122 123 CNOT(qs[0], qs[1]); 124 H(qs[0]); 125 126 // after this I -> 00, X -> 01, Y -> 11, Z -> 10 127 let ind = MeasureInteger(LittleEndian(qs)); 128 let returnValues = [0, 3, 1, 2]; 129 return returnValues[ind]; 130 } 131 } 132 ``` 133 134 ### [1357A7 - Distinguish Y, XZ, -Y and -XZ](/contest/1357/problem/A7 "Microsoft Q Coding Contest - Summer 2020") 135 136 In this problem we needed to distinguish 4 gates that were identical up to a global phase, i.e., gates $Y$, $iY$, $-Y$ and $-iY$. It is possible to do this "by hand", i.e., first applying the unitary twice and checking whether the result is $I$ (which allows us to distinguish $\pm Y$ and $\pm iY$, since the first two gates squared will be equivalent to the $I$ gate, and the last two — to the $-I$ gate), and then distinguishing the gates in each group. 137 138 The reference solution took advantage of [phase estimation](https://en.wikipedia.org/wiki/Quantum_phase_estimation_algorithm) algorithm which, given a unitary and its eigenstate, allows to find its eigenvalue. If we prepare an eigenstate of the Y gate $\frac{1}{\sqrt2}(|0\rangle + i|1\rangle)$, it will be the eigenstate of all other gates as well, with eigenphases $0, \pi/2, \pi, 3\pi/2$, respectively. You can convert the output of the phase estimation procedure into the return index directly. 139 140 You can learn more about phase estimation in [this kata](https://github.com/microsoft/QuantumKatas/tree/master/PhaseEstimation). 141 142 ``` 143 operation DistinguishYfromXZWithPhases_Reference (unitary : (Qubit => Unit is Adj+Ctl)) : Int { 144 // Run phase estimation on the unitary and the +1 eigenstate of the Y gate |0⟩ + i|1⟩ 145 146 // Construct a phase estimation oracle from the unitary 147 let oracle = DiscreteOracle(Oracle_Reference(unitary, _, _)); 148 149 // Allocate qubits to hold the eigenstate of U and the phase in a big endian register 150 mutable phaseInt = 0; 151 using ((eigenstate, phaseRegister) = (Qubit[1], Qubit[2])) { 152 let phaseRegisterBE = BigEndian(phaseRegister); 153 // Prepare the eigenstate of U 154 H(eigenstate[0]); 155 S(eigenstate[0]); 156 // Call library 157 QuantumPhaseEstimation(oracle, eigenstate, phaseRegisterBE); 158 // Read out the phase 159 set phaseInt = MeasureInteger(BigEndianAsLittleEndian(phaseRegisterBE)); 160 161 ResetAll(eigenstate); 162 ResetAll(phaseRegister); 163 } 164 165 // Convert the measured phase into return value 166 return phaseInt; 167 } 168 ``` 169 170 ## B: Reversible computing 171 172 ### [1357B1 - "Is the bit string balanced?" oracle](/contest/1357/problem/B1 "Microsoft Q Coding Contest - Summer 2020") 173 174 Classically this problem would've been quite straightforward: count the number of 1s in the bit string and check that this number equals half of the bit string length. In quantum computing, you do exactly the same, but in a reversible manner. 175 176 * We already know how to increment a number written in a quantum register from [1356B1 - Increment](/contest/1356/problem/B1 "Microsoft Q Coding Contest - Summer 2020 - Warmup") — here we'll assume that we've already implemented this operation as `Increment`. 177 * To count the number of 1s in the input register, you increment the counter for each element of the input register that is 1 using a controlled variant of the increment operation. 178 * To flip the output qubit if the number written in the counter register equals some classical constant, you use [ControlledOnInt](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.canon.controlledonint) function that will apply the X gate to the output only if the control register is in the state that corresponds to that constant. 179 * You have to remember to uncompute the counter register before releasing the qubits — within ... apply construct is useful to express the uncomputation step automatically. 180 181 ``` 182 operation Solve(inputs : Qubit[], output : Qubit) : Unit is Adj+Ctl { 183 let log = BitSizeI(Length(inputs)); 184 using (inc = Qubit[log]) { 185 within { 186 for (q in inputs) { 187 (Controlled Increment)([q], LittleEndian(inc)); 188 } 189 } apply { 190 (ControlledOnInt(Length(inputs) / 2, X))(inc, output); 191 } 192 } 193 } 194 ``` 195 196 ### [1357B2 - "Is the number divisible by 3?" oracle](/contest/1357/problem/B2 "Microsoft Q Coding Contest - Summer 2020") 197 198 This problem required you to come up with a way to perform increment and decrement modulo 3 reversibly. You can do that by allocating two extra counter qubits and figuring out the rules of updating them in a way which allows to go from $|00\rangle$ to $|10\rangle$ to $|01\rangle$ to $|00\rangle$ upon increment (and you can use adjoint of increment as decrement). (This has been the main part of [1116C3 - ``Is the number of ones divisible by 3?'' oracle](/contest/1116/problem/C3 "Microsoft Q Coding Contest - Winter 2019") in Winter 2019 contest). 199 200 This time you need an extra trick: instead of just counting the number of 1 bits modulo 3, you need to calculate the remainder of dividing the number by 3. You can use the fact that consecutive powers of 2 give remainders $1$ and $-1$ in turn: $2^0 \equiv 1$, $2^1 = 2 \equiv -1$, $2^2 = 4 \equiv 1$, $2^3 = 8 \equiv -1$, and so on. You start iterating from the least significant bit of the number, performing controlled increment of the counter qubits with qubits 0, 2, 4, ... as controls, and controlled decrement with qubits 1, 3, 5, ... as controls. 201 202 Finally, the number itself will be divisible by 3 only if the counter qubits are in the $|00\rangle$ state. 203 204 ``` 205 operation IncrementMod3 (counterRegister : Qubit[]) : Unit is Adj+Ctl { 206 let sum = counterRegister[0]; 207 let carry = counterRegister[1]; 208 // we need to implement +1 mod 3: 209 // sum carry | sum carry 210 // 0 0 | 1 0 211 // 1 0 | 0 1 212 // 0 1 | 0 0 213 // compute sum bit 214 (ControlledOnInt(0, X))([carry], sum); 215 // sum carry | carry 216 // 1 0 | 0 217 // 0 0 | 1 218 // 0 1 | 0 219 (ControlledOnInt(0, X))([sum], carry); 220 } 221 222 operation Task4_TestMod3_Reference(register : Qubit[], output : Qubit) : Unit is Adj+Ctl { 223 using (counter = Qubit[2]) { 224 within { 225 for (i in 0 .. Length(register) - 1) { // starting from LSB 226 if (i % 2 == 0) { 227 // i-th power of 2 is 1 mod 3 228 Controlled IncrementMod3([register[i]], counter); 229 } else { 230 // i-th power of 2 is 2 mod 3 - same as -1, which is Adjoint of +1 231 Controlled Adjoint IncrementMod3([register[i]], counter); 232 } 233 } 234 } apply { 235 // divisible by 3 only if the result is divisible by 3 236 (ControlledOnInt(0, X))(counter, output); 237 } 238 239 } 240 } 241 ``` 242 243 ## C: State preparation without arbitrary rotations 244 245 ### [1357C1 - Prepare superposition of basis states with 0s](/contest/1357/problem/C1 "Microsoft Q Coding Contest - Summer 2020") 246 247 This task is extremely similar to [1356C - Prepare state |01⟩ + |10⟩ + |11⟩](/contest/1356/problem/C "Microsoft Q Coding Contest - Summer 2020 - Warmup") and to [task 2.3 of the Superposition kata](https://github.com/microsoft/QuantumKatas/blob/master/Superposition/Tasks.qs#L228): you need to prepare an equal superposition of all basis states except one, the $|1...1\rangle$ state. The solution is also similar to [this one](https://github.com/microsoft/QuantumKatas/blob/master/Superposition/Workbook_Superposition_Part2.ipynb): prepare an equal superposition of all basis states (by applying an H gate to each qubit), allocate an extra qubit, apply a controlled X gate with the input qubits as controls and the extra qubit as a target, and measure the extra qubit: if it is measured in the 0 state, the rest of the qubits are in the necessary superposition, otherwise we have to retry. 248 249 ``` 250 operation Solve(qs : Qubit[]) : Unit { 251 using (ancilla = Qubit()) { 252 repeat { 253 // Create equal superposition of all basis states 254 ApplyToEach(H, qs); 255 // Create (our state) ⊗ |0⟩ + |11...11⟩ ⊗ |1⟩ 256 Controlled X(qs, ancilla); 257 let res = MResetZ(ancilla); 258 } 259 until (res == Zero) 260 fixup { 261 ApplyToEach(X, qs); 262 } 263 } 264 } 265 ``` 266 267 ### [1357C2 - Prepare superposition of basis states with the same parity](/contest/1357/problem/C2 "Microsoft Q Coding Contest - Summer 2020") 268 269 This problem can be treated as another post-selection state preparation task. Same as before, we start by preparing an equal superposition of all basis states and allocating an extra qubit. This time we use the extra qubit to calculate the parity of the input state: applying a series of CNOT gates, each one with one of the input qubits as control and the extra qubit as a target, will compute the parity of the state. Now we measure the extra qubit: if the measurement result matches our parity, we're done — the input qubits collapsed to an equal superposition of all states that have this parity. If the measurement result is the opposite, we can retry the whole process, like we did in the previous problems, if we're happy with a randomized solution. Alternatively, we can notice that applying an X gate to any one of the qubits changes the parity of each basis state to the opposite one, and thus converts the state we got to the state we need. 270 271 ``` 272 operation Solve(qs : Qubit[], parity : Int) : Unit { 273 using (ancilla = Qubit()) { 274 // Create equal superposition of all basis states 275 ApplyToEach(H, qs); 276 // Calculate the parity of states using CNOTs 277 ApplyToEach(CNOT(_, ancilla), qs); 278 let res = MResetZ(ancilla); 279 if ((res == Zero ? 0 | 1) != parity) { 280 X(qs[0]); 281 } 282 } 283 } 284 ``` 285 286 ## D: Quantum classification 287 288 > This turned out to be a rather controversial set of problems :-) Quantum machine learning, like most areas in quantum computing, is a topic of active research. The library used in these problems shows one possible algorithm, and it was interesting for me to explore it and to reverse-engineer the data encoding and model structures that would allow the algorithm to learn and classify the data easily. The problems were chosen to be deliberately "artificial" with just two features, so as to enable both a mathematical approach to the solutions and an engineering one. 289 290 ### [1357D1 - Quantum Classification - Dataset 3](/contest/1357/problem/D1 "Microsoft Q Coding Contest - Summer 2020") 291 292 If you plot the training data you're given, you'll get two classes divided by a vertical line at $x_0 = 0.5$. 293 294  295 296 This means that we need to discard the information about the second feature of the dataset, and base our classification decision only based on the first feature. Feature engineering mode 4 allows to do exactly that: if applied to a parameters array $[a_0, a_1]$ and a features array $[x_0, x_1]$, it combines them into an array that will be encoded as the state $(a_1|0\rangle + x_1|1\rangle) \otimes (a_0|0\rangle + x_0|1\rangle)$ (in the encoding in which the *last* qubit is measured in the end, which is consistent with the library behavior). 297 298 Now, if you measure the second qubit, you'll get $0$ with probability $|a_0|^2$ and $1$ with probability $|x_0|^2$, and $1$ will be the more likely outcome of the two if $|x_0| \gt |a_0|$. If we choose $a_0 = 0.5$, we'll get exactly the classification boundary that we need, and won't need to perform any rotations or to apply bias. 299 300 ``` 301 operation Solve () : ((Int, Double[]), ControlledRotation[], (Double[], Double)) { 302 return ((4, [0.5, 0.5]), [ControlledRotation((0, new Int[0]), PauliY, 0)], ([0.0], 0.0)); 303 } 304 ``` 305 306 ### [1357D2 - Quantum Classification - Dataset 4](/contest/1357/problem/D2 "Microsoft Q Coding Contest - Summer 2020") 307 308 The next problem featured a similar dataset, but with horizontal divides between classes at $|x_1| = 0.75$. 309 310  311 312 This time we need to base our decision on the second feature of the dataset. We can use the same feature engineering as in the first case, followed by a SWAP gate (which can be represented as 3 CNOT gates with alternating control qubits, which in turn are controlled PauliX rotations with $\pi$ as the rotation parameter). This will transform our data into a state $(a_0|0\rangle + x_0|1\rangle) \otimes (a_1|0\rangle + x_1|1\rangle)$, and measuring the last qubit will give us class 1 if $|x_1| \gt |a_1|$, so choosing $a_1 = 0.75$ will allow us to perform the necessary classification. 313 314 ``` 315 operation Solve () : ((Int, Double[]), ControlledRotation[], (Double[], Double)) { 316 return ((4, [0.75, 0.75]), 317 [ControlledRotation((0, [1]), PauliY, 0), 318 ControlledRotation((1, [0]), PauliY, 0), 319 ControlledRotation((0, [1]), PauliY, 0)], ([3.14, 3.14, 3.14], 0.0)); 320 } 321 ``` 322 323 ### [1357D3 - Quantum Classification - Dataset 5](/contest/1357/problem/D3 "Microsoft Q Coding Contest - Summer 2020") 324 325 In this problem we're finally moving on from linearly separable classes to classes separated by more interesting curves — in this case by a circle with the center in (0, 0) and radius 0.8. 326 327  328 329 We're looking for a classification criteria $x_0^2 + x_1^2 \lt 0.8^2$ for class 0. The squares of the features point us to a state $0.8|00\rangle + x_0|01\rangle + x_1|11\rangle$, which, if we measure the second qubit, will give us measurement result $0$ with higher probability in exactly this case (note that the amplitude of the $|10\rangle$ state is $0$). We can prepare this state using feature engineering mode 1 by padding the features array $[x_0, x_1]$ on the left with parameters array $[0.8, 0.0]$ (or any other array $[a_0, a_1]$ such that $a_0^2 + a_1^2 = 0.8^2$). 330 331 ``` 332 operation Solve () : ((Int, Double[]), ControlledRotation[], (Double[], Double)) { 333 return ((1, [0.8, 0.0]), [ControlledRotation((0, new Int[0]), PauliY, 0)], ([0.0], 0.0)); 334 } 335 ``` 336 337 ### [1357D4 - Quantum Classification - Dataset 6](/contest/1357/problem/D4 "Microsoft Q Coding Contest - Summer 2020") 338 339 Here the classes are separated by a hyperbola $0.3^2 + x_0^2 = x_1^2$. 340 341  342 343 The state that gives us this result when measured is $0.3|00\rangle + x_0|10\rangle + x_1|01\rangle$ (notice that now the amplitude of $|11\rangle$ is $0$), which can be prepared using the same feature engineering mode by padding $[x_0, x_1]$ on the left with parameters array $[0.3]$. 344 345 ``` 346 operation Solve () : ((Int, Double[]), ControlledRotation[], (Double[], Double)) { 347 return ((1, [0.3]), [ControlledRotation((0, new Int[0]), PauliY, 0)], ([0.0], 0.0)); 348 } 349 ``` 350 351 > Originally I used a more complicated solution that involved padding with $[0.3, 0.0]$ and swapping the qubits, but then I realized it can be simplified. 352 353 ### [1357D5 - Quantum Classification - Dataset 7](/contest/1357/problem/D5 "Microsoft Q Coding Contest - Summer 2020") 354 355 In the last problem we put together several rotation gates with random parameters and used that model to classify a random set of data. I think some participants managed to reconstruct the result by hand, similarly to the previous problems, but training a model might have been easier. 356 357  358 359 ## E: Quantum Fourier transform 360 361 [Solutions pdf](https://assets.codeforces.com/rounds/1357/problems-e1e2-2.pdf)