Microsoft's Quantum Team and Codeforces are excited to invite you to Microsoft Q# Coding Contest — Winter 2019!
The contest will run from March 1 to March 4 and will offer increasingly challenging tasks on superposition, measurement, quantum oracles and unitary transformations.
As a reminder, last weekend we held a warmup round with easier tasks on quantum oracles and unitary transformations; the tasks are available for practice here, and the solutions are explained here. You can brush up on the topics of superposition and measurement in the first Q# contest and its warmup round.
Several useful reminders:
- The contest is unrated :-)
- Solutions are accepted only in Q#.
- Participants are ranked according to the number of correctly solved tasks, with the last correct submission time as a tiebreaker.
- The tasks are grouped by topic, and the tasks within one topic are ordered in approximate order of increasing difficulty. If you find a problem too hard, don't forget to check the next problems in this topic and problems from different topics, they might turn out to be easier.
- Submission verdicts work as follows:
Wrong Answer means that the solution fails any problem-specific checks (such as leaving the qubits in a state other than expected, using measurements in a task which prohibits them or returning incorrect classical value in measurement tasks) or prints anything to the standard output (using Message or DumpMachine functions);
Runtime Error means that the solution throws a more general exception (for example, caused by releasing allocated qubits in non-zero state or trying to access array elements outside of array bounds);
Memory Limit Exceeded means that the solution together with the checker allocated more qubits than it is allowed (the limit is ~15 qubits for problems related to quantum oracles with memory limit 1024MB, and ~25 qubits for other types of problems);
Time Limit Exceeded works the same way as in classical competitions (your program is too slow), but I have to mention it for the sake of completeness :-) - Custom Invocation allows you to run Q# code on Codeforces servers; make sure your code has namespace
Solution
and an operation with a signatureoperation RunQsharp () : Bool
defined in it. - And finally, the really important stuff: the top 50 ranked participants will receive a Microsoft Quantum T-shirt! Here is a preview:
- NO PURCHASE NECESSARY. Must be 16 years of age or older. Game ends 3/4/19. For details, see Official Rules.
Good luck! We hope you enjoy the contest!
For first time Codeforces users:
- Create user account here.
- Register for the contest here.
- Once the contest starts on March 1st, access the problems here.
Update: The contest is over. Congratulations to eatmore for a very convincing victory!
Update 2: The editorials are published here. The comments to that post have some great explanations of alternative solutions as well.
No time limit exceeded?
Time Limit Exceeded is very intuitive and works the same way as in classical contests, so I didn't highlight is separately. You can, for example, get Memory Limit Exceeded by allocating purely classical resources, but that's classical so I didn't focus on that as well.
That's an amazing design!
Also, I'm curious about the last contest's design. What did it look like?
Yes, I like it quite a lot, too bad I'm not eligible for this contest :-P
I'll borrow a photo from https://twitter.com/frances_tibble/status/1026381426952990720:
I agree, the joke is strong with this one! So funny and pretty :D
Unless anyone shares last year's design I can take a picture of mine in several hours from now.
Edit: ok, nevermind :)
From where I can learn Quantum Computing theories to participate in these contests? Please share some resources to start with.
The original announcement has pointers to a variety of sources on quantum computing.
It's a Shrodinger cat on the T-shirt
Woowww no TLE involved??? :333
I've updated the post to include TLE as well, even though there is nothing specifically quantum about it.
While trying to use custom invocation to run code, I get a complaint from the compiler along the lines of:
CSC : error CS5001: Program does not contain a static 'Main' method suitable for an entry point
``However, it does say that the Q# has compiled correctly. Is there an example of code that runs with the custom invocation?
Where do you run custom invocation from? I believe you have to use it from one of the Q# contests (I just tried running code from https://codeforces.me/contest/1115/customtest and it works), if you call it from https://codeforces.me/problemset/customtest it will not realize that it needs extra files (which contain the actual C# driver with the
Main
method).Why does following code gets RTE? (When submitted similar code in A1 its WA, but in A2 RTE)
Ah, this is a tricky case! This throws a
ReleasedQubitsAreNotInZeroState
exception, which is generally treated as a Runtime Error. The qubits you release are released in 0 state (obviously, since you haven't done anything with them). But the checker allocates some extra qubits to to test that your solution returns correct answer — and those are the ones which are released in non-zero state if your solution is incorrect. (This same code gets WA if submitted to A1, because in A1 the checker doesn't allocate and release extra qubits.)I don't have a good way to distinguish
ReleasedQubitsAreNotInZeroState
caused by the solution vs caused by the checker because of incorrect solution. I'll think some more about it, but for now it will have to stay like this — some things that should be Wrong Answer produce Runtime Error instead :-(In problems where measurement isn't allowed, is calling
Reset(q)
on an ancillary qubit also prohibited?Yes,
Reset
does a measurement followed by an X gate, if one is required, so it is also prohibited.You really weren't kidding about the problems being tougher than last time. I got VERY hacky with my solutions, and stayed up for 12 hours.
Yes, I think this time we calibrated the complexity much better — last time the fate of the T-shirts was decided in less than 24 hours, and now it doesn't seem to be the case.
I'm getting "Time limit exceeded" error, so I wonder, what are the durations of execution for standard gates operations on Codeforces server?
It's hard to estimate, and not particularly useful — the total execution time of your program depends not only on the number of gates in your code but also on things like the number of qubits allocated (more qubits makes everything slower, since applying a gate requires updating more values).
Thanks. I see. Maybe you can at least provide some estimation, on how many value updates can be done per second? At least some order, e.g. tens of thousands, millions, etc.
Hundreds, in my estimate. It's low enough you most likely can't bruteforce through problems like C3 with O(2N) applications of
(Controlled X)(x, y)
and some applications ofX(x[i])
on suitable indices.Are the strict time limits in some problems intended? For example, in Problem B2 the solution gets called 1000 times but the time limit is only 1 second. It seems like you could get TLE just because you use an additional Qubit or perhaps two quantum gates in those problems.
I'm pretty sure those things won't push you over the limit.
Yes, the time limits are intended. The reference solutions never take more than a half of the time limit to run, and I didn't pick the most optimized solutions as reference ones either :-)
Hi! For question B2, is the idea that you can determine which state the qubit was not in with 100% accuracy? Wording doesn't explicitly say that but seems to imply it.
Yes. To be more precise, to determine "a" state which you know with certainty it wasn't in.
Many thanks. I thought that was the case but just wanted to be sure before I carry on staring at it ;)!
I would really really really recommend you do the last one before this. The last one turned out to be MUCH easier than I thought. I solved it in a few minutes after hours of staring at B2 with no luck.
Stuck on both ¯\_(ツ)_/¯
I see you solved it. What did I tell ya? ;)
Haha! Yep just managed it now. 99% sure I haven't done it the 'correct' way but it's done at least. Time to stare at B2 some more ;)
If less than 50 people solved all questions, do you still give out the T-shirts to the top 50, or only to the ones that solved all 13?
The rules say we'll give them to top 50, so that's what we'll do. Right now it doesn't look like it will be necessary to solve all problems to get in top 50, but there is still time for this to change :-)
Thanks.
Also, on a completely unrelated note: I noticed that there is no "break" statement in the language. Is this because it would be harder to reverse operations that contain them?
Yes.
It's possible to simulate "break" using repeat-until-success loop, as described here.
I'm kinda unclear on the exact meaning of the question B2. Are you guys saying that we are able to find which state its not in, or that we're able to do so with high enough probability that its ok for the 1000 rounds?
You have to find a state in which qubit is not on every trial; the number of rounds just tells you that it's not a single-shot experiment.
gotcha, thanks!
The language doesn't allow us to define our own (arbitrary) measurement operators, does it?
Only by expressing them in terms of
M
andMeasure
.I thought I had to give up on B2, but after thinking about it for a looooong time, I finally got it. Now I can finally sleep without worry.
What a great problem! Very counterintuitive.
Thanks for the contest! Even though my rank is lower than last time, I really enjoyed the more challenging problems. Looking forward to getting my T-shirt :D
How did you solve it? I honestly cannot wait until the editorial is out.
I tried introducing qubits, I tried looking into QFT, I even found this specific problem (called trine states) but I had to use measurement operators not in Q#.
It stumped me for a long time. My reasoning was: If all we do is some kind of transformation, then measure the qubit, this problem is impossible (because there's no way to get more than one of A,B, and C into a pure 0 or 1 state). So for this problem to be solvable, we need to introduce at least one more qubit. But how can that help? It seems like we would be getting information out of nowhere.
However, eventually I figured it out — measurement is a projection. So even though A and B are not orthogonal, they could become so after a measurement projects them onto a different plane. Of course, that's impossible to guarantee. But... it IS possible to guarantee that EITHER A and B become orthogonal, or A and C do.
So, first apply H and S to turn the three qubits into something more manageable. Then allocate another qubit. You can come up with a transformation that turns A into a combination of 00 and 10, B into a combination of 00, 01, and 11, and C into a combination of 10, 01, and 11 (Notice that if we only look at our original qubit, it looks like B turns into 0 and C turns into 1. This can't happen! But if you rotate the extra components into the 01/11 plane, it works).
Notice, once you measure the second qubit, if you get 1, you could not have started with A. and if you get 0, you can measure the first qubit and know that it's not B, or not C.
I think you should be able to reconstruct the solution from this. I'm not good at putting these vague thoughts into words.
I had similar ideas but was too bad at geometry to figure out the right rotations.
Is it possible to get this t-shirt from somewhere if i'm stupid enough to be top-50?)
I suggested t-shirts for finding important bugs, but no, you can't — other than by making one for yourself or getting it from someone who was in top 50.
What a cool Tshirt! And what a pity I can't solve some of the tricky and interesting tasks.
Looking forward to next Q# contest!
(...I really really like that Tshirt QAQ
(...Is there any way to get one if I am not the top 50? QwQ
Wow, thank you for the contest! The problems were great and I had a lot of fun while solving them. Unfortunately, It's quite a pity that I couldn't come up with a solution for the problem B2 (I spent ~16 hours solving it though), but I definitely enjoyed the whole process of solving.
Thanks a lot for organizing this contest. It was a lot a fun and I learned quite a few things. Special thanks to problem B2 which kept me busy for quite some time (But the solution in the end was quite intuitive and nice. It was also a nice contrast the the problems D1 — D6, which I mostly solved by trying out a few operations that look promising until the results matched.)
Also thanks for updating the language. The compiler error messages were a lot more helpfull that last year. (And I had no issues with the simulator this year.)
Some probably unintended solutions:
StatePreparationPositiveCoefficients
. (I didn't try this for A2 as I expected it to get TLE. It would be interesting to see what this function does internally and if it could be optimized for sparse states.)StatePreparationComplexCoefficients
to get an operation that maps |000> to |ψ₀>. Applying the adjoint maps |ψ₀> to |000>, so we can just measure all qubits and check if they're zero.ControlledOnBitString
gets TLE. We can optimize a factor of two if we note that the periodicity does not change if we flip all bits. This gets OK. (I tried something similar for C3, but I got TLE.) Intended is something with QFT?IntegerIncrementLE
intended? (that + manually modding by 3 gives OK whileModularIncrementLE
gives TLE. Once again, I don't know which algorithms are used internally. The modular one uses QFT I guess?)IntegerIncrementLE
for D4 and D5, but I guess there are many solutions to the D-tasks.IntegerIncrementLE can be implemented pretty easily. The codes below are for adding/subtracting 1.
I had so many TLEs on C3 trying to use IntegerIncrementLE. How did you manage to do it?
I ended up passing by abandoning that approach, and using three qubits that alternate between 100,010, and 001.
I tried something similar for B1. I just used the solution from the Katas for the W state with 3 qubits. I used the adjoint and measured, but wasn't sure if that would actually be a correct solution, since I might map the second state to something with 000 and measuring would give 000.
For C2, I hardcoded which periodicity based on the numbers. E.g. for 6 qubits, the possible are 1,2,3,4,5, but 2 is already 4-periodic, and 1 is already n periodic, so exclude them, and test for 3,4,5.
Here's a proof that the approach for B1 is correct:
The two states are orthogonal. So if you apply a unitary that takes the first state to |000>, the second state must map to something that's orthogonal to |000>. This means that if you measure it, it's impossible to get 000.
We're publishing the editorial here (it will take us some time to finish the descriptions for the harder problems — sorry about that!)
I'm honestly surprised at how long the solution for D6 is. Mine only used 1 extra operation, which increments a basis state |k> to |k+1 mod 2^n>
For the exponentiation, you could use
1 <<< N
or2^N
.D6 took me a long time but I found a really short solution.
First, a helper function to entangle the middle two vectors (111110 and 000001).
Then do a recursion — apply Solve to the first N-1 bits, controlled on the last bit. Apply the helper. Then apply Solve to the first N-1 bits again, but controlled on the last bit being 0.
The base case for N=1 is simply H.
For B1, that's what I did, except I manually came up with the transformation to prepare the state (just a variation on A1, with some phase changes).
For C2, for each k between 0 and N/2, you can check if the k-prefix and k-suffix of the string are equal.
My first approach was checking periodicity for EVERY period, which TLEs.
For D4, I used IntegerIncrementLE — I'm curious if there's any other approach.
For D5 it's definitely possible to do without — I came up with a pretty neat recursive solution.
I checked periodicity for every period, but avoided the TLE by not allocating extra qubits while checking for equality. Instead, I did some dirty hack of "overwriting the input qubits with the output qubits."
I hardcoded all periodic strings in a more compact way on C2. There are just a few conditions the qubits need to satisfy, starting with "if the first and last qubit are the same, it's periodic".
For C2, I literally brute-forced all possible values of P, doing something similar to my palindrome checker oracle (from the warmup round) to check pairs of bits for equality. I just allocated an ancilla qubit to store the result of each P. Then I just reused the OR oracle from the warmup round and the
WithA
operation. My solution ended up being an almost direct translation of the definition given in the problem statement.EDIT: Well, basically this was the intended solution.
I used approach similar to yours but got TLE on case 5 can you please have a look [link] .(https://codeforces.me/contest/1116/submission/50695009)
From what I can tell, your solution allocates an ancillary qubit register, qs, to determine periodicity. It is possible to do this operation on place on x, then revert it afterwards.
In addition, your 'or' register doesn't actually use it's 0-index qubit. It might be worth refactoring your code so that it doesn't need it.
Every qubit added, at minimum approximately doubles the amount of time required to run, so every little qubit counts.
Yes , I used qs to calculate the periodicity for every possible period and if the string is periodic for some period p , then or[p] would be One , then I used the OR oracle on or. Can you please tell me how can I determine periodicity in place , I stored the XOR of x[i] and x[i+p] in qs[i] and used Controlled X gate on qs to know if periodic for period p.
Basically, if one is careful about the order, they can put x[i] XOR x[i+p] into x[i] for all i from 0 to n-p-1 in a reversible manner.
Using the first [n-p] qubits instead of the qs, determine whether it is periodic with period p.
Then reverse the modifications to x, to return it to its original form.
You can check the editorial posted above. My solution ended up being basically the same as that one, and the same as sirknightingfail mentioned.