Microsoft Q# Coding Contest — Summer 2020: Main round
By Nickolas, 4 years ago, In English

Microsoft's Quantum team and Codeforces are excited to invite you to Microsoft Q# Coding Contest — Summer 2020! The contest will run from June 19 to June 22.

As a reminder, last weekend we held a warmup round with easier tasks on the topics that have not been covered in the previous contests. You can find the problems from the warmup round for practice here, and the described solutions here. There is also a list of great learning and practice resources here.

Several useful reminders:

  • The contest is unrated :-)
  • Solutions are accepted only in Q#.
  • 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, check the next problems in this topic and problems from different topics, they might turn out to be easier for you.
  • 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 the really important stuff: the top 50 ranked participants will receive a Microsoft Quantum T-shirt, and 25 random participants who solved at least one problem but didn't finish in the top 50 will also receive a Microsoft Quantum T-shirt! Here is a preview (we haven't printed the T-shirts yet, so the final look in print might differ slightly):

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 June 19th, access the problems here.
  • Vote: I like it
  • +331
  • Vote: I do not like it

Comments Comments (210)
| Write comment?
»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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.

So does this replace the Solve from the practice problems and previous years? And what is the boolean you have to return? Or am I confusing things?

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

    This is not related to Solve in the problems in any way.

    • The problems run with the testing harness, which provides input and verifies the output/results of running the solution. Solve is the interface with that testing harness.
    • Custom Invocation allows you to run arbitrary Q# code, but it doesn't provide you any feedback on it, you have to take care of the inputs/outputs yourself. RunQsharp is the entry point that will be called, after that it's up to you what it does — it can call one of the Solves with appropriate parameters, or some completely unrelated code. (This implementation predates the @EntryPoint syntax, maybe we'll take advantage of it for the next year :-))
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh! My problem was simply that I hadn't heard of custom invocation before. That's great actually -- I'll try out this workflow tomorrow before the contest, see if that works better for me. Thanks.

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

    And what is the boolean you have to return?

    The return value seems to be kind of like the exit status in Unix. The Custom Invocation runner prints Return value True or Return value False to the stdout, but that's not super useful since you can simply use Message() to print arbitrary information.

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -17 Vote: I do not like it

F

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

I am facing the same problem on MacOs. While changing to Microsoft.Quantum.MachineLearning::0.11.2006.403 cannot solve the issue for me(my sharp version is the same). A handful of "error QS6104: No namespace with the name "Microsoft.Quantum.Convert" exists." still occurs. And I have no idea how to deal with it Can someone help with this plz!

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

the T-shirt seems beautiful.

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

nice shirt, but ironed would look better xD

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

What is the shirt design supposed to represent?

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

Does Q# have a function to get current time? (If that's ok to ask during the contest.)

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

    No. That kind of classical processing is delegated to the classical driver.

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

I'm getting this error when I'm trying to make Custom Invocation: CSC : error CS5001: Program does not contain a static 'Main' method suitable for an entry point

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

    Are you defining operation RunQsharp () : Bool in your code? That serves as the entry point.

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

      Yes.

      Edit: Even if I try to run this:

      namespace Solution {
    open Microsoft.Quantum.Intrinsic;
    
    operation RunQsharp () : Bool {
        return false;
    }
}
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is weird, the same code runs fine for me... You couldn't have gotten a different site version, could you?

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

          No, I even tried on a different browser.

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

          Okay, it's working now.

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

Comrades, when exactly will this contest finish? At 19-00 (GMT+3), 22.06.2020?

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

Could you explain the preprocessing functions for D tasks a bit better?
Preferably with pseudocode?

I don't quite understand fanout and split fanout.

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

    I don't think I'll be able to write pseudocode that is clearer than the actual code without diverging from the original code. The point of offering you the actual tester code is to allow you to run it to answer any questions you have about it.

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

      Oh, I'm sorry, I didn't see the link to the implementation of the testing harness, that's exactly what I was looking for.

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

        Agreed, without the code that kind of description would've been quite insufficient :-)

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

Solved 1 problem to get a shot at the t-shirt... 9.6% prob so far ;) It was fun, thanks for organizing!

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

(Being careful to avoid spoilers) Are library functions allowed on the B questions? Using some (that internally dont use measuremnt or arbitary rotation) in my attempted solution. Written test code to look at what my solution does and am pretty sure the method is correct but am getting runtime error/wrong answers when submitting.

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

    In general library operations are allowed, but specifically IncrementByInteger uses arbitrary rotations, so using it is going to fail.

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

Should any of these solutions make use of multiple measurements on the same qubit to obtain a probability or are all solutions expected to be deterministic?

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

    I expect some of the solutions can be non-deterministic.

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

      Can be or should be? I'm a little stuck on some of the A problems, so it would be helpful to know what path to take.

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

        Please read the problem statement — it has a lot of relevant information.

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

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

