Microsoft's Quantum Team has good news for quantum enthusiasts and coders looking for new challenges. We are excited to announce Microsoft Q# Coding Contest — Summer 2018! By entering the contest, you can hone your quantum coding skills by tackling problems of varying difficulty and implementing solutions in the quantum programming language Q#. Winners will receive a Microsoft Quantum T-shirt!
Quantum computing is a radically different computing paradigm compared to classical computing. Indeed, it is so different that some tasks that are believed to be classically intractable (such as factoring integers, computing discrete logarithms on elliptic curves, or simulating physical systems) can be performed efficiently on a quantum computer. Microsoft recently introduced the Quantum Development Kit which includes Q# — a new programming language to express quantum programs in a way that makes it easier for classical coders to enter the space. Q# integrates into Visual Studio or Visual Studio Code development environments, and is available as a command line tool. Visual Studio Code allows development under Windows, macOS, and Linux.
The contest will run from July 6 — 9 and will consist of increasingly challenging tasks on introductory topics in quantum computing: superposition, measurement, oracles and simple algorithms.
The rules of the contest are:
- The contest will have
1215 tasks of various complexity levels. - To solve each task, you will write Q# code to implement the described transformation on the given set of qubits or to analyze the state of a set of qubits. Solutions are accepted in Q# only.
- The solution is correct if it passes all tests from a predefined test set. You will know whether the solution is correct soon after submitting it.
- Participants are ranked according to the number of correctly solved tasks.
- Ties are resolved based on lowest total penalty time for all tasks, which is computed as follows. For each solved task, a penalty is set to the submission time of that task (the time since the start of the contest). An extra penalty of 20 minutes is added for each failed submission on solved tasks (i.e., if you never solve the task, you will not be penalized for trying that task).
- The top 50 ranked participants will receive a Microsoft Quantum T-shirt.
- NO PURCHASE NECESSARY. Must be 16 years of age or older. Game ends 7/9/18. For details, see Official Rules.
From June 29 to July 2, we will offer a warmup round with simpler tasks on the topics covered in the main contest. Participation in the warmup round is entirely optional. The warmup round gives you an opportunity to get familiar with the contest environment and submission system beforehand, as well as refresh or learn the basics of quantum computing and Q# programming language. During the warmup round everybody is encouraged to discuss the tasks and the solutions. 24 hours after the start of the warmup round we will publish explanations and solutions to the easiest three problems. Once the warmup round is over, we will publish the editorials on the contest page explaining both the quantum computing logic behind the solution and the Q# implementation.
To start, please refer to Q# installation instructions and language reference.
Quantum computing and Q# materials:
- Run Q# online
- Quantum Computing: Lecture Notes by Ronald de Wolf (first two chapters)
- "Quantum Computation and Quantum Information" by Nielsen & Chuang (part I)
- Introduction to Quantum Oracles
- Quantum computing concepts from Q# documentation
- The Hitchhiker’s Guide to the Quantum Computing and Q# Blog
- Quantum Computation Lecture notes by John Preskill
- Q# Language Quick Reference
For first time Codeforces users:
- Create user account here.
- Register for the warmup round here.
- Register for the contest here.
- Once the warmup round starts on June 29, access the problems and see additional contest materials here.
- Once the contest starts on July 6, access the problems here.
Good luck! We hope you enjoy the contest!
Update. Explanations for problems A, D and G of the warmup round are published.
Update. The warmup round is over. Explanations for all problems are published.
Is it rated?)
No.
For those familiar with past Codeforces contests, this contest is most similar to Surprise Language Rounds.
Thanks!
this contest is most similar to 1 april contest
Is it a hiring contest?
Just another person who doesn't solve problems because of getting fun
No.
This contest is educational and aims to encourage people to learn quantum computing and Q#.
Wow, that sounds amazing! Sadly I have 3 exams in the 3 days of the contests, but I will probably participate in the warm-up round. Btw, what level of knowledge is required about quantum computing in order to participate? also, if the practice and contests rounds will be available after the contest ends for people who failed to participates on time it would be great :D
I aimed to make a lot of the tasks accessible for people with no quantum computing background, who will start by learning what is superposition, what are the basic gates used in quantum computing, what is measurement etc. Of course, there are also some tasks which are definitely more challenging, just in case people with quantum computing training show up. But only the contest will show whether I got the balance right :-)
I think the problems will be available on Codeforces for a few weeks after the contest. We plan to publish the test harnesses as well, so that everybody can try and solve the problems offline.
I haven't used Q# to solve any problems, though I installed Q# two month ago. Will this contest fit me?
Yes, definitely. With the compiler already installed, you're ahead of a lot of others :-)
I have heard of Q# about 2 months ago but haven't try it. I will give it a shot this time.
stupid language, useless. this is a waste of my time. codeforce should give more brainf*ck language contests. because codeforces’ retardness is f*cking my brain. stupid codeforces. stupid contestants
⬆️It seems that this guy drunk.
It’s too negative.
can you even proper english? no wonder codeforces is hopeless. this china guy broken english
If you don’t want me to speak English,please open your translate. 我不明白你为什么对Codeforces有如此大的仇恨,也不明白你为什么要用此般语言去辱骂,如果你觉得Codeforces给你带来了不好的影响,请你注销账号,关闭网站。如果你觉得你说的话值得所有人去追捧,那么请您解释-92和您的Contribution是-23的原因。如果您觉得我的话侵犯到您,我可以向您道歉。但是请您端正您的态度,没有人强求您参加这场比赛,也不强求您必须参与Codeforces。
Is "can you even proper english?" proper English? It breaks my google-translate.
Whatever, we should keep calm. Hold your fire. & do not hurt others.
Excited to code Q#. Are the problems typical problem-solving style or some kind of different one? Like, using unitary matrix or something.-
The tasks are definitely very different from typical competitive programming problems. And yes, you pretty much can't avoid using unitary matrices :-)
Is quantum computing background required for this contest?
I aimed to make a lot of the tasks accessible for people with no quantum computing background, who will start by learning what is superposition, what are the basic gates used in quantum computing, what is measurement etc. We'll see whether I got that right :-)
I had a doubt. Will I be able to test my code on the custom invocation like code of any other language? Please pardon if you do not find this comment sensible enough.
This is a very sensible question. Unfortunately, due to the unusual nature of the tasks each of them requires a custom test harness, which is more complicated than the usual console I/O. Custom invocation would have to be per-problem to provide the same test harness as the problem does, but that's essentially the same as just submitting the problem, so we didn't provide a separate custom invocation.
If you want to run some Q# code but don't want to install it on your machine, you can use https://tio.run/#qs-core
Can I do this contest without using any Mrkvosoft tools?
:^)
Haven't actually tried it yet. But from what I can see from Setting up the Q# development environment, you only need to install
dotnet
, and the development kit. Afterwards you can use any editor you want, and compile/run the programs via the terminal.You can write untested code and submit. lol
Well, technically speaking Codeforces back end uses Q# compiler which is a Microsoft tool, so once you sumbit the code to the contest, you're using a Microsoft tool. But then, Codeforces back end runs on Windows, so the same applies to any CF contest :-)
If you mean running Q# locally, and are willing to tolerate Q# compiler but are averse to tools like Visual Studio and Windows, then (as Jakube already said) you can use Linux or Mac with .NET Core which is open source.
I wouldn't call CF a MS tool, not anymore than I'd call an airplane a Kernighan/Ritchie tool :D
Yeah, I don't want to use Windows and if possible not use VS. My first adventure with VS OSS (I don't remember why prebuilt versions didn't work) on Arch Linux ended up with running out of /tmp space, my first adventure with VS on Windows VM ended up with running out of RAM and virtual disk space and my second adventure with VS OSS on Arch Linux ended up with uninstalling it because it was unnecessarily taking up space.
You should be able to use VSCode to developt Q#, I believe. VSCode is cross platform.
So is the Brainfuck compiler.
Will system tests be handled by quantum computers? :D
No, but you won't be able to tell the difference :-)
Quantum systems of up to 30 qubits can be simulated perfectly on a (not very powerful) classical computer. The tasks in the contest use at most 16 qubits, just to be on the safe side.
Is there any materials about Quantum Programming?
I'm very interested in this but having no idea how to learn about it.
I have been studying Ronald de Wolf's lecture notes for the past couple of days and would recommend. It seems possible to pick up QC pretty fast if you are already comfortable with linear algebra and bit bashing.
Exm, what does "bit bashing" mean? And thanks a lot for your book.
I mean tricks with bitwise operations. A lot of XOR, AND, popcount so far. Or another way to look at it, linear algebra over GF(2) is used in addition to over the complex numbers.
There are also John Preskill's lecture notes. "Quantum Computation and Quantum Information" by Nielsen & Chuang is a very useful book. I'll try and assemble a list of useful links a bit later today.
Interested in this contest but won't participate for my poor knowledge of quantum mechanics and unfamiliarity with Q# and even C#.
I'm interested in Q#, and looking forward to this contest!
Can only use Q#? 这次比赛只能用Q#吗 Google Translate....Chinese->English.....
You can only use Q#.
参与者只能用Q#
Google Translate....English->Estonian->Spanish->French->Japanese->Russian->Swahili->German->Xhosa->Chinese->Taiwanese->Simplified Chinese
lol
Is there any guide to the quantum algorithms for Complete Idiots (tm)?
Try this
I've already tried, got to page 3, read few more pages and understood that I did not understood anything (after page 3). I guess there are some prerequisites for most of the material on the subject. The question is more if there are classical-programmer-oriented materials available.
What I want is more or less a specification of the abstractions provided by the Q# language. I do not really want to deep into the quantum physics math (not yet). Not only because it is too high matter for me, but also because it looks incomplete and not well understood by those who write on it (the latter conclusion is made based on the language they use; remember "if you cannot describe a thing in simple words, you don't understand it").
Try searching documentation on the microsoft page, I recently found about this article that really helped me write first quantum program
For Q# language-based introductions, best sources are Q# language reference (it has an intro to quantum concepts before diving into Q#) and this blog.
The blog you referenced is what I was looking for. Thanks!
may i use any other language other than Q#
No
You may manipulate the quantum state of CF to achieve AC or use a quantum computer to crack encryption, gain access to CF and give yourself AC.
Expected ranklist:
... Remaining ones are difficult to decide.
Oops, why doesn't the following work for G?
Is there any materials for quantum oracle? I'm stuck in G :'(
Sorry, I have no idea what's going on. :(
The wiki page of Deutsch-Jozsa algorithm have what you want.
Thanks. Actually I saw Deutsch-Jozsa algorithm before(Yet not fully understood). But how this can be applied to Problem G?
There is a paragraph saying the actual function of a quantum oracle.
Wow, thanks! I guess I shouldn't initialize y to 0. :P
Magic! I thought we need to use teleportation.. Am I correct that CNOT may result in different phase, but this is allowed by the problem?
I think the problem in initializing y is that makes the function non-invertible (the initial state of y is lost) and from tutorial: "oracles have to have an adjoint defined for them"
https://codeforces.net/blog/entry/60319
I think this may break the superposition of y qubit
You shouldn't set it to zero. You need to act on the previous state of the qubit.
Maybe I didn't understand this task correctly. I tried to read an article about oracles but it's too mathy. Should I set y:=x[k] and don't change x[k] at the same time?
There is a theorem which prohibits copying the (arbitrary unknown) state of a qubit without changing the state of the original one (no-cloning theorem).
You need to set y := y XOR x[k], and not change x[k].
This single sentence is more useful than that article!
So in oracles the phase of the qubit does not matter? E.g. what if I apply Z to the answer? Or e.g. submit |+> instead of |->.
The absolute phase of the whole system doesn't matter; you can always multiply the whole state by a complex number of norm 1 and it won't change anything. However, relative phase (phase by which you multiply only some parts of superposition and not the others) matters. and states are effectively the same, but and are not (they are orthogonal).
How can I find that "Tutorial blogpost", where the specification of an Oracle is given?
My bad!
https://codeforces.net/blog/entry/60319
It seems the checker does not recognize compilation errors. Sent non-compilable code and got WA.
It does give compile errors.
Guys I would like to ask a question.
Since this is a practice contest, I think its ethical to take help.
However, I would still ask you guys, should I ask a question related to the contest ?
I think it's probably better to ask rather than remain with WA on task A for the next day ;)
Sure, the warmup round is supposed to help participants learn the basics and prepare for the main contest. We'll publish detailed editorials for problems A, D and G tomorrow, but you can ask for hints now.
Any hints for E & F?
Hint for E: Look at the vector representations of the Bell states and see how you can fiddle with them to get |B0> to |00>, |B1> to |01>, etc. In particular, most fundamental quantum operations are reversible, so try to go through your solution for B in reverse.
Hint for F: It's way easier than it may seem. It's actually a purely classical programming task, nothing quantum. You have 3 bitstrings A, B and C, either A=B or A=C. Which is it?
Need some more hints for F :/
ACed all other problems, this remains with WA3.
First attempt was to check till first difference between bits0 & bits1. WA1. Now I check all differences, WA3. Code seems clear.
Are there some important things like not-reseting-output-qubit for oracles?
Well, somehow it works now.
You can't say anything about which state it was based on measurements of qubits which have the same value in both bitmasks. I suspect your AC submission should fail because it effectively makes the decision based on the last bit of the masks, not on the differing bit. But I can't figure out why it was accepted right now (it's well past midnight here...)
For your submissions which check only positions where the bitmasks differ, the idea is correct but the logic in the condition is incomplete, it covers only half of the cases.
Actually, last version still checks only differences. It makes the decision based on last qubit with difference from bitstrings. It does nothing when founds a match :)
Why no online IDE for this?
The linked one isn't working properly.
I want to test my Q# method but I don't really know how. I understand that I can make a C# driver class (since I'm using Visual Studio Code, that is done for me), but I can't call the Q# method because it takes a Qubit[], which in C# seems to be a QArray(). Now, normally, this would be no problem, and I would just look up the documentation for QArray and Qubit to see how to create them, but I can't find documentation for these two classes anywhere. I suppose I am just bad at looking, any help would be appreciated.
Qubits can not be allocated in C# code. You need to write a Q# wrapper around your solution that would:
using
keyword,DumpMachine
to dump the state of the simulator without measuring it).Testing and Debugging section of Q# documentation provides more information.
Thanks for the help, it makes sense, but I still can't get it to work in practice. I made a testing operation in the qs file and put dump machine in the operation, like so
So I expect it to print out the program state to test.txt. I have also tried DumpMachine(()) to print to console. However, either way, nothing seems to happen when I run the Driver code, which looks like this:
Wierdly, it says TestOp does not exist in the current context, but it still seems to run (though of course nothing happens). I tried to figure out how to make it defined but the compiler seems dead set on ignoring my test method ): Can you explain the reason for the weird behavior?
Same here. I was unable to get any debugging output. Running on macOS if that could matter.
You should use 'DumpMachine("")' to write to console. This is wrong in the documentation and I just sumitted an issue. This works on TIO.run. ('DumpMachine(())' writes to a file named '()' on my machine.)
Edit: Also running simulations that don't return anything get optimized away or something, so the quick fix is to return some dummy value. fixed code
A method I also use for printing to console is Message(str), works with no problems.
Nickolas, One question please. Are the inputs of Problem G any random state of qubits? Like, x[k] = α|0 > + β|1 > with any proper α and β?
Yes, in oracle tasks oracles should work on arbitrary state of input qubits.
Thanks. I suddenly wonder how multi-bit logic gates actually work on a real quantum computer atomically :| Amazing!
Typically a multi-qubit gate would be approximated by a sequence of one- and two- qubit gates which can be implemented natively on the hardware. A set of gates which can approximate any gate is called universal.
Is there a Q# issue-tracker somewhere? Some of the error-messages are not very helpful and look like a bug in the compiler:
error QS0001: Internal error: The index was outside the range of elements in the list.
occurs if the body of an operation with a return value contains only comments. (Just an empty body does produce a proper error message.)error QS0001: Internal error: Parsing produced an error node without logging an error
occurs really often for me, mostly when I guess the syntax wrongly. Some examples of such wrong syntax are: & as bitwise operator, ! or ~ as boolean not, braced-initializer for a new array, a single-statement for-loop without {}, a single-statement else without {}.error QS0001: Internal error: ("C:\\<path-to-folder>\\prog.qs", Ln: 112, Col: 2): The combinator 'many' was applied to a parser that succeeds without consuming input and without changing the parser state in any other way. (If no exception had been raised, the combinator likely would have entered an infinite loop.)
occurs if your create imbalanced curly brackets by commenting some }. Surprisingly, deleting them instead of commenting produced a different (more reasonable) error.I also encountered a strange crash that is quite sensitive to code changes (The crash does not occur on TIO.):
Crash: Microsoft.Quantum.Simulation.Simulators.Exceptions.ReleasedQubitsAreNotInZeroState: Released qubits are not in zero state.
It looks like the unused qbit
A
got flipped.Edit: I just figured out how to dump to console ('DumpMachine("")'):
Something's seriously wrong on my machine xD.
There is a package for bitwise operations: https://docs.microsoft.com/en-us/qsharp/api/prelude/microsoft.quantum.extensions.bitwise?view=qsharp-preview
You can actually just use
&&&
. (As I'm most used to C++, I tried a single&
first and it didn't work.) The main complaint is not about the different syntax, but rather about the error message.Internal error
to me implies that something broke inside the compiler. (Just like GCC telling you it'sconfused by earlier errors, bailing out
.)The issue tracker is here, though for some reason it calls issues "ideas".
I totally agree that the error messages are, ahem, not ideal. We are working on a new parser which should eliminate all of the weird messages at once.
I have a question.
let's say q[0] is in state |0> + |1>. I use the operation CNOT(q[0],q[1]) so I have |00>+|11>. Now measure res=M(q[0]). Now if I do res2=M(q[1]) will I always get the exact same measurement or different. i.e does measuring q[0] collapse q[1] or will q[1] still remain in superposition.
A quantum bit will be set to |0 > if measured value is 0 otherwise |1 > after measuring so yes, it will break the superposition.
You will always get the same measurement, and the qubits are said to be entangled with each other. This process is known as Quantum Entanglement. More info here. Quantum Entanglement Wikipedia
The document says:
Is it enforced in the judger of this contest? I got WA in Problem I if I don't reset them, and got AC if I do. I wonder whether this means I produced a wrong answer or the judger was unhappy because I didn't reset.
On TIO and on my machine, this is enforced and you get a
Microsoft.Quantum.Simulation.Simulators.Exceptions.ReleasedQubitsAreNotInZeroState
exception. I'd expect similar behaviour on codeforces.Judging by the fact that no submission got the
Runtime error
verdict, I'd guess that exceptions get reported as WA and not as RE.Either way, it would be nice to get confirmation on this.
You are right, the simulator enforces that the qubits must be released in zero state, and the tester converts any exception to WA. In problems on superposition and oracles this is necessary: the tester checks that the generated state/returned oracle is correct by applying some operations to the qubits and checking that in the end they are in zero state, so incorrect solution is indicated by this exception.
I will try to improve the checker for tasks which allow some degree of separation between RE and WA (like measurement tasks and Deutsch-Jozsa algorithm) for the main contest.
Fastest Editorial ever!!! It comes out (partially) 2 days before contest even ends O:
Any hidden tricks for Deutsch Josza? I don't know what am I doing wrong.
I don't get how M(qs[i-1]) could give one because applying H twice will get them back to initial state.
You have to make sure the qubits you release are in zero state. Otherwise, as discussed above, the simulator will throw
ReleasedQubitsAreNotInZeroState
exception which is interpreted as WA.Thanks a lot Nickolas!, that was the exact issue. I was confused as I got WA.
completely new to this topic
learn quantum computing in 6 days
wow
Hey would it be possible to include a driver program so that we could test our code in the actual contest? I'm having trouble in using online IDE link given.
Most of the tester code is Q#, and for most problems it literally contains the solution code. So, unfortunately, we can't provide the test harness during the contest without revealing the solutions.
Custom invocation on Codeforces would have to be per-problem to provide the same test harness as the problem does, but that's essentially the same as just submitting the problem, so we didn't provide a separate custom invocation.
The driver code doesn't need to check the validity of the output, just print it to the console so that the programmer can check it and possibly debug the program. That's how I made my driver programs, but it took some time to write them.
Maybe the driver doesn't create the state of the qubits just allows us to actually make the states and call our solution function.
We have added Custom Invocation to the main contest; hope that helps!
Will the actual contest have tougher problems? otherwise it would become a time race.
Yes, it will. This one is a warmup round, after all :-)
Is there any difference between the functions ResultAsInt and PositiveIntFromResultArr?
From their implementation at https://github.com/Microsoft/Quantum I don't see any, other than the check for potential overflow in
PositiveIntFromBoolArr
. Nice catch :-)I am worried that the judge does not working because it always returned AC for every problem. Can someone confirm it is possible to get WA ?
Yes, I was able to obtain WA for deliberately incorrect solutions.
i have no object oriented programming knowledge.I have been using only functional(haskell) and procedural languages(C,C++).Will Q# suit me in this case.If not is their any alternative?
PS even though c++ has oops i have never tried or used it.
Yes, it will. Q# is not object-oriented.
Try it and see. Worst case scenario, you learn OOP.
Is it ok that smart tabs do not work at all in Q# sources in Visual Studio 2017?
Basically, whenever I press Enter to create a new line, a new line is created, but it's empty and does not contain any indentation:
I've already went to Tools -> Options -> Text Editor -> All Languages -> Tabs and switched "Indenting" to "Smart", but it didn't help with Q# source files. Indentation in C# works as expected.
Works on my machine.
I suspect that either this setting is overridden by the setting for "plain text" files or VS doesn't have enough information to figure out the smart way to indent. I set mine to "block" which works, it's not ideal but better than "none".
Is there any analogue of
AssertQubitState
, but for n-qubit states? I was able to findAssertProbInt
, but it checks probabilities only and does not check phase shifts. Basically, I want to write a unit-test for problem B.Not that I'm aware of.
For testing B, I ended up applying adjoint transformation and checking that the result is an all-zero state using
AssertAllZero
.Thanks, that was very educational — I've read about quantum computing before and had a very basic understanding that the state vector could be evolved through unitary matrices and measurement, but actually coding it help understanding a lot, particularly that it's non-trivial to construct the unitary matrices from gates.
I'm feeling pretty happy that I managed to derive Deutsch-Jozsa for N=1 before reading the Wikipedia page. It's still hurting my brain that even though the oracle doesn't modify any of the input qubits, the algorithm throws away the output and just manipulates the inputs.
Do you have an intuitive explanation for Deutsch-Jozsa?
Deutsch-Jozsa creates a uniform superposition of all possible inputs. Then, it negates the phase of all inputs that satisfy the predicate. Finally, it applies hadamard to all qbits again. The phase of the all-zero qbit array will be the sum of all the phases of the intermediate state because hadamard maps
∣0⟩
to(|0⟩+|1⟩)/√̅2
and|1⟩
to(|0⟩-|1⟩)/√̅2
and so the contribution of each state to the all-zero state is its phase multiplied by1/√̅2ⁿ
. If the function is balanced, the contributions cancel out, and if it is constant, they add up to either -1 or 1. Therefore, the function is constant exactly if we measure the all-zero array.That sheds some light, thanks! But how/why the oracle modifies the phase of the inputs? Is it because of the entanglement?
The phase flip is implemented using an ancillary qubit that is initialized with
1/√̅2(|0⟩-|1⟩)
. The entire state will be given byThe oracle will take the input qubits to the left and flip the qubit to the right.
But because
1/√̅2(|1⟩-|0⟩) = -1/√̅2(|0⟩-|1⟩)
, this yields:At this point, we can forget about the ancillary qubit, as it is not entangled with any of the others, so our state is simply
Can someone explain C to me?
It is very similar to generating the first Bell state ; you just need to synchronize the state of the qubits after the second one with the state of the first qubit the same way you do it for the second qubit.
Okay, but why isn't this correct: I am doing for same thing for every qubit as I did for B:
namespace Solution { open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon;
}
H gate creates superposition of two states, then CNOT gate changes the state of target qubit based on the state of control qubit. When you use H gate second time, you split the existing two states into four, which you don't need to do. Consider what your code does for N = 3:
Ahh, thanks, got AC now
Are tests running? It seems like all submissions are in queue but none is being evaluated
That's because a system test of another contest was running. You just have to wait until the system test ends.
I realized that the pdf with problem explanations has some issues with copying the code which makes it fail compilation. I'll be fixing it in the following editorials. Meanwhile, here is the code from the pdf that you can copy and run.
What's wrong in this code for problem H?? I'm getting WA.
operation Solve (x : Qubit[], y : Qubit) : () { body { mutable counter = 0; for(i in 0..Length(x)-1) { if(M(x[i]) == One) { set counter = counter + 1; } } set counter = counter % 2;
Thanks in Advance!!
You must not measure any qubits.
It worked. Thanks dalex!! What's the reason behind it??
I think it's because when measuring qubit, you put it as 1 or 0. So if you have qubit with superposition, mesuring it will make qubit 1 or 0 (depends on where it is)
So does this mean that the oracle should return the input qubit register without any changes?
It said this in statement: The operation doesn't have an output; the "output" of your solution is the state in which it left the qubits.
Yes, it should return input qubits without changes, and output qubit should be xor-ed with the function you calculate.
operation Solve (qs : Qubit[]) : () { body { let n = Length(qs); for (index in 1 ..n) { X( qs[index]); } } }
http://codeforces.net/contest/1001/submission/39862662 ( the last index is out of bound)
why it's WRONG ANSWER instead of RUNTIME ERROR
Right now all incorrect solutions produce WA verdict, regardless of what exception they throw. I'll try to introduce some separation between WA and RE verdicts for the main contest.
This is my code for the H question. It seems to work for all sorts of superpositions as well, but I got a wrong answer. Is there an issue with using an extra qubit and discarding it, as I did below?
Well qubit output shouldn't exist in first place.
Wrong algorithm
Why shouldn't it exist?
Because you should CNOT with y, not output
You don't know the state of y, so you should use output as replacement
You are allowed to allocate extra qubits, but (as discussed above) you have to reset them to state before releasing them. In this code the allocated qubit is still entangled with x and y when it is released, so it throws
ReleasedQubitsAreNotInZeroState
exception, which in turn is treated as WA.try setting output to zero at the end. qubits must be released in zero state.
I need help with this part of I problem: Uf : ((Qubit[], Qubit) => ())
How should this array be represented. If I wanted to, let's say CNOT first and second element, what should I write? CNOT(Uf.Qubit[0],Uf.Qubit[1])?
That's not an array, it's a function. You can use if calling Uf(x, y), where x is an array of N qubits and y is a single qubit. This function will act as a oracle for the described function. Read https://codeforces.net/blog/entry/60319
Oh, I didn't know about that. Thanks!
What about syntax highlighting plugins for other editors than VS? If I want to use, say, Sublime Text or Vim (and compile with .NET SDK or by submitting), is there a way to get correct syntax highlighting? C# syntax isn't the same.
In vim I used F# syntax highlighting (syntax file is easy to find). F# seems closer to Q# than C#. But of course, a designated syntax for Q# would be better.
I haven't looked specifically at these editors yet. We do syntax highlighting via TextMate grammars, so if these editors support TextMate grammars, you can get qsharp.tmLanguage.json file from one of the extensions for VS/VS Code and use it to configure your editor.
In problem G, is y guaranteed to be initialised to ?
I wanted to set it to by first measuring it, which puts it in one of the Pauli Z basis states, and then flipping it if the measured eigenvalue was - 1. It gave WA.
I'm aware entanglement means I shouldn't measure in oracles, but if y is entangled with something (not ), then I'm not going to set its value to xk using just CNOT anyway.
y does not have to be initialized to . In that case, the oracle should set y to (link to oracle tutorial blog).
Also,
one way of using this is calling the oracle with which results in , i.e. the oracle return value in the phase.
Ah, seems like I didn't read that blog correctly — I thought the function determines what state y will be in and it can use or discard the initial state of y as it sees fit. Makes sense this way from a QM perspective.
The warmup round is over! Here are the editorials for the tasks.
Can someone write me I problem, so I can examine it. I have hard time dealing with compilation errors..
IsConstantBooleanFunction
from the samples implements problem I, but with parameters N and Uf swapped.Why the solutions are closed for viewing?
Open now :-)
About how hard / harder than warm up round will the next Q# round be? For example, rate this round X/10, and next one Y/10. I am a fan of /10 scores
X/10 scores imply the existence of a contest which is 10/10. Since the warmup round and the main contest are the only two quantum programming contests I'm aware of, and the main contest is harder than the warmup, the main has to be 10/10 :-)
On a serious note, the tasks in the main contest will range from ones similar in complexity to the harder ones from the warmup round to much harder. But the existence of the warmup round (editorial and open solutions) should make some of the tasks easier than the similar-level ones in the warmup.
For people interested in the very mathematical form of QM (using matrices and vectors), here's a physics problem where the physics is just an interpretation of the math, problem 9, QM beamsplitter:
consider a beamsplitter that takes two photon beams (light beams) as input, described as and (the input Fock state is ) and produces two photon beams as output, described as , , where each of n1, n2, n1', n2' describes the number of photons in the given beam; all photons are indistinguishable
the creation operators of the input and output beams — a creation operator creates one photon (also known as ladder operators for some reason) are tied by the following relations:
\$ show that the transformation from basis to and vice versa is unitary; why does it have to be, physically?
what's the physical/practical meaning of θ?
if the input state is , compute the output state and the probabilities that we'll measure a photon in output beam 1, output beam 2
same as above, if the input state is — compute the output state and relevant probabilities or the expected number of photons we should measure in each output beam
especially for , can there be interference between output beams? (Dirac claimed that a photon can only interfere with itself, like in the double slit experiment)
how do the answers to the above questions change when photons are considered distinguishable, e.g. with different wavelengths in the two input beams?
A unitary matrix satisfies . It's true that ; the second matrix is Hermitian adjoint.
The reason why it has to be unitary is conservation of the number of photons / energy between the input and output.
Many reasons can be offered, my own is that cos2θ is the fraction of energy of input beam i transmitted into output beam i and sin2θ is the fraction transmitted into output beam 3 - i. Maybe there's a better explanation.
Since by definition and similarly for input beam 2 and output beams, we have
where we used the fact that the vacuum state is the same on the output as on the input — if zero photons go in, zero photons go out.
Measuring the number of photons in output beam 1 can be described generally using a counting operator N'1 with eigenvalues/vectors: , with a similar operator for output beam 2. A measurement of beam 1 of our output state will collapse it to with probability cos2θ, giving result 1 photon, or to with probability sin2θ, giving result 0 photons. If we measure beam 2, the probability of getting the result 1 photon is sin2θ and the probability of getting 0 is cos2θ. Note that the total number of measured photons is 1, which is consistent with unitarity.
It's very similar to previous case with some more complicated calculations. Since we can apply creation operators repeatedly, the formula connecting vacuum and our state is
Now let's compute
\$ We used boson commutation relations — photons are bosons, so they satisfy , similarly for output operators. That means the output state is
A measurement will collapse this into the state with probability cos22θ or into either of the states with probability sin22θ / 2. The expected number of photons is again 1·cos22θ + 2·sin22θ / 2 = 1, as expected (heh); however, a probability of finding a photon at an output is cos22θ + sin22θ / 2.
Btw, the third commutation relation I didn't mention is (identity). The reason the magic sqrt appears in the definition of creation operators is this and normalisation of all state vectors to 1. If this magic number for state is kn, then for a single beam,
The rest is just a natural choice of $k_0=1$ and . I used a to denote a corresponding annihilation operator that's defined with a corresponding magic constant.
Note that interference = one measurement affecting another, which is the same as asking if entanglement is possible.
The answer lies in the previous part: we actually obtained an entangled state. Note what happens after the mentioned measurement: if we measured x photons in output beam 1, we'll always measure 2 - x photons in output beam 2 afterwards. However, if the measurement of beam 1 wasn't performed, we could measure 0, 1 or 2 photons in beam 2.
The mathematical approach to QM is helpful in knowing what should happen without endless philosophical debates.
The commutation relations I mentioned will still hold (except the one with identity, which is 0 instead). However, if we denote the distinct photon types' creation operators as , then the resulting state is separable (the subscripts of numbers describe what kind of photons the states consist of — e.g. red or blue). In fact, we could write each input state as and similarly for output states, since each photon type has an independent operator set that only acts on its own state.
Different particles don't interfere with each other.
How does the checker for problem G look like?
Essentially it uses operation AssertOperationsEqualReferenced from
Microsoft.Quantum.Extensions.Testing
namespace to compare your submission with the reference implementation of the oracle.Why this doesnt work for problem B ?
This code generates wrong state for index = 1. Z gate flips the sign of qubit in state , but you apply it to qs[1] which is in state , so it has no effect, and the state generated is instead of . If you apply Z gate on the same qubit as H gate, it will work.
OK correct me if I'm wrong, I'm new to Quantum Computing and find some part of it confusing .
|00>
,q[0]
andq[1]
as both|0>
.H
onq[0]
we get(|00> + |10>)1/√2
, now what doesq[0]
andq[1]
refer to, doesq[0]
mean|00>
andq[1]
as|10>
?q[0]
refers to|00>
then what will be the result of applying the flip gateX
onq[0]
, and onq[1]
?q[0]
andq[1]
are both qubits. and are terms in the expression for superposition state, they don't correspond to qubits, the first digit in each of the terms corresponds toq[0]
and the second — toq[1]
.After applying H gate to
q[0]
, the state of the two-qubit system is , the state ofq[0]
is and the state of q[1] is still .Once you apply an entangling gate to the qubits, like CNOT, you won't be able to represent the state of the system as a tensor product of states of separate qubits.
Small correction for the solution to task E: B_1 gets mapped to |10>.
How is the time limit exceeded determined? In terms of real execution time of the code on the cf server (so a classical computer) or supposed runtime on a quantum computer (measured by e.g. number of operations)?
I can imagine that an efficient quantum algorithm simulated on a classical computer can be significantly slower than the usual classical algorithm for the same problem.
Or maybe there won't be problems where this is an issue?
Real execution time on CF server.
I don't expect there will be problems for which it will be an issue. Reasonable correct solutions are small enough to not time out accidentally.
For most problems, there doesn't exist a classical algorithm — you can't really generate a quantum state or distinguish quantum states classically.
Problems which can be solved classically — for example, the task of figuring out whether a function is constant or balanced, solved by Deutsch-Jozsa algorithm, can be solved by encoding classical queries in qubits before calling the oracle, — have extra checks to restrict the number of calls to the oracle to only one.
Thanks!
I wasn't sure if this is going to be algorithmic contest (i.e. get a nice complexity) or a quantum contest (i.e. solve a problem in non-familiar environment). I'd be personally happy with both.
I'm really looking forward to the contest. This seems like a lot of fun. Thanks for preparing it!
Did tourist forget to register or he just want to make a penalty of 38687?
I have a dumb question: How do i declare an array of Bool in Q#? i tried mutable v = new Bool[4]; but i get either parsing error or symbol v is undefined. Also, what types can i send from c# to q# via arguments of an operation? Sending an array of bool from C# to Q# doesn't work... however Result exists both in C# and in Q# (this is in Microsoft's tutorial), are there more of these? If yes, which types?
Declaring mutable v = new Bool[4]; seemed to work just fine to me. Check for example my submission to problem F. I didn't remove the testing code before submitting, and it might contain what you need.
I noticed that Q# has its own bool-like type, that is not the same as C# bool. Apparently, they can be casted to each other (meaning passing a bool is fine) but array doesn't work. For bool arrays, I just passed a bitmask and reconstructed the array. It even made my C# code easier (one random number instead of whole array).
I found the samples from this repository pretty useful in terms of what can I do in Q#.
Thank you, i tested it and apparently it works, i don't know what i've messed up then, but thank you again!
mutable v = new Bool[4];
should be the right syntax, I definitely have code in which it works.You can send pretty much any type (except qubits, which are technically possible to pass but really should be allocated inside Q# code), but a C# array has to be cast to
Microsoft.Quantum.Simulation.Core.QArray
first. You can look up example of QArray of long inReversibleLogicSynthesis/Driver.cs
in https://github.com/Microsoft/QuantumWhat does the "adjoint auto;" do, in solution of A4?
I think Pcorrect in solution of C1 is:
instead of
because both two states have possibility to be given.
In problem D I tried something different from tutorial. I let another variable to store the state of our qubit. Then i applied X gate on our qubit knowing that X|+> = |+> and X|-> = -|-> then simply compared q and another variable where I stored q and returned 1,-1 accordingly. But it gives WA. Can anyone explain 83325355.
It doesn't work like that... The qubits in Q# are not qubit states, they are objects that change the underlying state of the system when acted upon (you can read more about it in this blog post). When you compare qubits you're not comparing their states (that's not a physically realizable operation), you're comparing that the variables point to the same object. So what your code actually does is:
Got it! thanks!