codeforces-scrape

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

1356.md (9968B)


      1 Source: https://codeforces.com/blog/entry/78832
      2 
      3 The warmup round is over; I hope you enjoyed it and learned something new in the process!
      4 
      5 Here are the explanations for the contest problems and pointers some extra resources that can help you learn more about the respective topics before the main contest. You should also be able to see the solutions of the contest participants and to solve the problems in practice mode.
      6 
      7 ## A: "Distinguishing Unitaries" problems
      8 
      9 Here is the editorial for the problems: <https://assets.codeforces.com/rounds/1356/A1-A5.pdf>.
     10 
     11 > These problems are [published in the Quantum Katas](https://github.com/microsoft/QuantumKatas/tree/master/DistinguishUnitaries), so that you can see the testing harness used for the problems and use it for testing your solutions in the main contest.
     12 
     13 ## B: Reversible computing
     14 
     15 Reversible computing is a branch of quantum computing that deals with expressing classical computations in a reversible manner (i.e., so that the computation has a unique input state for each output state, and inputs and outputs allow a 1:1 mapping). This enables us to perform classical computations (such as arithmetic) on quantum data. This can be done in a systematic way by decomposing the classical computation into primitive classical gates (such as NOT, XOR, OR and AND) and replacing each classical gate with its reversible equivalent (NOT with X gate, XOR with CNOT gate and AND with CCNOT gate), possibly with the use of extra qubits to store intermediary computation results. Let's see how this approach can be applied to these tasks.
     16 
     17 ### [1356B1 - Increment](/contest/1356/problem/B1 "Microsoft Q Coding Contest - Summer 2020 - Warmup")
     18 
     19 Consider the logic of incrementing a classical number in binary notation:
     20 
     21 * Flip the least significant bit.
     22 * If the least significant bit is now 0, increment the rest of the number (i.e., flip the second-least significant bit, check whether it is 0 and apply the same procedure recursively).
     23 
     24 We can swap these two steps, so that we would first increment the rest of the number if the least significant bit is 1, and then flip the least significant bit.
     25 
     26 To translate these steps to quantum gates,
     27 
     28 * If statements translate to controlled gates (remember that all computations have to be done without measurements, so that if the qubit inputs are in superposition, they remain in superposition after the computation as well); we can use `Controlled` functor to call controlled version of `Solve`, with the first argument being the array of control qubits (the least significant bit) and the second argument being the arguments passed to the `Solve` (the rest of the bits).
     29 * Flipping the bit corresponds to applying an X gate to it.
     30 
     31 ```
     32 operation Solve (register : LittleEndian) : Unit is Adj+Ctl {
     33     // unwrap LittleEndian type
     34     let qarray = register!;
     35     if (Length(qarray) > 1) {
     36         // increment the rest of the number if the least significant bit is 1
     37         (Controlled Solve)([qarray[0]], LittleEndian(qarray[1 ...]));
     38     }
     39     // increment the least significant bit
     40     X(qarray[0]);
     41 }
     42 ```
     43 
     44 ### [1356B2 - Decrement](/contest/1356/problem/B2 "Microsoft Q Coding Contest - Summer 2020 - Warmup")
     45 
     46 It is possible to implement the decrement operation in a manner similar to the increment, by analyzing the pattern of bits transformation that happens to a number when it is decremented. But a faster and more neat way involves realizing that decrement is the inverse of the increment operation, or, in quantum computing terms, its adjoint. This means that you can just copy your solution to the previous problem (under a different name, say, `Increment`) and call `Adjoint Increment(register);` in your solution.
     47 
     48 > Here are the resources to learn more about reversible computing and solving problems of this type:
     49 >
     50 > * [The Quantum Katas](https://github.com/microsoft/QuantumKatas/) that cover quantum oracles (DeutschJozsaAlgorithm, GroversAlgorithm, SolveSATWithGrover, GraphColoring) and quantum arithmetic (RippleCarryAdder).
     51 > * Problems G1-G3 from [Winter 2019 — Warmup](https://codeforces.com/contest/1115) and problems C1-C3 from [Winter 2019](https://codeforces.com/contest/1116) Q# contests.
     52 
     53 ## C: [1356C - Prepare state |01⟩ + |10⟩ + |11⟩](/contest/1356/problem/C "Microsoft Q Coding Contest - Summer 2020 - Warmup")
     54 
     55 This problem is extremely similar to [task 2.3 of the Superposition kata](https://github.com/microsoft/QuantumKatas/blob/master/Superposition/Tasks.qs#L228). You can find a detailed explanation of the math used in that solution in the [workbook](https://github.com/microsoft/QuantumKatas/blob/master/Superposition/Workbook_Superposition_Part2.ipynb).
     56 
     57 To adapt that solution to this problem, you can use the code for that solution exactly as it is to prepare a $\frac{1}{\sqrt3}(|00\rangle + |01\rangle + |10\rangle)$ state, and as the last step apply an X gate to each of the qubits. This will flip $|0\rangle$ states to $|1\rangle$ and vice versa, resulting in the $\frac{1}{\sqrt3}(|11\rangle + |10\rangle + |01\rangle)$ state, which is exactly our target state.
     58 
     59 > * This approach to preparing states is called post-selection. You can learn more about it in the ["Repeat-Until-Success Examples"](https://docs.microsoft.com/en-us/quantum/user-guide/using-qsharp/control-flow#repeat-until-success-examples) section of Q# documentation.
     60 > * Another example of preparing a state using post-selection can be found in task 2.7 of the [Superposition kata](https://github.com/microsoft/QuantumKatas/tree/master/Superposition).
     61 
     62 ## D: Quantum classification
     63 
     64 Both classification problems in the warmup round were very similar to the problem solved in [MLADS tutorial](https://github.com/microsoft/MLADS2020-QuantumClassification) linked from the statements.
     65 
     66 If you plot the training data you're given (I used the Python notebook included in the tutorial to do this, with some modifications to load the data from file rather than generate it on the fly), here are the images you'll get:
     67 
     68 ![D1 training data](/predownloaded/9c/dc/9cdc8589b25d350696d18ead1dded99db38d2c64.png) ![D2 training data](/predownloaded/0a/67/0a670bce58e78d5610c6d8fb6623ac04e7dea193.png)
     69 
     70 You see the similarity with the tutorial: in all cases the classes are defined by the polar angle of the data point, and not by the distance from the origin. The encoding of the data in the qubit state, described in the "Data Encoding" section of the tutorial, fits this type of problems perfectly, since it preserves the relative magnitudes of the features but discards the information about their absolute magnitudes.
     71 
     72 This means the we have only one qubit to build our model upon, which leaves us a very limited choice of gates: Rx, Ry and Rz. The classification process is going to be very simple (and match exactly the one described in the tutorial):
     73 
     74 1. Encode the data point into the qubit state.
     75 2. Apply a rotation gate.
     76 3. Measure the result and interpret it.
     77 
     78 From here, you can take two approaches to the solution:
     79 
     80 #### Mathematical approach
     81 
     82 A model without any gates and with 0 bias is going to perform classification that is exactly the opposite of what we need in D1, with 100% error rate, classifying the vertical "hourglass" area as class 1 and the horizontal "hourglass" — as class 0. To get D1 classification correct, you need to rotate the data by $\pi/2$ either clockwise or counterclockwise (which corresponds to Ry gate), so that the data from class 0 becomes aligned with the horizontal axis, and the data from class 1 — with vertical. Remember that the angle parameter you pass to the gate is *twice* the rotation angle you'd use geometrically, so the model parameters end up being (rotation angle = 3.14, bias = 0.0).
     83 
     84 The first step to solve D2 is to rotate the data as well, so that middle axis of class 0 is aligned with the horizontal axis — we'll need a $\pi/6$ geometric rotation, or $\pi/3$ parameter for Ry gate. However, this time we'll also need to tweak the bias to modify the width of the area that is classified as class 0. Some experimentation or a geometric representation will show that bias = 0.25 allows to achieve this.
     85 
     86 #### Software engineering approach
     87 
     88 Alternatively, you can train the model using the provided library to learn the rotation angle and the bias. Most frequently asked question here was tweaking the hyperparameters of the training process so as to speed up the learning. To improve the learning speed and push the model away from the starting parameters, I had to increase LearningRate parameter and reduce Tolerance, as you can see in [this code](https://github.com/microsoft/MLADS2020-QuantumClassification/blob/master/QuantumClassification/Backend.qs#L44). You can find the list of hyperparameters available to the training process [in the code comments here](https://github.com/microsoft/QuantumLibraries/blob/8706abea604ab74db94992c69cd726a268d5c309/MachineLearning/src/Types.qs#L163).
     89 
     90 > The most frequent cause of runtime error verdicts on these two problems was using the more complicated model structure from the [library documentation example](https://docs.microsoft.com/en-us/quantum/libraries/machine-learning/basic-classification), rather then the simpler and the more suitable model structure from the tutorial. You have to make sure that the qubits you're referencing in your model will actually be used to encode the data; in this case the data has 2 features and there is no preprocessing to engineer more features, so those 2 features will be encoded in the state of 1 qubit, and referencing qubit with index 1 will cause a runtime error. 3 or 4 features will be encoded in 2 qubits, 5-8 — in 3 qubits and so on, the number of qubits used is the power of the nearest power of two greater than or equal to the number of features.
     91 
     92 In the main round of the contest we'll take a closer look at how to use feature engineering to build and train more complex models.