Is an 'In queue' status normal for a submission for extended periods of time? I've had a submission stuck for close to half an hour now. The uncertainty is killing me — although,I should have known that uncertainty is a part and parcel of quantum computing.

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

    im getting this also, guessing something is up with it

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

    This was because the div2 round / system testing taking priority (shouldn't have to though).

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
How can I solve this error? I'm facing with this error when I'm trying to Reset a free qubit.
error QS6312: The called operation does not support the necessary functor(s) for the requested auto-generation of a specialization. Missing support for functor(s) Adjoint, Controlled.
error QS7112: Executing the transformation for the compilation step "Functor Generation" loaded from "/Users/mozafari/.dotnet/tools/.store/microsoft.quantum.iqsharp/0.11.2006.403/microsoft.quantum.iqsharp/0.11.2006.403/tools/netcoreapp3.1/any/Microsoft.Quantum.QsCompiler.dll" failed.
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Reset includes a measurement, and you can't generate adjoint of an operation that uses measurements. In this case you should write your code in a way that doesn't use measurements.

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

Is there a good way to estimate the running time of a program with respect to the transformations performed?

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

    You can do basic complexity estimates such as "exponential in the number of qubits" vs "linear". But the exact execution time of the solution on Codeforces depends not only on your solution but also on the testing harness, so I don't think there's a better way to get precise runtime other than try it.

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

When the question says "You are allowed to apply the given operation and its adjoint/controlled variants exactly once.", does that mean once each for the operation, its controlled variant and its adjoint variants(for a total of 3) or does it mean you can only apply the operation once and it can be either the operation or one of its variants? Also what error can we expect to see if we don't adhere to this?

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

    from the practice rounds, it should be that you can only apply the unitary/its variants once in total.

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

Can we use Ry for C1?

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

    From the problem statement:

    You are not allowed to use any gates except the Pauli gates (X, Y and Z), the Hadamard gate and the controlled versions of those

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

Is it rated?

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

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

    pull your kata git repo from upstream to sync it to the latest version, or if you just downloaded it previously just re-download and replace it

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

Why is Q# such a terrible language to write in? I feel like compared to Qiskit and PyQuil I have to spend more time trying to stare at documentation and debug random syntax related things.

A few suggestions to send up to the Microsoft folk: 1) Deprecate the Reset function. Instead let the program do "automatic garbage collection" in the sense where the programmer does not need to clean up after the qubits it allocates. I realize that this might be challenging, as C++ and some related languages have the functionality of pointers, which don't really allow for easy automatic garbage collection.

2) Controlled (insert Gate here) feels super clunky to use. You need to declare the control bits in an array, even if you intend to only have a single control bit. Also, I wanted to use a controlled version of a gate for one of the problems, but it took me forever to figure out the syntax, cuz I kept getting compilation errors around it.

3) Are you able to use * and / operators in Q#? I feel like you cannot and need to use the operations located in the Microsoft.Quantum.Math library, which again is super clunky.

Maybe I'm just a noob and I don't see how this is advantageous compared to the other languages, but those are my two cents.

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

    1) Reset function is a measurement, and you can't use measurement if you want your operation to be invertible. The language can't know your intentions, and even if it can — it's better when the programmer is aware of his own intentions. Also there are classical languages without garbage collection, in general they are much more reliable.

    2) I don't see a problem in the putting [control_qubit] instead of control_qubit as an argument. Supplying the array of control qubits is just a more unified syntax.

    3) You can use it for numbers, but you can't multiply operations.

    Q# has its own downsides and limitations, but any classical language that is closer to a hardware has them in comparison to high-level languages like Python.

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

      Q# has its own downsides and limitations, but any classical language that is closer to a hardware has them in comparison to high-level languages like Python.

      One problem is that developing a good, usable and well-documented language is difficult and time-consuming. If you participated in the 2018 Q# contest here, you can see how significantly Q# evolved. And probably you can see how much it can/has to evolve further.

      That said, it is not clear why Q# does not simply extend an existing well developed language (even C# or F#). Ideally, it could even be an external program with bindings for various languages (though in this case the mixture of classical and quantum computations is impossible to analyze in compile time).

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

        We actually started with extending F#, but it turned out to be a lot harder to analyze the code in this case. There is a blog post that talks about the history a bit here.

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

    3) the problem is that Q# doesn't have type coercion, so instead of PI() / 2 you must use PI() / 2.0 so both arguments are Double.

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

Please Help, how do you declare a controlled gate. like for instance, I want to use a controlled version of the given unitary gate.

Do I do (Controlled unitary) ([control bits], inputs)?

I'm getting an error when I try this.

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

    Controlled unitary ([control bits], target bit) should work

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

    If there are many inputs (like for rotation gates), you have to use a tuple for arguments:

    (Controlled Rx)([controls], (angle, q));
    → Reply
»
4 years ago, # |
  Vote: I like it +126 Vote: I do not like it

