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

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.

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

»
6 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

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

How is penalty time computed?

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

    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 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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 лет назад, # ^ |
        Проголосовать: нравится +23 Проголосовать: не нравится

      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 лет назад, # |
Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

goodbye tshirts :'(

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

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +21 Проголосовать: не нравится
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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

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

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

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

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

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

      I think of an array as an array.

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

      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 лет назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

        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 лет назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

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

Is there any doc for custom invocation?

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

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

    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 лет назад, # |
  Проголосовать: нравится +146 Проголосовать: не нравится

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

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

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

Q# doesn't have "continue" ?

That's weird...

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

Will we be able to view others' submissions?

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

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

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

    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 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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

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

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

    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 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

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

      Thank you!

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

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

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

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

          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 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

exactly 100 participants solved all tasks. wow.

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

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

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

    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 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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

    Aha this is cool! thank you!

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

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

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

      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.