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
Solutionand an operation with a signatureoperation RunQsharp () : Booldefined 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:
So does this replace the
Solvefrom the practice problems and previous years? And what is the boolean you have to return? Or am I confusing things?This is not related to
Solvein the problems in any way.Solveis the interface with that testing harness.RunQsharpis the entry point that will be called, after that it's up to you what it does — it can call one of theSolves with appropriate parameters, or some completely unrelated code. (This implementation predates the@EntryPointsyntax, maybe we'll take advantage of it for the next year :-))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.
The return value seems to be kind of like the exit status in Unix. The Custom Invocation runner prints
Return value TrueorReturn value Falseto the stdout, but that's not super useful since you can simply useMessage()to print arbitrary information.F
https://quantumcomputing.stackexchange.com/questions/12466/qsharp-reload-throws-error-in-python
the T-shirt seems beautiful.
nice shirt, but ironed would look better xD
Maybe the wrinkles are a part of the design?
Maybe you're right ;D
No. Look at the shadow at the bottom.
What is the shirt design supposed to represent?
Q
The one with Schrodinger's cat is still the only good one.
I guess it's some qubit lattice (in addition to the Q).
Does Q# have a function to get current time? (If that's ok to ask during the contest.)
No. That kind of classical processing is delegated to the classical driver.
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 pointAre you defining
operation RunQsharp () : Boolin your code? That serves as the entry point.Yes.
Edit: Even if I try to run this:
This is weird, the same code runs fine for me... You couldn't have gotten a different site version, could you?
No, I even tried on a different browser.
Okay, it's working now.
Comrades, when exactly will this contest finish? At 19-00 (GMT+3), 22.06.2020?
Time and date link for or people in other time zones
Could you explain the preprocessing functions for D tasks a bit better?
Preferably with pseudocode?
I don't quite understand fanout and split fanout.
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.
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.
Agreed, without the code that kind of description would've been quite insufficient :-)
Solved 1 problem to get a shot at the t-shirt... 9.6% prob so far ;) It was fun, thanks for organizing!
(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.
In general library operations are allowed, but specifically
IncrementByIntegeruses arbitrary rotations, so using it is going to fail.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?
I expect some of the solutions can be non-deterministic.
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.
Please read the problem statement — it has a lot of relevant information.
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.
im getting this also, guessing something is up with it
This was because the div2 round / system testing taking priority (shouldn't have to though).
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.
Is there a good way to estimate the running time of a program with respect to the transformations performed?
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.
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?
from the practice rounds, it should be that you can only apply the unitary/its variants once in total.
Can we use Ry for C1?
From the problem statement:
Is it rated?
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
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.
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 ofcontrol_qubitas 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.
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).
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.
3) the problem is that Q# doesn't have type coercion, so instead of
PI() / 2you must usePI() / 2.0so both arguments areDouble.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.
Controlled unitary ([control bits], target bit) should work
If there are many inputs (like for rotation gates), you have to use a tuple for arguments:
Congratulations. With this contest, you've convinced me that quantum machine learning is garbage that will never get off the ground.
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.
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.
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.
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.
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).
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?
Yes, that's the problem. They can be solved this way much more easily than by any sort of training.
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.
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.
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."
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.
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.
Next time, Microsoft should allow us to use their quantum computers. My poor ol' classical computer is very tired after all the circuit training.
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.
Are all solutions rejudged after the contest? Or the current verdict is final?
update: I think they didn’t rejudge solutions.
Yes, the current verdicts are final.
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.
I used this Mathematica package and copied the results into Q# by hand: https://github.com/Q-Compiler/UniversalQCompiler/
Failed to get a T-shirt, working out E2 but defeated by the final two ML problems. Maybe I have started too late...
How to solve QFT root? Managed to solve it adhoc for 1 and 2 qubits (any root power), then gave up.
Maybe arxiv 0810.3843 can help.
I solved it using https://arxiv.org/abs/quant-ph/0208130
I use it too，but failed on the precision problem. I dont know how to make the ancilla exactly reusable to avoid runtime errors.
What do you mean by precision? Did you apply the middle gate between the two ancillas with insufficient precision?
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.
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).
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
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?
No, check this excellent explanation https://algassert.com/post/1710
Sounds more like "yes" than "no" to me.
answered.
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.
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.
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
Thank you Nickolas and the codeforces community for answering my often times 'stupid' questions. Overall, I had fun working on the problems. :)
Can someone explain the idea behind B2? I know that there is an equivalent condition:
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 :(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)
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.
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).
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
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?
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.
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.
Hi, Guys
Now, when the solutions became open for participants, I'd like to open a question about two participants They are https://codeforces.net/profile/Yash57 and https://codeforces.net/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.net/contest/1357/submission/84614237 and https://codeforces.net/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.net/contest/1357/submission/84571235 https://codeforces.net/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
Nickolas, Mam, please have a look at them. They seem to have done cheating.
i_blinnikov, you are definitely right. I have more such examples from top 50.
Let me tell you all.
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.
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.
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?
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.
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?
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:!
Can confirm, the half-moon classifier is publicly available
Very nice use of inspect element to change the username, how far can you go for cheating?
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.
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.
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.
I am quite interested in this field and will read the resources. Thanks for your quantum information!
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?
HALF MOONS IS THE TUTORIAL CODE USED BY MICROSOFT. I SAY NOTHING ELSE.
Hmm, so unnatural coincidence between students from same college make their code look similar.
You think people will believe this coincidence.
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'.
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.
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)
Honestly Legendary_Grand_Master, do you even know what quantum even means?
You, fake account shut up and if you have the guts then come with your original account?
Don't play the game like toddlers.
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.
I also received email from this person asking for codes during contest.
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.
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.
Not a third person. That lady texted several people for code solutions.
OH REALLY fake account who?
I got a linkedin connection request from this person asking for code
I find this hard to believe. This is the architecture straight from the Microsoft documentation.
Do you know how machine learning works? The entire point of that problem was to train a model, meaning, yes, change "some numbers".
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
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.
As I predict in 2020, I will be a legendary grand master.
You do realise you have become an extremely hilarious laughing stock, right?
You still sure about this?
Jesus Christ you're a moron. Obtaining those numbers was the whole problem.
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.
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...
Sorry I confused i_blinnikov with shruti_chandel. My apologies for i_blinnikov. Sorry!
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.
We all know sometimes there’s only one solution, but the codes are rarely IDENTICAL.
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!
What's the logic in disqualifying one of the reported cheaters but not the other?
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.)
Any Idea, when the results of who gets the Tshirt will come out?
How to solve A6? distinguish I, X, Y, Z in one query
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.
That's it? I can't believe I didn't get that. :') I spent pretty long on that question, too.
Same. I feel like a clown reading this after hours of messing with roots of unity phases and trying to apply phase kickback.
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
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.
Is there a way to do this without Bell states btw?
I believe so, but Bell States is definitely the cleanest
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.
I've tried to distinguish controlled versions on a two-qubit input at first. But my calculations showed that this is impossible.
Really? I had initially thought of this as well and ended up going nowhere. Seems interesting that you proved it is impossible.
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: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.Oh, damn. I proved this too, but it was a lot of tedious calculation. I didn't think to compare columns. Obvious in retrospect.
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?
The only difference is
IntAsBoolArray, which looks like it could potentially be slow: https://github.com/microsoft/QuantumLibraries/blob/master/Standard/src/Convert/Convert.qs#L81I think the B-problems weren't run on a full simulator, only one with classical logic and hence much faster, so a slow
functioncould add up.thats what i thought to, but in my local testing i found that ControlledOnBitString + IntAsBoolArray was actually the one faster than ControlledOnInt by itself
Suppose we have a unitary implemented as Z, for "distinguish" problems like A7:
How do we introduce a phase, like -Z or (-i)I?
With the R1 operation.
Thank you. Sill R1(pi) |0> is not the same as -Z |0>
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> usingX.So:
R1(angle); X(); R1(angle); X();There are probably better ways to do it, but that one should work.
In this particular case, you can replace R1 by Z itself. :-)
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!)
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.
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!
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
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.
The only advice I got about quantum computing was from here which was "Shut up and calculate!". Lol..
Unfortunately that is not really the truth xD
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!
Thanks. Will definitely try it in my free time. Lets hope to do better in the next Q# contest.
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!
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
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 :)
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.
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.
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.
Using misses in the cost function is just ridiculous and hardly can be called Machine Learning at all, it's more like Machine Guessing.
when will the random T-shirts winners for the contest be announced?
From the rules:
Give us a bit of time :-)
I tried to solve B1 with n/2 extra qubits, https://codeforces.net/contest/1357/submission/84461367
I prepared a state of n/2
|1>'s and then applied aControlled Xon 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 ?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
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.
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.)
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.
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.
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.
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.
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.
Is this a bug or did I miss something? Nickolas
This is for problem D3.
No rotations (gets WA): https://codeforces.net/contest/1357/submission/84380572
1 useless rotation which should be equivalent (gets AC): https://codeforces.net/contest/1357/submission/84380482
Yes, models without rotations processed incorrectly is a known bug that unfortunately wasn't discovered in time for the release used during the contest.
I think this is due to a divide by zero bug here: https://github.com/microsoft/QuantumLibraries/blob/bb75af3caa54b99b6e68989fe9fb1de0cc6d0b65/MachineLearning/src/Classification.qs#L47
If the
ControlledRotationarray is of length zero,ApproximateInputEncoderis called with tolerance infinity. This results in the state always being encoded as $$$|0\rangle$$$ from my tests.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!
Thanks,Its too excited for me to win a T-shirt for the first time!
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!
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 !
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 :-(
Any update?
Any update?
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!