Congratulations. With this contest, you've convinced me that quantum machine learning is garbage that will never get off the ground.

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

    It put a real damper on the contest for me as well. It made me perversely happy to see the top 50 fill up with people with 17-18 solutions, because it meant I could just give up on the ML questions without feeling like I'd given up early. Fingers crossed that next year won't contain problems like that.

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

      It's not just the time/effort thing, but the fact that we're classifying trivialities and if even that's tough to train, real-world data will be impossible.

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

    Although I do agree that the questions were somewhat annoying they could (atleast some of them) be done without having to blind guess architecures in the air if you observe things carefully. Also I think people in the 80s-90s said the same about classical ML too and now look where we are.

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

      ML was missing datasets back then. QML isn't missing datasets anymore than classical ML.

      They can be done without doing anything with architectures, that's part of the problem.

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

    Making decision about the whole QML based on a very specific tasks ... weird.

    The thing is that Q# ML library is very young, it was clear after the warmup. I personally didn't use it, and wrote my own training routine, which worked great. Also, D1-D4 can be solved just by paper and pencil (D5 too, though it's much harder).

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

      FYI these problems will have the effect of attracting or repelling people from QML. It's the same as how the contests as a whole will affect popularity of Q# somehow or how Kotlin Heroes will affect popularity of Kotlin. Why are you shocked about that?

      Also, D1-D4 can be solved just by paper and pencil (D5 too, though it's much harder).

      Yes, that's the problem. They can be solved this way much more easily than by any sort of training.

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

    I don't believe that to be the case.

    Sure, putting it in this contest was an absolutely stupid mistake.

    HOWEVER, it has potential when used on real quantum computers.

    Remember that currently we're just emulating the quantum computer using a classical computer, and that's REEEEEEAAAAALLY inefficient. Anything with more than 10 qubits drops below a million operations per second. But with a true quantum computer you could work with dozens of qubits on billions of operations per second. That's when quantum machine learning will really shine.

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

      I just don't see that potential so far. When I compare beginner-tier classical ML with this, you can easily train a small network on a small dataset, with the only drawback being lack of precision from either overfitting or underfitting because both the network and dataset are small. You can eliminate that when you're not a beginner. In here, on the other hand, encoding even linearly separable data into anything other than total chaos is a challenge, even with a small network.

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

      It's not yet clear that there is potential when used on real quantum computers. A lot of the results of the past few years in quantum computational complexity research have been "They are no more powerful than classical counterparts."

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

        Are you talking about equivalence of BQP and P complexity classes? I don't think they have been proved to be equal right? Also just because the complexity classes are the same does not mean they are no more powerful.

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

          Yeah, I wasn't very precise with my words. We are quite far from being able to prove or disprove BQP = P. We can't even prove P != NP yet. What I meant was, specifically with regards to quantum machine learning, after the initial discovery and excitement in the earlier part of this decade, there followed a bunch of papers showing that what were originally thought to be exponential speedups were in fact "only" polynomial. You might've heard of Ewin Tang's result. "No more powerful" is a bit of an exaggeration. After all, polynomial speedups are still pretty significant. But the actual advantages will be tempered by the availability of reliable qubits, ability to load data into amplitudes of quantum states, and other caveats. (See Scott Aaronson's "Read the Fine Print" paper for more details.) So, quantum computers might still be able to help in machine learning, but not in as drastic a way as most people imagine.

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

    Next time, Microsoft should allow us to use their quantum computers. My poor ol' classical computer is very tired after all the circuit training.

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

    I guess if we just implement all gates, states with backprop etc. just like in classical ML we can get the things working, but anyway, it's no longer 'quantum' :/ You don't backprop in your quantum computer.

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

Are all solutions rejudged after the contest? Or the current verdict is final?

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

    update: I think they didn’t rejudge solutions.

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

    Yes, the current verdicts are final.

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

Is it possible to create an operator from arbitrary unitary matrix in Q#?if so, how? meaning, I have a unitary matrix U , and I want to apply it on some register.

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

Failed to get a T-shirt, working out E2 but defeated by the final two ML problems. Maybe I have started too late...

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

How to solve QFT root? Managed to solve it adhoc for 1 and 2 qubits (any root power), then gave up.

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

    Maybe arxiv 0810.3843 can help.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 5   Vote: I like it +20 Vote: I do not like it

    It's actually quite neat and figuring it out at the last moment was really fun.

    Observe that QFT when applied four times is the identity operation. Thus the eigenvalues are the fourth roots of unity.

    Now we will use phase estimation. Supppose that the input register is an eigenvector of the QFT operator. Apply phase estimation using two ancilla qubits in the storage register (this is sufficient to store with exact precision). Use a subroutine for phase estimation as we would have to apply adjoint and reset the ancilla qubits.

    Now apply R1 gates on the storage registers so that the entire system is multipled by the pth root of the eigenvalue of the eigenvector (this is easy to do by simply using R1 gates that add the corresponding angle which is influenced by a qubit of the storage register). Now simply apply the adjoint of the subroutine to reset the ancilla qubits. The above procedure for an eigenvector will precisely output the value given by the pth root of QFT on application to this eigenvector. However since QFT is diagonalisable there exists a basis of our input state composed of eigenvectors and therefore this operation is precisely the pth root of the quantum fourier transform!

    One alternative direction that I was going for (but could not make much progress in) was that QFT^3 satisfies the cube root, QFT satsifies the 5th root and QFT^3 satisfies the seventh root. Thus it sufficies to find the eighth root only although I could not do it. The above solution is far neater and general and infact applies to any quantum operator that when applied four times gives the identity operator.

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

      Well done! I think this is actually a more natural way of solving it than the published one (https://arxiv.org/abs/quant-ph/0208130).

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

        Thanks! Although I should not take all the credit, there was a problem sheet froma CS course on quantum computing that had defined such a procedure for finding square roots which I then generalised. I must say though that the literature for the fractional quantum fourier transform is quite limited which made this even more challenging

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

      Does this work in general, even when the operation isn't periodic, as long as the unitary is diagonalizable and you capture the phase with sufficient precision?

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

        No, check this excellent explanation https://algassert.com/post/1710

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

          This apply-fractional-power-by-phasing-the-phase-estimation trick is very general. It works on any operation amenable to phase estimation. The trick worked on the QFT because the QFT has a nice small evenly-spaced set of eigenvalues, but it also works if you have some way to apply large integer powers of an operation (and a non-zero tolerance for errors). It is very much a tool worth keeping in your toolbox.

          Sounds more like "yes" than "no" to me.

          → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

answered.

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

    Try running your solution a couple of times (but not in Custom Invocation: it caches the result) and you'll see that the output is random.

    I built the equivalent circuit in Quirk, and in both cases (R1 and Rz) you end up with the same state.

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

Despite Solving 17 Problems, I missed out on the Tshirt. :(. QML took too damn long. I think they should have given the paper link to help us solve E2.

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

    If that was done then it would have become speedforces again. As it is there are 33 submissions of E2.. So I guess it was justified

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

Thank you Nickolas and the codeforces community for answering my often times 'stupid' questions. Overall, I had fun working on the problems. :)

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Can someone explain the idea behind B2? I know that there is an equivalent condition:

  • let's call the number of set bits on even and odd positions $$$e$$$ and $$$o$$$.
  • then, the number is divisible by 3 iff $$$abs(e-o)$$$ is divisible by 3.

And since $$$e$$$ and $$$o$$$ are $$$O(log_2(N))$$$ of the original number, we can then just use brute force (I think the possible absolute differences are between 0 and 4).

My implementation: 84683768. Subtracting two quantum registers is very painful, because Q#'s standard library operation for some reason does not define Ctl, so you need to do this manually. I did a stupid trick of first figuring out which one is larger, and then doing either $$$e-o$$$ or $$$o-e$$$ in a "semi-classical" way. This doesn't work for some inputs, like 80, and I have no idea why :(

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

    There is an explanation on how to increment a 2-qubit register mod 3 in the tutorial to an earlier contest (see here, task C3). So you can just increment mod 3 at set even positions and decrement at set odd positions and then check if that register is 0.

    (Like this: 84358532)

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

      I see, thanks. So it's basically B1 combined with C3 from 2019. I should've checked the previous years, it's a bit annoying that they build upon the previous contests like that.

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

    I used a lookup table to count the number of odd/even set bits modulo 3 (4-to-2 bit map, 11 ControlledOnInt calls). Then (2x2)-to-1 bit map to subtract modulo 3 (accepts 0-0, 1-1, 2-2, so 3 calls to ControlledOnInt).

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

    Theres a simpler but less efficient method of a mod 3 counter, which is to initialise a 3-qubit ancilla as |100> and shifting the register left on a 1 and right on a 0. This can be done using two airs of controlled SWAP gates. Then, the first ancilla will be a 1 if the difference is 0 mod 3, and you can do a CNOT on the output qubit based on that

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

I'm really interested in knowing whether there is a paper approach to D5 like there are for the other four questions (paper approach as in we find the state after preprocessing using the four ways given through which we can find what kind of boundaries we obtain, we can obtain circle, ellipses, lines and hyberbolas (centered at origin though))

I found out that D5 was a circle with a shifted origin and I tried to shift origins by using controlled PauliY operations with the first qubit as the target but it just didn't work. Did anyone do it this way?

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

    Yes, I did it analytically.

    Add the features a and b to the set, getting the state a|00> + b|10> + x|01| + y|11>.

    Now apply two "controlled Y" operations to mix the a/b with the x/y. You can get it so that measuring 1 on the last qubit will give you probability ((x-a)^2/2 + (y-b)^2/2)/N^2, where N^2 = a^2+b^2+x^2+y^2.

    Unfortunately, this won't work with probability set to 1/2 because the quadratic terms will cancel out. But remember about the bias term! With bias, the equation becomes

    (x-a)^2/2 + (y-b)^2/2 = (1/2 — B) (a^2+b^2+x^2+y^2)

    With some annoying algebra, you can find a,b,B to make that the circle you want.

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

    I'm sure it's possible, it's just hard.

    I unfolded the solution I managed to train with ML into a matrix and applied it to the input, and what I got was indeed the equation for a conic section, so I presume every conic section can be classified with a 2-qubit quantum circuit and the right number prepended to the (x, y) vector.

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

Hi, Guys

Now, when the solutions became open for participants, I'd like to open a question about two participants They are https://mirror.codeforces.com/profile/Yash57 and https://mirror.codeforces.com/profile/ElProfesor._. (23rd and 25th place) Even during the contest they were uncertain for me, because they had very similar timings of solving. (For example, E2, E1 and D4 were solved with the difference of less than 3 minutes.

After their codes were opened, I could see, that the solutions of the task are similar, too For example, for D4 https://mirror.codeforces.com/contest/1357/submission/84614237 and https://mirror.codeforces.com/contest/1357/submission/84614189 are solved without any differences (even in any symbol, which is not easy). Speaking about E2 problem (the most difficult, as for me), they have the similar solution now, too! (The difference is the names of variables and number of enters). Everything else is similar again!

https://mirror.codeforces.com/contest/1357/submission/84571235 https://mirror.codeforces.com/contest/1357/submission/84571240

These solutions were sent with the difference of 5 seconds! (I cannot explain, how this could be without the fact, that they wrote together)

And as the information in their pages says, they played in one team at CF, so they know each other.

I think, that it is unfairly, that both of them will have a T-shirt Thank you

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

    Nickolas, Mam, please have a look at them. They seem to have done cheating.

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

      i_blinnikov, you are definitely right. I have more such examples from top 50.

      Let me tell you all.

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

        Oh really? Legendary_Grand_Master Please tell! Please also tell how you texted people to cheat off from them and when they denied you shamelessly tried to insult them because you don't know what hard work means.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it -21 Vote: I do not like it

          You (the fake account of one of the users I reported here).

          Don't try to get on me with this? I already knew in the middle of the contest, that the following people have cheated and I told the same that if you can share code with your friends then why don't you distribute among all the users. If they were not guilty then you can see the conversation that most of them even didn't replied.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 3   Vote: I like it +10 Vote: I do not like it

            Get your English right first, entitled lady. Also, I'm not a fake account of anyone you think. Just wandered around after one of my friends exposed your dirty talks. I don't know to how many people you went around asking that shamelessly. Also, they couldn't care less. Come again, which jhunjhunwala college were you from?

            → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -53 Vote: I do not like it

    One very important thing I noticed is that these 3 users had their submissions common for problem D5.

    They all cheated, you can check other people solution differ so large and their differs only by some numbers which they changed accordingly to beat MOSS.

    Users are: geekpradd vibhav011 wall_of_fire

    D5 Submissions of all three respectively: 84581263 84579654 84623603

    Nickolas, mam please check them and disqualify them, here are people who tried all the questions themselves even if they didn't land in top 50. These cheaters should be disqualified for all further Q# competitions.

    It's my request to all who codeforces users to check if other also did the same. No cheater should get praised for what they haven't achieved.

    It's better to score 0 but with your efforts than to score 100 by some other's efforts.

    i_blinnikov thanks for taking this step and bringing cheaters in front of community.

    Please report others cheaters if left soon.

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

      RIGHT, ABSOLUTELY RIGHT. Like you texted people so that you could cheat answers off them? "It's better to score 0 but with your efforts than to score 100 by some other's efforts." Such hypocrisy. No?

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

      This allegation is extremely serious and is WRONG. D5 I TRAINED ON THE HALF MOONS CODE GIVEN BY MICROSOFT. This code is available online and I trained my classifier using this. If the above person had ever done any Q# she would know. Also the above person was asking me for code which I blatantly refused to give and I guess she is trying to take it out. Proof here:!

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

        Can confirm, the half-moon classifier is publicly available

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -50 Vote: I do not like it

        Very nice use of inspect element to change the username, how far can you go for cheating?

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

          SERIOUSLY? Codeforces please go through my messages. I am allowing codeforces to go through my chats to see this. I am extremely saddened by this. I learnt so much in the last three days and all this to end this way not only makes me want to not participate anymore but also makes me feel really sad about humanity. I have nothing else to say.

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

            Do not get affected emotionally by other people so much and stay motivated :) Btw, may I ask where did you learn about quantum computing? I think that maybe there are good resources other than Q-katas, but I failed to find a really comprehensive but still intuitive one while busy preparing for finals :D.

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

              Thanks for the words man. Actually I had taken a summer reading project on Quantum Computing under my institution where I read most of the quantum computation part of Nielsen and Chuang so I had the theoretical background needed.

              I had not really heard of Q# until I saw the announcement on Codeforces after which it was mostly a matter of solving the past problems and getting a hang of the language. I did not really use QuantumKatas other than for the Quantum Machine Learning which is something I saw for the first time in the warmup round.

              I would say it would be better to read Nielsen and Chuang and also watch the video lectures in the Berkeley Quantum Computing course on EdX (I think it started last week again) and also the MIT course on OCW. There are also some cool projects and questions uploaded in the CS269Q course by Stanford.

              It seems to be that quantum programming (atleast now) is less of programming and more of the theoretical science behind it which in a way makes it even more fun.

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

                I am quite interested in this field and will read the resources. Thanks for your quantum information!

                → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -45 Vote: I do not like it

        Give me one reason that all the top 20 people have distinguishable code at a glance for D5 problem and how magically, unwantedly or coincidentally all three of you have very similar code seeming in a single glance.

        I would rate this coincidence abnormal or unnatural?

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

          HALF MOONS IS THE TUTORIAL CODE USED BY MICROSOFT. I SAY NOTHING ELSE.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it -29 Vote: I do not like it

            Hmm, so unnatural coincidence between students from same college make their code look similar.

            You think people will believe this coincidence.

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

              Before posting something you should go and do some research (if you are even capable of it). The circuit architect we used is used by Microsoft in their half moons example. It should come as no surprise if multiple users (even if they happen from the same college) have used the same circuit. Your ignorant comments make my head hurt. Go get a life and stop ruining others'.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                  Vote: I like it -24 Vote: I do not like it

                Listen see, I agree to the point that it may be available on web but just explain the coincidence with timings.

                I agree that I asked for code but I asked it becuase if you can share code with your friends then why not with whole community and that's why I made a fake request asking for code.

                Can you see that I hadn't participated seriously in the competition otherwise I would have solved the first questions at least as they were similar from problmes from past contest.

                I didn't said anything wrong and I didn't publicly shamed anyone, geekpradd said that codeforces can check his account for proof that I asked for code. Okay I agree that I asked but check that I havent used any slang language and I would ask codeforces to check that he used slang language and why didn't he provided that screenshot. If you people wan to be treated as people who didn't cheated then let it be. It doesnt affect me, I just said so that some deserving people get the position on the leaderboard they actually had.

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

                  If you are referring to this, here is the screenshot:

                  This is the last time I am replying to a troll like you and as you can see the way I used the above word is how people express anger in the western world. By the way you do realise that you agreed above that you messaged us while in a previous statement you said I used inspect element. Haha. The community can judge for themselves (which is evident in the way you have been downvoted)

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

              Honestly Legendary_Grand_Master, do you even know what quantum even means?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                  Vote: I like it -31 Vote: I do not like it

                You, fake account shut up and if you have the guts then come with your original account?

                Don't play the game like toddlers.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                  ← Rev. 3   Vote: I like it +3 Vote: I do not like it

                  Please stop accusing me of being a fake account when I proved how you are using a fake one to promote yourself. You can't even get your english correct, which is extremely frustrating given how you feel entitled about yourself in every aspect. Your profile says you're from some college studying CS and you don't even have the mental capacity to read editorials and solve problems which are so so similar. College mentality, you couldn't get into any of the top colleges and here you are shaming these people. I believe that they are smart and intelligent enough to not play games with fake accounts, unlike you. You also mentioned about their ranks in high school exams in their personal messages as a help. What does that show? You are clearly jealous and feel hatred.

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

        I also received email from this person asking for codes during contest.

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -22 Vote: I do not like it

      Did anyone get why the above users didn't reply on the following allegation of cheating and a third person is fighting with the one who posted the comment?

      Why didn't this competition had a plagiarism detector, I would say many have just changed variables and submitted. Like the ones listed above have a super similarity in their codes and timings.

      I think God gave them equal speed and intelligence.

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

        I have replied. Also given the fact that the QML questions can be done by hand there are not really that many solutions to it. It's extremely disheartening seeing people give such false allegations.

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

        Not a third person. That lady texted several people for code solutions.

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

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

        OH REALLY fake account who?

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

        I got a linkedin connection request from this person asking for code

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

      I find this hard to believe. This is the architecture straight from the Microsoft documentation.

      ... and their differs only by some numbers which they changed accordingly to beat MOSS.

      Do you know how machine learning works? The entire point of that problem was to train a model, meaning, yes, change "some numbers".

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 5   Vote: I like it +35 Vote: I do not like it

      I really can't comprehend how some people can be so hypocritical. As geekpradd mentioned, the code for half moon model is publicly available and I too used it for training in D5 because the graph seemed somewhat more general. Also let me show you the screenshots of chats with this person. The link v.ht/qhash redirects to a document which has the exact same questions as the contest. She may delete that so here is a screenshot of that as well: After this, I blocked her and now she is alleging me falsely for plagiarism which is a very serious matter.

      EDIT: As I predicted, the link no longer works. EDIT2: This user has changed her username : Legendary_Grand_Master

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

        She doesn't even know what she's talking about. She just cares about copying code and then after being refused publicly shaming experienced users.

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

        As I predict in 2020, I will be a legendary grand master.

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

          You do realise you have become an extremely hilarious laughing stock, right?

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

          You still sure about this?

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

      some numbers which they changed accordingly to beat MOSS.

      Jesus Christ you're a moron. Obtaining those numbers was the whole problem.

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

    Firstly, about how I solved E2, i had found a research paper with link https://algassert.com/post/1710 from where I derived the structure of required gates.

    I can provide you methods as well as solutions to each one of my solution witb my training data and everything, if that's what it takes.

    As far as shruti chandel is considered she tried to contact me via mail, linked in etc for solutions. I xan prove it with screenshots as well.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it +12 Vote: I do not like it

      Despite the second charge he made was nonsense, your evidence listed cannot convince me of not cheating. You and the other users’ solutions are too similar that’s hard to think of it as coincidence. Extremely similar code, almost same submission time, being in a team before...

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

        Sorry I confused i_blinnikov with shruti_chandel. My apologies for i_blinnikov. Sorry!

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

    The solution which you have mentioned can be proven analytically by constructing a hyperbolic graph. So the parameters can come out same. Thats all I want to say about the solutions you have linked.

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

      We all know sometimes there’s only one solution, but the codes are rarely IDENTICAL.

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

    Thank you for pointing this out. We investigated the suspicious cases and made some tough decisions.

    P.S. I'm so glad I don't have to do this for April Fools Contests!

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

      What's the logic in disqualifying one of the reported cheaters but not the other?

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

        Presumption of innocence: it's impossible to prove that the person who submitted the solutions first shared them with the person who submitted them second deliberately (and not had them stolen). Repeated offense will disqualify both. (This is more or less standard Codeforces policy.)

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

Any Idea, when the results of who gets the Tshirt will come out?

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

How to solve A6? distinguish I, X, Y, Z in one query

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

    Prepare a Bell state and apply the operation to one of the qubits, the result will be another Bell state which you should know how to distinguish.

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

      That's it? I can't believe I didn't get that. :') I spent pretty long on that question, too.

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

        Same. I feel like a clown reading this after hours of messing with roots of unity phases and trying to apply phase kickback.

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

    That's basically superdense coding. That Wikipedia page even has the complete implementation as a nice diagram:

    The part labelled "Sender encodes bits" is the unitary you are given, the rest can be easily implemented in Q#: 84532682

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

    Prepare (|00> + |01> + |10> — |11>), apply the unitary to second qubit, and distinguish the 4 possible resulting states. One way to come up with that is to look for a 2-qubit state |psi> such that I2|psi>, X2|psi>, Y2|psi>, and Z2|psi> are orthogonal (i.e. distinguishable) — this requirement can be written as some simple equations.

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

    Is there a way to do this without Bell states btw?

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

      I believe so, but Bell States is definitely the cleanest

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 4   Vote: I like it +5 Vote: I do not like it

        Maybe it is not possible by information theory. You need 2 bits of information to distinct 4 states. While bell state somehow allows us to copy information and do the measure again.

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

      I've tried to distinguish controlled versions on a two-qubit input at first. But my calculations showed that this is impossible.

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

        Really? I had initially thought of this as well and ended up going nowhere. Seems interesting that you proved it is impossible.

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

          I also proved it, just to get on and try something else :D

          Say you prepare a state [a b c d] first. Now arrange the possible outcomes in a matrix:

          a b  c   d
a b  d   c
a b -id  ic
a b  c  -d

          Since the first two columns are a constant apart (a/b, or one of them is zero), the set of columns can't have a 4D-span. This means the rank of the matrix is less than 4, and the rows can't be linearly independent either. So there's no way to map these states to the orthogonal four basis states.

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

            Oh, damn. I proved this too, but it was a lot of tedious calculation. I didn't think to compare columns. Obvious in retrospect.

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

Is there any reason why ControlledOnInt computes so slowly compared to ControlledOnBitString? It was giving me huge problems on B1, until I tried timing some of the operations I was using and found ControlledOnInt to be 5 times slower than ControlledOnBitString! Are there any significant differences in the implementation that would lead to such a difference in runtime?

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Suppose we have a unitary implemented as Z, for "distinguish" problems like A7:

operation unt(qb : Qubit, tp : Int) : Unit is Adj+Ctl {
  if(tp == 1) {
    Z(qb);
  }
}

How do we introduce a phase, like -Z or (-i)I?

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

    With the R1 operation.

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

      Thank you. Sill R1(pi) |0> is not the same as -Z |0>

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

        R1(angle) applies the shift to |1> only. If you want to apply the shift to |0> as well, you can temporarily swap |0> with |1> using X.

        So: R1(angle); X(); R1(angle); X();

        There are probably better ways to do it, but that one should work.

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

          In this particular case, you can replace R1 by Z itself. :-)

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

