Microsoft Q# Coding Contest — Winter 2019
By Nickolas, 6 years ago, In English

Microsoft's Quantum Team and Codeforces are excited to invite you to Microsoft Q# Coding Contest — Winter 2019!

The contest will run from March 1 to March 4 and will offer increasingly challenging tasks on superposition, measurement, quantum oracles and unitary transformations.

As a reminder, last weekend we held a warmup round with easier tasks on quantum oracles and unitary transformations; the tasks are available for practice here, and the solutions are explained here. You can brush up on the topics of superposition and measurement in the first Q# contest and its warmup round.

Several useful reminders:

  • The contest is unrated :-)
  • Solutions are accepted only in Q#.
  • Participants are ranked according to the number of correctly solved tasks, with the last correct submission time as a tiebreaker.
  • The tasks are grouped by topic, and the tasks within one topic are ordered in approximate order of increasing difficulty. If you find a problem too hard, don't forget to check the next problems in this topic and problems from different topics, they might turn out to be easier.
  • Submission verdicts work as follows:
    Wrong Answer means that the solution fails any problem-specific checks (such as leaving the qubits in a state other than expected, using measurements in a task which prohibits them or returning incorrect classical value in measurement tasks) or prints anything to the standard output (using Message or DumpMachine functions);
    Runtime Error means that the solution throws a more general exception (for example, caused by releasing allocated qubits in non-zero state or trying to access array elements outside of array bounds);
    Memory Limit Exceeded means that the solution together with the checker allocated more qubits than it is allowed (the limit is ~15 qubits for problems related to quantum oracles with memory limit 1024MB, and ~25 qubits for other types of problems);
    Time Limit Exceeded works the same way as in classical competitions (your program is too slow), but I have to mention it for the sake of completeness :-)
  • Custom Invocation allows you to run Q# code on Codeforces servers; make sure your code has namespace Solution and an operation with a signature operation RunQsharp () : Bool defined in it.
  • And finally, the really important stuff: the top 50 ranked participants will receive a Microsoft Quantum T-shirt! Here is a preview:
  • NO PURCHASE NECESSARY. Must be 16 years of age or older. Game ends 3/4/19. For details, see Official Rules.

Good luck! We hope you enjoy the contest!

For first time Codeforces users:

  1. Create user account here.
  2. Register for the contest here.
  3. Once the contest starts on March 1st, access the problems here.

Update: The contest is over. Congratulations to eatmore for a very convincing victory!

Update 2: The editorials are published here. The comments to that post have some great explanations of alternative solutions as well.

  • Vote: I like it
  • +144
  • Vote: I do not like it

Comments Comments (68)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

No time limit exceeded?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Time Limit Exceeded is very intuitive and works the same way as in classical contests, so I didn't highlight is separately. You can, for example, get Memory Limit Exceeded by allocating purely classical resources, but that's classical so I didn't focus on that as well.

    → Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

That's an amazing design!

Also, I'm curious about the last contest's design. What did it look like?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

From where I can learn Quantum Computing theories to participate in these contests? Please share some resources to start with.

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It's a Shrodinger cat on the T-shirt

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Woowww no TLE involved??? :333

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've updated the post to include TLE as well, even though there is nothing specifically quantum about it.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

While trying to use custom invocation to run code, I get a complaint from the compiler along the lines of:

CSC : error CS5001: Program does not contain a static 'Main' method suitable for an entry point ``

However, it does say that the Q# has compiled correctly. Is there an example of code that runs with the custom invocation?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Why does following code gets RTE? (When submitted similar code in A1 its WA, but in A2 RTE)

namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;

    operation Solve (qs : Qubit[], bits : Bool[][]) : Unit {
        body(...) {
		  using(x = Qubit[2]) {
		  }
		}
		adjoint auto;
    }
}
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Ah, this is a tricky case! This throws a ReleasedQubitsAreNotInZeroState exception, which is generally treated as a Runtime Error. The qubits you release are released in 0 state (obviously, since you haven't done anything with them). But the checker allocates some extra qubits to to test that your solution returns correct answer — and those are the ones which are released in non-zero state if your solution is incorrect. (This same code gets WA if submitted to A1, because in A1 the checker doesn't allocate and release extra qubits.)

    I don't have a good way to distinguish ReleasedQubitsAreNotInZeroState caused by the solution vs caused by the checker because of incorrect solution. I'll think some more about it, but for now it will have to stay like this — some things that should be Wrong Answer produce Runtime Error instead :-(

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problems where measurement isn't allowed, is calling Reset(q) on an ancillary qubit also prohibited?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yes, Reset does a measurement followed by an X gate, if one is required, so it is also prohibited.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You really weren't kidding about the problems being tougher than last time. I got VERY hacky with my solutions, and stayed up for 12 hours.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Yes, I think this time we calibrated the complexity much better — last time the fate of the T-shirts was decided in less than 24 hours, and now it doesn't seem to be the case.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm getting "Time limit exceeded" error, so I wonder, what are the durations of execution for standard gates operations on Codeforces server?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's hard to estimate, and not particularly useful — the total execution time of your program depends not only on the number of gates in your code but also on things like the number of qubits allocated (more qubits makes everything slower, since applying a gate requires updating more values).

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. I see. Maybe you can at least provide some estimation, on how many value updates can be done per second? At least some order, e.g. tens of thousands, millions, etc.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hundreds, in my estimate. It's low enough you most likely can't bruteforce through problems like C3 with O(2N) applications of (Controlled X)(x, y) and some applications of X(x[i]) on suitable indices.

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Are the strict time limits in some problems intended? For example, in Problem B2 the solution gets called 1000 times but the time limit is only 1 second. It seems like you could get TLE just because you use an additional Qubit or perhaps two quantum gates in those problems.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'm pretty sure those things won't push you over the limit.

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, the time limits are intended. The reference solutions never take more than a half of the time limit to run, and I didn't pick the most optimized solutions as reference ones either :-)

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi! For question B2, is the idea that you can determine which state the qubit was not in with 100% accuracy? Wording doesn't explicitly say that but seems to imply it.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. To be more precise, to determine "a" state which you know with certainty it wasn't in.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Many thanks. I thought that was the case but just wanted to be sure before I carry on staring at it ;)!

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I would really really really recommend you do the last one before this. The last one turned out to be MUCH easier than I thought. I solved it in a few minutes after hours of staring at B2 with no luck.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Stuck on both ¯\_(ツ)_/¯

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            I see you solved it. What did I tell ya? ;)

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              Haha! Yep just managed it now. 99% sure I haven't done it the 'correct' way but it's done at least. Time to stare at B2 some more ;)

              → Reply
»
6 years ago, # |
  Vote: I like it -17 Vote: I do not like it

If less than 50 people solved all questions, do you still give out the T-shirts to the top 50, or only to the ones that solved all 13?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    the top 50 ranked participants will receive a Microsoft Quantum T-shirt!

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    The rules say we'll give them to top 50, so that's what we'll do. Right now it doesn't look like it will be necessary to solve all problems to get in top 50, but there is still time for this to change :-)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thanks.

      Also, on a completely unrelated note: I noticed that there is no "break" statement in the language. Is this because it would be harder to reverse operations that contain them?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Yes.

        It's possible to simulate "break" using repeat-until-success loop, as described here.

        → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I'm kinda unclear on the exact meaning of the question B2. Are you guys saying that we are able to find which state its not in, or that we're able to do so with high enough probability that its ok for the 1000 rounds?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    You have to find a state in which qubit is not on every trial; the number of rounds just tells you that it's not a single-shot experiment.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      gotcha, thanks!

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The language doesn't allow us to define our own (arbitrary) measurement operators, does it?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Only by expressing them in terms of M and Measure.

        → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I thought I had to give up on B2, but after thinking about it for a looooong time, I finally got it. Now I can finally sleep without worry.

What a great problem! Very counterintuitive.

