codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![D1 training data](/predownloaded/46/d2/46d29ecb41a1ae748b3d18fbd183b1660f352708.png)
    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 ![D2 training data](/predownloaded/9e/41/9e418b687de6bb45fa065d3c6d325f1b2500379a.png)
    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 ![D3 training data](/predownloaded/cf/6f/cf6f2854450f854777f5f77b091ae082b7b74c3f.png)
    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 ![D4 training data](/predownloaded/96/fe/96fef1775fca46d9775c8b58e04828d465f1161c.png)
    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 ![D5 training data](/predownloaded/73/69/7369d85a40274df4fbbcf11690b21d044bd6dd7e.png)
    358 
    359 ## E: Quantum Fourier transform
    360 
    361 [Solutions pdf](https://assets.codeforces.com/rounds/1357/problems-e1e2-2.pdf)