Hey guys how did you do B1? I'm a fool and thought just checking each number up to 2^10 and doing a controlled X with it would suffice, but apparently doing that with 10 qubits is infeasible (?). I couldn't come up with a more clever process to apply to the input/output qubits. Appreciate any insight. (This was my first contest on Codeforces and I started learning about quantum computing during the warmup round!)

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

    You can define an adder function and use its controlled form to count the number of ones in the input register. Then you can simply make use of ControlledOnInt. Here is my code for further clarification.

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

      Wow that's wild but I see how that works. Where did you get the insight for an approach like this? I'm guessing exposure to more problems and ideas like this is probably it lol. I did just the tutorials and katas up to teleportation but I didn't directly come across an approach like this. Entangling another n bits with the input bits and incrementing those is brilliant. Thanks for sharing!

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

        Increment and Decrement in the practice round was a big telltale sign that we would need to use some sort of counter in the main contest in my opinion

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

I've never learnt any quantum physics. I attempted questions just by reading the docs and practicing katas. I guess there are lot like me so can someone guide me on how to understand a whole language with no knowledge of the concept as well from the docs. I always find learning through docs boring. Can someone pls guide me in this. Thanks in advance.

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

    The only advice I got about quantum computing was from here which was "Shut up and calculate!". Lol..

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

      Unfortunately that is not really the truth xD

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

    I would say you need to learn quantum physics (atleast the mathematical treatment) and a good deal of linear algebra to even begin understanding quantum computing. Ofcourse you can solve the questions without knowing it per se (we can always use sort function in C++ without knowing quick/mergesort right?) but an introduction to the math is really necessary. I would suggest looking at the Berkeley Quantum Computing course on edX and reading the book on Quantum Computation by Nielsen and Chuang (preferably after taking a basic quantum physics course) Good luck!

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

      Thanks. Will definitely try it in my free time. Lets hope to do better in the next Q# contest.

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

    Some basic understanding of quantum physics is required, You can read the first chapter of J.J. Sakurai if you have absolutely zero background in quantum physics. After that try reading Nielsen and Chuang. No need to read the whole book, just the first five chapters are sufficient as long as contests are concerned (especially chapters 2 and 4). These will give you all the required theoretical knowledge. Then actually start to code. The only good sources of learning Q# I found are the official docs and katas. Practice all the problems of previous rounds and warmups.

    For understanding the concepts of QML, I found this paper really helpful: https://arxiv.org/pdf/1804.00633.pdf

    All the best!

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

    There is a course by Vazirani (the man who created bernstein-vazirani algorithm). I was able to finish in top 20 after doing that course, then the katas and previous q# contests. I already knew quantum mechanics before, but I think you will still be able to go through the course without knowing it. You will also get to learn some quantum mechanics, and trust me it will blow your mind. All this took less than a month

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

