By Nickolas, 6 years ago, In English

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

The contest will run from July 6 — 9 and will consist of increasingly challenging tasks on introductory topics in quantum computing: superposition, measurement, oracles and simple algorithms. The top 50 ranked participants will receive a Microsoft Quantum T-shirt!

As a reminder, last weekend we help a warmup round with easier tasks which covered the same topics. The results were quite impressive: 167 participants solved all tasks! You can see the tasks here, and the solutions with explanations here.

Several useful reminders:

  • The contest is unrated.
  • Solutions are accepted in Q# only.
  • Participants are ranked according to the number of correctly solved tasks, with penalty 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.
  • Unlike the warmup round, you're not allowed to discuss the tasks during the contest.
  • By popular demand, we have added Custom Invocation to allow you to run Q# code on Codeforces servers. Here is the signature of the code you should use to run it (note that the namespace and operation name have to match this code exactly):
namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;

    // ------------- Operation which is called from C# -------------------
    operation RunQsharp () : Bool
    {
        body
        {
            Message("Hi");
            return true;
        }
    }
}
  • For tasks which require you to create a certain quantum state or to implement a unitary transformation, any kind of error gives verdict "Wrong Answer". For tasks which have classical return, I tried to differentiate verdicts "Wrong Answer" (your return value was incorrect) and "Runtime Error" (array index out of bounds, qubits released are not in zero state, oracle called too many times etc.).
  • NO PURCHASE NECESSARY. Must be 16 years of age or older. Game ends 7/9/18. For details, see Official Rules.

You can find the discussion of the warmup round and pointers to Q#/quantum computing materials here.

For first time Codeforces users:

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

Good luck! We hope you enjoy the contest!

Update. The contest is over. Editorials are published.

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

| Write comment?
»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Thanks for creating this! A quick question: how do you use basic math functions like sin() or pow() in Q#? I couldn't see how to use Math like in C#.

»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

The submission is in superposition state in the round. After you measure the judge result, you will get CE or AC.

PS: It's really difficult to understand why and how the input qubits are changed in oracle, unlike classical algorithms.

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

    In general, either the target is in a computational basis state, in which case nothing happens (except for the entanglement), or a minus state, in which case the phase is flipped. The thing that is difficult to understand it's what happens after you apply another Hadamard to the input, and the various states are made to interfere with each other. I had to trust Wikipedia for Deutsch-Jozsa and Bernstein-Vazirani, and I tried things almost at random for E2.

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

How is penalty time computed?

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

    The usual ACM ICPC rules: initially the penalty is 0, and for each solved problem it is increased by submission time (since the start of the contest) + 20 minutes for each failed submission.

»
6 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Done. More?

Many problems are way too exercise-like and too much like from the warmup contest, solutions "[search engine of your choice] the solution instantly" aren't a very good thing either. I know it's more of an educational contest, but one learns less by repetitive tasks than creative work. You may have just moved the most trivial problems into the warmup round.

I like A4, C1, C2, D3, since they made me think pretty hard (not that I had to in D3, these were tangential thoughts). The rest is much more boring in comparison.

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

    Indeed, for a four day contest with prices the tasks could have been a bit more challenging. I started 2 and half hours late, and the penalty hit I take is quite severe.

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

      Yeah, the "prizes" are another thing — you really have to start quickly and solve many problems quickly to have a chance of getting a t-shirt. I almost didn't get one just because I took a break in the middle of solving 15 problems, and I see now I dropped from 34th to 48th (and you lost a t-shirt). People who thought this was going to be a 3-day contest and didn't start immediately speedsolving are at a massive disadvantage.

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

      A lot of it is the scoring system, where penalty is based on the sum of your submission times. Maybe using "max of submission times" would have been better.

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

goodbye tshirts :'(

Thank you Nickolas for preparing the round. Some of the problems are really interesting intelligently.

»
6 years ago, # |
Rev. 3   Vote: I like it +21 Vote: I do not like it
System.ArgumentException: Attempt to allocate zero qubits.

Yes, that's precisely what I wanted to do. Please fix the language. :)

Also, consider: https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html

