Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

By Nickolas, 3 weeks 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

»
3 weeks 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?

  • »
    »
    3 weeks 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 :-))
    • »
      »
      »
      3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
Rev. 3   Vote: I like it -17 Vote: I do not like it

F

»
3 weeks 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!

»
3 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

This contest uses Q# language?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Solutions are accepted only in Q#.

»
3 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

the T-shirt seems beautiful.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

nice shirt, but ironed would look better xD

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the shirt design supposed to represent?

»
3 weeks 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.)

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

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

»
3 weeks 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

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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;
          }
      }
      
      • »
        »
        »
        »
        3 weeks 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?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No, I even tried on a different browser.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Okay, it's working now.

»
3 weeks 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?

»
3 weeks 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.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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 :-)

»
3 weeks 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!

»
3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks 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?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +38 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, How we can express a negative control in Q#?

»
3 weeks 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.

»
3 weeks 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.
  • »
    »
    3 weeks 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.

»
3 weeks 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?

  • »
    »
    3 weeks 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.

»
3 weeks 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?

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In E2, shouldn't the solution applied p times be equivalent to QFTLE(LittleEndian(qs));?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we use Ry for C1?

  • »
    »
    2 weeks 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

»
3 weeks ago, # |
  Vote: I like it -32 Vote: I do not like it

Is it rated?

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How can we perform custom preprocessing other than given 4 modes from the available modes given on Problem D3 onwards(Quantum Machine Learning)? As I wanted to try other methods to my model but I think it will change model parameters and might get a higher error on the test set.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even if you will invent a better preprocessing — you won't be able to submit it. You have to pick the mode and find the parameters for it.

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

  • »
    »
    2 weeks 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

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

      Thanks, but I moved my comment here since it was more related to the Warmup and Editorial.

      Yeah, I deleted the older version Microsoft.Quantum.Standard::0.10.1910.1804-beta from my .nuget folder and the katas work now.

      Edit: I think it might have happened because I ran conda install -c quantum-engineering qsharp which may have found an older version.

»
2 weeks 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.

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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).

      • »
        »
        »
        »
        2 weeks 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.

  • »
    »
    2 weeks 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.

»
2 weeks 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.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    2 weeks 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));
    
»
2 weeks 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.

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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.

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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.

  • »
    »
    2 weeks 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).

    • »
      »
      »
      2 weeks 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.

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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.

    • »
      »
      »
      2 weeks 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."

      • »
        »
        »
        »
        2 weeks 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.

        • »
          »
          »
          »
          »
          2 weeks 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.

  • »
    »
    2 weeks 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.

  • »
    »
    2 weeks 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.

»
2 weeks 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?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    update: I think they didn’t rejudge solutions.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, the current verdicts are final.

»
2 weeks 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.

»
2 weeks 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...

»
2 weeks 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.

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

    Maybe arxiv 0810.3843 can help.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I use it too,but failed on the precision problem. I dont know how to make the ancilla exactly reusable to avoid runtime errors.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You probably have not quite correct implementation.

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

          What do you mean by precision? Did you apply the middle gate between the two ancillas with insufficient precision?

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes,I mean that the precision of diagonal unitary between controlled qft. Also, I JUST find that CF provides competitors codes after the contest is over. Thanks for replying me.

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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).

      • »
        »
        »
        »
        2 weeks 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

    • »
      »
      »
      2 weeks 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?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          2 weeks 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.

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

            I have to think about generalizing it more carefully. My feeling was that being a root of identity operation was crucial.

            Anyway, this method worth a further research :)

»
2 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

answered.

  • »
    »
    2 weeks 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.

»
2 weeks 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.

  • »
    »
    2 weeks 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

»
2 weeks 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. :)

»
2 weeks 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 :(

  • »
    »
    2 weeks 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)

    • »
      »
      »
      2 weeks 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.

  • »
    »
    2 weeks 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).

  • »
    »
    2 weeks 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

»
2 weeks 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?

  • »
    »
    2 weeks 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.

  • »
    »
    2 weeks 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.