As for ML training, I must say that the default loss function as described here https://arxiv.org/abs/1804.00633 is somewhat weird. It's just MSE — mean squared error. But the output of a model is biased, i.e. it lay in the interval [b, 1.0+b], while the actual label is 0 or 1. So MSE is not the greatest choice.

My idea was to introduce a sigmoid at the model output, so the output will be in [0.0,1.0].

The problem is that you can't tweak the actual Q# ML training lib, so I implemented equivalent code in Julia. You can see a first version of it here https://github.com/dandanua/QML, I wrote it after the warmup. The new version is messy and not yet uploaded, but conceptually I just incorporated method encoding from the new tasks and also my training learns an encoding params alongside model params.

A little bit hacky, but at least this is not a pure analytic approach to the solution of D tasks :)

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

    Wow this is really impressive! How are you running it on Julia though? I don't think there is any quantum simulator that uses Julia? And Q# also does not have Julia bindings.

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

      Julia is a general purpose language, mostly designed for technical computing. You can multiply matrices in it very fast :) For the most quantum tasks this is enough and you don't need some sophisticated emulators.

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

    Another odd thing is that the paper incorporates bias in the cost function, but the library implementation does not. If I understood the code correctly, bias is learned by taking an arbitrary point on the interval of least misses in the current implementation (using a suboptimal version of golden-section search, where sorting would suffice).

    Overall the implementation uses misses instead of the cost function in a lot of places, which I don't think statistically makes much sense.

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

      Using misses in the cost function is just ridiculous and hardly can be called Machine Learning at all, it's more like Machine Guessing.

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