BTW: Why is Result distinct from Bool?

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

    I can only guess that the reason behind measurement returning object of type Result instead of normal boolean is the concept of measurement itself. It is phisically dependent on orthogonal basis you are using to perform such an operation, something like if you were measuring your state in some direction rather than just getting some random 0 or 1. If your measurement basis was |+> and |->, qubit in state |0> now behaves like |->. And now with probability 0.5 you'll measure Zero (and your qubit collapsed to |->) or One (and your qubit is now |+>). Just like Java not having a generic pair class to enforce type safety with you creating your usecase specific class, same way measurement returns Result not Bool.

    Edit: Q# operation M seems to measure in computational base (|0> and |1>)

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

    It's not too much of an issue because you can use the BoolFromResult function to convert.

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

      It just seems a bit pointless. (BTW: b == One is shorter and at least as obvious as BoolFromResult(b).)

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

    I also wanted to allocate zero qubits; having to special-case this seems like a flaw.

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

    If you think of an allocated array as the pointer to the first element, it makes sense — you can't have a pointer to something that doesn't exist. Okay, you can make it a null pointer, but if the OS doesn't support "allocate me nothing and give me a pointer to that nothing", it'd still need special handling internally, you'd have to watch out not to free it, etc.

    The null pointer is special. Ignoring that is often bad design.

    Result is probably distinct from Bool because it actually represents two eigenvalues, not 1 and 0 or true and false. Up (Zero) and Down (One) would be even better names.

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

      Another thing is you can't compare bool to 0 or 1 it has to be true and false.

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

      I think of an array as an array.

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

      It shouldn't be a null pointer, it should be an empty array. Depending on how the internals works, it might be a special-case in the implementation, but it shouldn't be a special case in the language. Every other language I can think of has 0-length lists.

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

        Every other language I can think of has 0-length lists.

        ISO C forbids arrays with length 0 (both C99 and C11). Try compiling

        int main(int argc, char** argv) {
            int x[0];
            return 0;
        }
        

        with gcc -pedantic. It will give you a warning. It's allowed in GCC as an extension, but GNU C is a superset of the C language and it's a feature of C that just because your code is able to do something doesn't mean it should or that it will work.

»
6 years ago, # |
  Vote: I like it +56 Vote: I do not like it

Awesome contest! It was very interesting and fun to study and code in such a different paradigm. Some problems looked like textbook level, but others were very challenging! I had to cram so much stuff in my head this week, but I'm afraid that's not near enough for working with quantum computer in practice...

I'm just a quantum computing noob, can't really judge, but Q# looks like a solid platform to me!

Just for fun, I think Codeforces should add separate ratings for quantum contests, and they should have complex values! Imagine yourself celebrating rating rises, lamenting falls, and not knowing how to feel about phase changes...

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

Is there any doc for custom invocation?

I don't know how to input a quantum qubit.

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

    Custom invocation has C# driver which calls operation RunQsharp and prints its return. Whatever code you need to invoke, you have to call from that operation, creating inputs you need in it. If your code takes qubits as inputs, you have to allocate them in RunQsharp and pass them to your code.

»
6 years ago, # |
  Vote: I like it +146 Vote: I do not like it

I really liked the contest! Many thanks for Nickolas and Microsoft's Quantum Team!

I wish there were more unusual contests like this or Distributed Code Jam. Feels very refreshing after all this countless classical rounds.

Hope there will be more Quantum contests on Codeforces in future!

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

Note: your solution may be judged as Wrong Answer if your solution prints anything to the standard output: DumpMachine(""), Message("foo"), or DumpRegister(""). DumpRegister("a.txt") is ok, though.

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

I liked the contest very much, thank you! Though I didn't really focus on doing everything as quickly as possible, I enjoyed occasionally coding something on weekends. The problems were fun to solve and I would like to experiment with some more.

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

Q# doesn't have "continue" ?

That's weird...

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

    Reserved for C#. There are so many C#-reserved keywords, holy shit.

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

      Would you please tell me where is the c# reserved keywords list?

      thanks.

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

    Does it have break? i think not even that.

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

      it doesn't have a break according to Xellos 's link

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

        actually, I was able to use continue and break for the contest.

        just do not add a semi-colon at the end of the line for break and continue...

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

Will we be able to view others' submissions?

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

Can anyone explain why this solution to A4 gets WA on test case 5? I'm guessing it may be something to do with resetting ancillary bits that are still entangled, but then I'm not sure why it would have worked for the other 4 test cases.

