Автор Nickolas, 15 месяцев назад, По-английски,

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 abacabadabacaba 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.

 
 
 
 
  • Проголосовать: нравится
  • +144
  • Проголосовать: не нравится

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

No time limit exceeded?

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

»
15 месяцев назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

That's an amazing design!

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

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

It's a Shrodinger cat on the T-shirt

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Woowww no TLE involved??? :333

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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;
    }
}
  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    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 :-(

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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).

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 :-)

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
15 месяцев назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

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?

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    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 :-)

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Yes.

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

»
15 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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?

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

»
15 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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#.

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I couldn't figure out how to make B and C measure differently (use different basis states). I figured I could change the states to be cos(k*pi/3)|0>+sin(k*pi/3)|1>, but not much after that.

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится +41 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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.

»
15 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.
  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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);
    }
    
  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I solved C2 with a much simpler approach than using QFT and I'm pretty sure that's the intended solution: for each P from N/2 to N-1 check if every pair of bits in the input whose position's index differ by P are equal. If this is true for some P, the input is periodic.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      That's actually pretty smart and easier to implement than a mod 3 adder. I whipped out Karnaugh maps for this one.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Oooooh, I like it.

        I really ought to start refining my intuition for qubits.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.
    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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;
      }
    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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."

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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".

  • »
    »
    15 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          15 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            15 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

          • »
            »
            »
            »
            »
            »
            15 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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