when will the random T-shirts winners for the contest be announced?

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

    From the rules:

    ... prize winners will be selected ... within 7 days following the Entry Period.

    Give us a bit of time :-)

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

I tried to solve B1 with n/2 extra qubits, https://mirror.codeforces.com/contest/1357/submission/84461367

I prepared a state of n/2 |1>'s and then applied a Controlled X on the output as a target. However this approach timed out every time I tried, any idea how to get this Accepted or a better approach ?

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

    n/2 extra qubits is too much for the simulator to handle in time, instead you should be keeping a small register that counts the number of 1's in the string. 1 extra ancillary qubit is just enough if you use that in combination with one of the given input qubits. This will give you a mod 4 register, allowing you to handle N <= 6 easily. For N=8 and N=10, there will be some input sequences which will give you false positives (eg 0111111111 will give the same count as 0000011111) and you will have to take care of them separately, but this method will get the runtime down to between 1 and 2 seconds

    Edit: I stand corrected by the editorial. I though 4 ancilla would be too much, but my problem was using an inefficient implementation of Increment

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

Time to finally explain in detail what's wrong with this "machine learning".

Problem one: the datasets are trivial and classification is a question of learning to preprocess — but why would you do that when you can already preprocess by hand? We don't use neural networks to implement cosine either, we have the math behind it and can use it to get the result faster with great precision. These problems reduce to "make a quantum circuit that will implement simple classical math operations" only because custom preprocessing isn't allowed. That, by itself, is incredibly unrealistic, since in real ML, choosing a custom preprocessing method is as important as the right model to train and the right objective function. ML is used exactly for the kind of problems where the input distribution is complicated enough that we can't just look at it and decide what function will split them into 2 classes.