Thanks for the contest! Even though my rank is lower than last time, I really enjoyed the more challenging problems. Looking forward to getting my T-shirt :D

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you solve it? I honestly cannot wait until the editorial is out.

    I tried introducing qubits, I tried looking into QFT, I even found this specific problem (called trine states) but I had to use measurement operators not in Q#.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It stumped me for a long time. My reasoning was: If all we do is some kind of transformation, then measure the qubit, this problem is impossible (because there's no way to get more than one of A,B, and C into a pure 0 or 1 state). So for this problem to be solvable, we need to introduce at least one more qubit. But how can that help? It seems like we would be getting information out of nowhere.

      However, eventually I figured it out — measurement is a projection. So even though A and B are not orthogonal, they could become so after a measurement projects them onto a different plane. Of course, that's impossible to guarantee. But... it IS possible to guarantee that EITHER A and B become orthogonal, or A and C do.

      So, first apply H and S to turn the three qubits into something more manageable. Then allocate another qubit. You can come up with a transformation that turns A into a combination of 00 and 10, B into a combination of 00, 01, and 11, and C into a combination of 10, 01, and 11 (Notice that if we only look at our original qubit, it looks like B turns into 0 and C turns into 1. This can't happen! But if you rotate the extra components into the 01/11 plane, it works).

      Notice, once you measure the second qubit, if you get 1, you could not have started with A. and if you get 0, you can measure the first qubit and know that it's not B, or not C.

      I think you should be able to reconstruct the solution from this. I'm not good at putting these vague thoughts into words.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I had similar ideas but was too bad at geometry to figure out the right rotations.

        → Reply
»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Is it possible to get this t-shirt from somewhere if i'm stupid enough to be top-50?)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I suggested t-shirts for finding important bugs, but no, you can't — other than by making one for yourself or getting it from someone who was in top 50.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +41 Vote: I do not like it

What a cool Tshirt! And what a pity I can't solve some of the tricky and interesting tasks.

Looking forward to next Q# contest!

(...I really really like that Tshirt QAQ

(...Is there any way to get one if I am not the top 50? QwQ

→ Reply
»
6 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Wow, thank you for the contest! The problems were great and I had a lot of fun while solving them. Unfortunately, It's quite a pity that I couldn't come up with a solution for the problem B2 (I spent ~16 hours solving it though), but I definitely enjoyed the whole process of solving.

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks a lot for organizing this contest. It was a lot a fun and I learned quite a few things. Special thanks to problem B2 which kept me busy for quite some time (But the solution in the end was quite intuitive and nice. It was also a nice contrast the the problems D1 — D6, which I mostly solved by trying out a few operations that look promising until the results matched.)

Also thanks for updating the language. The compiler error messages were a lot more helpfull that last year. (And I had no issues with the simulator this year.)

Some probably unintended solutions:

  • A1: Just call StatePreparationPositiveCoefficients. (I didn't try this for A2 as I expected it to get TLE. It would be interesting to see what this function does internally and if it could be optimized for sparse states.)
  • B1: We can use StatePreparationComplexCoefficients to get an operation that maps |000> to |ψ₀>. Applying the adjoint maps |ψ₀> to |000>, so we can just measure all qubits and check if they're zero.
  • C2: Hardcoding all periodic strings and checking them with ControlledOnBitString gets TLE. We can optimize a factor of two if we note that the periodicity does not change if we flip all bits. This gets OK. (I tried something similar for C3, but I got TLE.) Intended is something with QFT?
  • C3: Is using IntegerIncrementLE intended? (that + manually modding by 3 gives OK while ModularIncrementLE gives TLE. Once again, I don't know which algorithms are used internally. The modular one uses QFT I guess?)
  • I also used IntegerIncrementLE for D4 and D5, but I guess there are many solutions to the D-tasks.
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    IntegerIncrementLE can be implemented pretty easily. The codes below are for adding/subtracting 1.

    operation sub1 (x : Qubit[]) : Unit {
	for(i in 0..Length(x)-1) {
		Controlled X(x[0..i-1], x[i]);
	}
}
operation add1 (x : Qubit[]) : Unit {
	ApplyToEach(X, x);
	sub1(x);
	ApplyToEach(X, x);
}
    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had so many TLEs on C3 trying to use IntegerIncrementLE. How did you manage to do it?

    I ended up passing by abandoning that approach, and using three qubits that alternate between 100,010, and 001.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried something similar for B1. I just used the solution from the Katas for the W state with 3 qubits. I used the adjoint and measured, but wasn't sure if that would actually be a correct solution, since I might map the second state to something with 000 and measuring would give 000.

    For C2, I hardcoded which periodicity based on the numbers. E.g. for 6 qubits, the possible are 1,2,3,4,5, but 2 is already 4-periodic, and 1 is already n periodic, so exclude them, and test for 3,4,5.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Here's a proof that the approach for B1 is correct:

      The two states are orthogonal. So if you apply a unitary that takes the first state to |000>, the second state must map to something that's orthogonal to |000>. This means that if you measure it, it's impossible to get 000.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    We're publishing the editorial here (it will take us some time to finish the descriptions for the harder problems — sorry about that!)

    • A1: this is a perfectly intended solution — it's an A1 problem, after all :-) Well, the library function I used was PrepareUniformSuperposition because I'm too lazy to specify the coefficients explicitly :-) You can see the implementations of all library operations in this repo.
    • B1: intended solution again :-) Admittedly, the reference solution did the prep manually (because I already had the code for W state in the katas, after that it's just a couple of phases), but since it's only a three-qubit state, library state preparation routines will also work.
    • Reference solutions for C2 and C3 are already there in the editorial. In them I aimed to have hardcoding all solutions time out, but if you do something clever to optimize your solution it should pass — the exact nature of cleverness was not specified.
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm honestly surprised at how long the solution for D6 is. Mine only used 1 extra operation, which increments a basis state |k> to |k+1 mod 2^n>

      operation Solve(qs : Qubit[]) : Unit{
    let N = Length(qs);
    mutable r = 1;
    for(i in 0..N-1){set r = 2*r;} //Is there an exponentiation operator in Q#?
    for(i in 0..r-2){
        Controlled H(qs[1..N-1],qs[0]);
        increment(qs);
    }
    increment(qs);
}

operation increment(qs : Qubit[]) : Unit{
    body(...){
        for(i in (Length(qs)-1)..(-1)..1){
            Controlled X(qs[0..i-1], qs[i]);
        }
        X(qs[0]);
    }
    adjoint auto;
    controlled auto;
    controlled adjoint auto;
}
      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        For the exponentiation, you could use 1 <<< N or 2^N.

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      D6 took me a long time but I found a really short solution.

      First, a helper function to entangle the middle two vectors (111110 and 000001).

      Then do a recursion — apply Solve to the first N-1 bits, controlled on the last bit. Apply the helper. Then apply Solve to the first N-1 bits again, but controlled on the last bit being 0.

      The base case for N=1 is simply H.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For B1, that's what I did, except I manually came up with the transformation to prepare the state (just a variation on A1, with some phase changes).

    For C2, for each k between 0 and N/2, you can check if the k-prefix and k-suffix of the string are equal.

    My first approach was checking periodicity for EVERY period, which TLEs.

    For D4, I used IntegerIncrementLE — I'm curious if there's any other approach.

    For D5 it's definitely possible to do without — I came up with a pretty neat recursive solution.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I checked periodicity for every period, but avoided the TLE by not allocating extra qubits while checking for equality. Instead, I did some dirty hack of "overwriting the input qubits with the output qubits."

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I hardcoded all periodic strings in a more compact way on C2. There are just a few conditions the qubits need to satisfy, starting with "if the first and last qubit are the same, it's periodic".

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    For C2, I literally brute-forced all possible values of P, doing something similar to my palindrome checker oracle (from the warmup round) to check pairs of bits for equality. I just allocated an ancilla qubit to store the result of each P. Then I just reused the OR oracle from the warmup round and the WithA operation. My solution ended up being an almost direct translation of the definition given in the problem statement.

    EDIT: Well, basically this was the intended solution.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used approach similar to yours but got TLE on case 5 can you please have a look [link] .(https://mirror.codeforces.com/contest/1116/submission/50695009)

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        From what I can tell, your solution allocates an ancillary qubit register, qs, to determine periodicity. It is possible to do this operation on place on x, then revert it afterwards.

        In addition, your 'or' register doesn't actually use it's 0-index qubit. It might be worth refactoring your code so that it doesn't need it.

        Every qubit added, at minimum approximately doubles the amount of time required to run, so every little qubit counts.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes , I used qs to calculate the periodicity for every possible period and if the string is periodic for some period p , then or[p] would be One , then I used the OR oracle on or. Can you please tell me how can I determine periodicity in place , I stored the XOR of x[i] and x[i+p] in qs[i] and used Controlled X gate on qs to know if periodic for period p.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Basically, if one is careful about the order, they can put x[i] XOR x[i+p] into x[i] for all i from 0 to n-p-1 in a reversible manner.

            Using the first [n-p] qubits instead of the qs, determine whether it is periodic with period p.

            Then reverse the modifications to x, to return it to its original form.

            → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You can check the editorial posted above. My solution ended up being basically the same as that one, and the same as sirknightingfail mentioned.

            → Reply