The idea is that I generate k ancillary qubits, and if those bits encode the integer i then I flip bit i of qs; but I set up the ancillary bits in a superposition of all 2^k=N basis states so that the input bits become a super-position of weight-1 states. My calculations for small k showed that the final application of H to the ancillary bits dis-entangled them, in the sense that any combination of basis state of those bits and valid basis state of the input bits has the same coefficient, except for sign.

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

    I tried to simulate your solution for k = 1 (N = 2**1 = 2 qubits), and for such an input code simplifies to:

    operation Solve (qs : Qubit[]) : () //qs =  two qubits in state |0>
        {
            body
            {
                let N = 2;
                using (b = Qubit[1])
                {
                    H(b[0]);
                    X(b[0]);
                    CNOT(b[0], qs[0]);
                    X(b[0]);
                    CNOT(b[0], qs[1]);
                    H(b[0]);
                    ResetAll(b);
                }
            }
        }
    

    Or maybe I missed something? Otherwise before ResetAll(b) you'd get 1/2 (|001> + |010> + |101> — |110>) — first bit being b[0]. Since ResetAll performs measurement, if you measure One as b[0], your state is now |->. Maybe this is an answer to your question?

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

    I won't bother with writing normalisation factors.

    • For N = 2, immediately after using, you have (k = 1 so I'll only use b as the auxiliary qubit):
    • Now you apply Hadamard:
    • Loop iteration with i = 0:
      • Applying X to b:
      • Applying CX on q0:
      • Applying X to b:
    • Loop iteration with i = 1:
      • Flip does nothing since 1 = 20
      • Applying CX on q1:
      • Flip does nothing again
    • Final Hadamard:

    When you reset b, you reach either (measuring Zero) or (measuring One). You made a mistake somewhere or I made a mistake somewhere or both.

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

      Thanks (and to Wielomian too) — I'd missed that the signs will carry through to the final state vector. Possibly I just got lucky with the measurements when I solved cases 1-4. So to make this work I'd probably need to look more carefully at the signs.

»
6 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Thanks for the contest! I'm curious how the evaluator works for problems where you had to produce some quantum state as output. Do you have a back door to access the quantum state vector or do you have to do it probabilistically via repeated execution and measurement?

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

    I allocate qubits in zero state, apply the participant's solution, then apply the adjoint of the reference solution and check in the end qubits are in zero state again (using AssertAllZero method which has access to the state in the simulator).

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

How to achieve 1/sqrt(2) error-free probability for B2? I searched through numerous academic papers but couldn't find the relevant information. Some referenced it as well-known but only cited a paper that isn't publicly available.

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

    I guess you are talking about C2.

    If you measure |0> then you get 0. If you measure |+> then you get 50/50. Therefore if you measure and get 1, it was |+>.

    Since we need to cover both cases, we can choose to measure "along" |+> and use the same trick. (instead of measuring "along" axis we can perform a rotation a do a normal measurement).

                let r = RandomInt(2);
                if (r == 0) {
                    if (M(q) == One) {
                        return 1;
                    }
                    return -1;
                }
                else {
                    if (Measure([PauliX], [q]) == One) {
                        return 0;
                    }
                    return -1;
    
                }
          
    
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I think it's this one, and ResearchGate allowed me to download it without logging in.

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

      Thank you!

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

      But is it possible to perform such a three-valued measurement in Q#? If so, how?

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

        Yes. The measurement you want to do in Q# is actually four-valued (you need to use at least one ancilla, and measure at least two qubits), but if you pick the rotation correctly then one of the results will have probability zero of occurring.

        This is not really a requirement though: you could just as easily have two possible measurement results that each return -1, if you're less careful with your rotation, which will still give the same success rate.

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

          Could you explain, or at least point me to a reference material, how to perform rotations in the 2-qubit space using only single-qubit rotations? Even if I ignore phase and treat it as a 4-D space with the computational basis, I can't grasp what the single-qubit rotations would do (a rotation around a hyperplane? Which one? How does it help me if I can't visualize 4-D?), much less how to combine them to get to a desired state.

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

exactly 100 participants solved all tasks. wow.

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

What does the "adjoint auto;" do, in solution of A4?

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

    It specifies that Q# compiler should generate the adjoint (inverse) of this operation automatically, as described here. It is not actually required for the participant's solution, this line sneaked in from reference solution which does need it (the tester code applies adjoint of the reference solution to invert the transformation done by the submission, so it needs to know how to generate adjoint).

»
6 years ago, # |
  Vote: I like it +23 Vote: I do not like it

We have published the tasks together with the testing harnesses, "coding kata"-style, here. The implementation is slightly different from the tester code used on Codeforces, since the katas use unit tests and Codeforces uses executables, but the core of the checks is the same.

The katas have some tasks not included in the contest, and we plan to add more over time. If you feel like you need more quantum computing programming exercises, take a look :-)

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

    Aha this is cool! thank you!

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

    How to pass a C# array int[] to the Q# operation as an input Int[]? Thanks.

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

      You have to create a QArray of the type you want to pass (Q# integers are represented as long in C#). You can see this example, where the C# driver passes an array of integers to Q# operation DeutschJozsaTestCase.