One partial fix would be to not "market" it as ML, but as "find a circuit that will transform this distribution in an optimal way". That still doesn't change the fact that we're unnecessarily kneecapped by not allowing custom preprocessing, which solves the problems more simply and efficiently.

Problem two: With regular ML, you make some dumb shit and let it learn from one fixed set of initial parameters, only to sometimes discover that the precision doesn't drop below some % (underfitting = use a bigger model or that performance on the validation dataset is too high (overfitting = use a smaller model or regularise better). Either way, you can always see something going on unless you have a big dumb bug. Here? I had huge problems forcing the training to give me a different result than "found nothing better than your initial parameters", even in the first problem in the warmup contest when learning that one PauliY rotation described in the tutorial! That's not supposed to happen, there's a clear gradient to follow there! The differences were sometimes in decreasing the learning rate or number of epochs, which should affect the quality of the final result, but that result should be better than a fixed random starting point all the time, not sometimes. This ML library is broken.

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

    I agree with the sentiment that the problems feel artificial and convoluted, but I think the contest organizers could be given some slack. QML doesn't offer anything new to ML other than (dubious at the moment) speed when ran on real quantum computers. And unlike the other quantum tasks, you don't really need any "quantum thinking" to achieve those (again, dubious at the moment) speed improvements, at the level of abstraction offered by the QML library. Since quantum computers don't exist yet, there's a problem of how to "force" the contestants to use the quantum library, even as classical approaches are much more powerful (at the moment, maybe). Allowing custom preprocessing ruins everything, as you can just train a classical neural network beforehand, and preprocess all the data into 0 or 1 and have empty quantum circuits. So a certain degree of "unrealisticness" and "unnecessary kneecapping" is unavoidable, I think. As machine learning tasks, the tasks in this contest were bad. But as tasks that introduce the QML library, they were ok.

    The QML library needs work though, I agree. I even encountered a bug in the library. Perhaps, it is simply too early to start marketing QML to non-QML researchers. (And this isn't the first time Microsoft got ridiculed for being a too early adopter.)

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

      The fact remains that it's always practical to do preprocessing by hand and only use ML when you can't distinguish any more important properties of the given data. Sometimes you even have one classifier (manual or trained) and then use different NNs based on the class of the data.

      I'm giving the organisers some slack in not complaining that in E2, implementing the algorithm from the right paper was the way to go, rather than thinking about it. At least you need to understand what's going on and it inspires more ideas, so that's fine. There was a lot of nice problems that can't be solved without quantum stuff and without thinking, but I can't help but complain about D because there was no learning involved in that ML.

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

        Well, for me, I came up with a solution to E2 myself. I only used the fact that Fourier transform's eigenvalues are $$$\pm1$$$ and $$$\pm i$$$, which you should already know if you solve E1.

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

          Yeah, it was possible to figure out and I don't mind too much that it was in papers since that still required some work.

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

    The main problem with this "machine learning" is that it is fundamentally limited, that is, there is no analogue of universal approximation theorem for those models. In my post, I've explained exactly which functions such a model can recognize and what is changed by classical preprocessing.

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

      Glad you agree that Ds are bad. It's even worse since it has a problem learning one rotation (D1), giving the exact same parameter on the output as it gets on the input unless the lr/epochs are large enough, which should never happen.

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

Is this a bug or did I miss something? Nickolas

This is for problem D3.

No rotations (gets WA): https://mirror.codeforces.com/contest/1357/submission/84380572

1 useless rotation which should be equivalent (gets AC): https://mirror.codeforces.com/contest/1357/submission/84380482

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

We have published the editorial and finalized the contest results. I have also read through the comments, and will try to take them into account for future.

Congratulations to the T-shirt winners, and I hope to see you in the future contests and events!


T-shirt winners in the main contest (top 50 + 25 random participants outside of top 50)
T-shirt winners in the warmup round (25 random participants who didn't win a T-shirt in the main contest)
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    Thanks,Its too excited for me to win a T-shirt for the first time!

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

      Me too, this boosted my moral(especially after two last contest in which i really did bad) to practice more and become better, contest itself sparked my interest in quantum computing in general, very nice experience! Hopefully i become better at cp and do much better next year and be in top 50 :) P.S. can someone point me to some info on t-shirt prizes i have no idea how to provide info or process of it, thank you in advance and thanks for interesting contest!

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

    It was a great contest, even if I'm a little sad to don't win a t-shirt, let's try next year ! Thanx !

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

    We ran into several new and interesting issues with the T-shirt shipping this year, so I'm afraid it will take at least another two months for them to make it to the winners :-(

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

      Any update?

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

      Any update?

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

        Hello! In the process of making gifts and receiving them, we faced great difficulties. We have put in a lot of effort and are now happy to announce that we are already close to start sending gifts. We wrote about this to the winners. If you suddenly didn't receive such a message, please write me a private message and I will try to fix everything. We all really want all the winners to receive their gifts!

        → Reply