»
2 weeks 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://codeforces.com/profile/Yash57 and https://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://codeforces.com/contest/1357/submission/84614237 and https://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://codeforces.com/contest/1357/submission/84571235 https://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

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh really? shruti_chandel 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.

        • »
          »
          »
          »
          »
          2 weeks 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.

          • »
            »
            »
            »
            »
            »
            2 weeks 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?

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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?

    • »
      »
      »
      2 weeks 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:!

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

        Can confirm, the half-moon classifier is publicly available

      • »
        »
        »
        »
        2 weeks 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?

        • »
          »
          »
          »
          »
          2 weeks 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.

          • »
            »
            »
            »
            »
            »
            2 weeks 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.

            • »
              »
              »
              »
              »
              »
              »
              2 weeks 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                2 weeks 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!

      • »
        »
        »
        »
        2 weeks 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?

        • »
          »
          »
          »
          »
          2 weeks 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.

          • »
            »
            »
            »
            »
            »
            2 weeks 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.

            • »
              »
              »
              »
              »
              »
              »
              2 weeks 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'.

              • »
                »
                »
                »
                »
                »
                »
                »
                2 weeks 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks 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)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I may be a cheater but the above user is too. I can bet

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

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

              • »
                »
                »
                »
                »
                »
                »
                »
                2 weeks 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  The OP judged me by my CV. So I said that ranks doesnt matter, as it does not show only your intelligence. It shows your hardwork + luck + intelligence + problem-solving..

                  People are stupid to judge people by IQ. You cannot do farming like a farmer and he cannot do CP like you unless you both gain the skills required.

                  Please stop all this nonsense.

                  That peopel from high-rated colleges are only smarter.

                  Okay, let's take the challenge who gets to GM first.

                  Again see that I am mot judging by this..

                  I am just saying that with equal hardwork a non-premier college student can get same results as a student from premier college.

                  Everyone has equal sized brain, it's just how we train it.

                  Now, don't waste my time. My road to GM starts this moment.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Do you know why, I upvoted this comment because this is the comment which ignites the fire in me to do better than so called top-level college students.

                  Would getting judges by marks right?

                  Would getting judged by looks right?

                  Would getting judged by financial or social status be right?

                  You keep CP aside and first learn personal ethics and then do CP.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  There are a lot of students who despite not being from IITs and other top colleges shine in this domain. So by all means, you can do this too if you try hard enough. But please do not lecture known and established members of the CP fraternity about ethics. After seeing those screenshots, it's clear you should be the last person to say anything about ethics. Just stop. You have single handedly absolutely decimated the average IQ of Codeforces. (PS I'm not a fake account, just another CP noob as of now)

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

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

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it -15 Vote: I do not like it

          I agree that I was cheating but that doesnt change the fact that above people also tried cheating.

    • »
      »
      »
      2 weeks 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.

      • »
        »
        »
        »
        2 weeks 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.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

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

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          This one is fake, in my whole talks I checked I asked some user but statement shown in statement was not asked by me. Good use of inspect element by a fake account of the people I listed above. They all are now downvoting me and making this false screenshots.

          P.S. I am not saying that I didn't asked I am just saying that it not intended actually for cheating, it was to make them feel how sharing code with friends and community is nothing different. they had no problem sharing it with friends but they had problems sharing it with community.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +29 Vote: I do not like it

        OH REALLY fake account who?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 weeks 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".

    • »
      »
      »
      2 weeks 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

      • »
        »
        »
        »
        2 weeks 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.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

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

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I am extremely sorry to the whole CP community, contest organizers and especially the coders who I argued with.

    • »
      »
      »
      2 weeks 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.

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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...

      • »
        »
        »
        »
        2 weeks 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!

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    both the users seems to have some alphanumeric code in their name at the same time coincidentally the same way geekpradd and his friends coincidentally had the same code.

    This was last message from the upcoming GM.

  • »
    »
    13 days 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!

    • »
      »
      »
      12 days 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?

      • »
        »
        »
        »
        11 days 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.)

»
2 weeks 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?

»
2 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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.

      • »
        »
        »
        »
        2 weeks 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.

  • »
    »
    2 weeks 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

  • »
    »
    2 weeks 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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I believe so, but Bell States is definitely the cleanest

      • »
        »
        »
        »
        2 weeks 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.

    • »
      »
      »
      2 weeks 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.

      • »
        »
        »
        »
        2 weeks 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.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Those four controlled versions must rotate some state to a four distinguishable states (pairwise orthogonal). But if you write down the equations for a general state you can deduce that they are incompatible.

        • »
          »
          »
          »
          »
          2 weeks 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.

          • »
            »
            »
            »
            »
            »
            2 weeks 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.

»
2 weeks 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?

»
2 weeks 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?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    With the R1 operation.

    • »
      »
      »
      2 weeks 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>

      • »
        »
        »
        »
        2 weeks 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.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can use rotation around I: R(theta,PauliI) is equivalent to a global phase of e^(-i*theta/2)

»
2 weeks 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!)

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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!

      • »
        »
        »
        »
        2 weeks 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

»
2 weeks 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.

  • »
    »
    2 weeks 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..

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

      Unfortunately that is not really the truth xD

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah. I think if I'd done all the Katas and understood what each of them was about all the way, I'd have been able to solve all problems except D1-D5 (didn't try them).

  • »
    »
    2 weeks 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!

    • »
      »
      »
      2 weeks 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.

  • »
    »
    2 weeks 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!

  • »
    »
    2 weeks 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

»
2 weeks 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 :)

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -21 Vote: I do not like it

      Sorry to all the users whom I argued with. I just wanted to solve all the questions and when they refused and someone stated that some of them have really cheated then I though that why they cheated and didn't gave me code.

      But I was wrong, I am sorry for my behaviour but P.S that I never used wrong words or language though I might have said that they cheated.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it -21 Vote: I do not like it

        And this is my fake account too so that's right but I made it for practising but didn't did that.

        So that's my fault.

        There was no intention to do any bad to those people I just got angry when I thought that they cheated and I was wrong.

        It was their real hardwork

        Kudos to you guys to land a great position on the leaderboard.

        Regards, Shruti Chandel

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    2 weeks 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 :-)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried to solve B1 with n/2 extra qubits, https://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 ?

  • »
    »
    2 weeks 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

»
2 weeks 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.

  • »
    »
    2 weeks 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.)

    • »
      »
      »
      2 weeks 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.

      • »
        »
        »
        »
        2 weeks 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.

        • »
          »
          »
          »
          »
          2 weeks 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.

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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.

»
2 weeks 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://codeforces.com/contest/1357/submission/84380572

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

»
13 days 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 warmup round (25 random participants who didn't win a T-shirt in the main contest)
  • »
    »
    13 days 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!

    • »
      »
      »
      12 days 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!

  • »
    »
    13 days 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 !

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wish I had received a T-shirt. And for retirees there were no discounts? :)