Microsoft Q# Coding Contest - Summer 2018
http://codeforces.com/contest/1002
I had never study quantum computing. I acquired all the knowledge of quantum computing from only a official tutorial. I mean I am not an expert, so this article is unreliable.
Write a quantum program | Microsoft Docs
Official editorials are here:
https://assets.codeforces.com/rounds/997-998/main-contest-editorial.pdf
C1
If you don't do anything, about 750 cases will pass. So you only have to modify just a little bit. All you have to do is to increase the probability of appearing 1. It isn't difficult to devise such a rotation.
operation Solve(q: Qubit): Int { body { Ry(0.4, q); if M(q) == Zero { return 0; } else { return 1; } } }
C2
The key observation is if you observe One then you can answer correctly, the given state is the plus state. For answering not only plus state but also zero state, we apply H to the given state with probability 50%. By doing so, you can distinguish states with probability 25%. To make a binary random variable, a quantum will be helpful.
operation Solve(q: Qubit): Int { body { mutable res = -1; using (qs = Qubit[1]) { H(qs[0]); if M(qs[0]) == Zero { if M(q) == One { set res = 1; } } else { H(q); if M(q) == One { set res = 0; } } ResetAll(qs); } return res; } }
D1
The problem is to find the inner product of x and b. I think CNOT(x, y) corresponds to the classical xor gate, y ^= x.
operation Solve(x: Qubit[], y: Qubit, b: Int[]): () { body { for (i in 0 .. Length(x) - 1) { if b[i] == 1 { CNOT(x[i], y); } } } }
D3
This problem is to make the oracle state representing (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z) ≡ (x ∧ y) ⊕ (x ∧ z) ⊕ (y ∧ z). I think CCNOT(x, y, z) corresponds to doing z ^= x&y classically.
operation Solve(x: Qubit[], y: Qubit): () { body { CCNOT(x[0], x[1], y); CCNOT(x[0], x[2], y); CCNOT(x[1], x[2], y); } }
E1
This algorithm is well-known and is written in a lecture note listed in a certain article on Codeforces. I think its explanation is a little complicated, so I explain it in my own way.
Firstly, transform x such that x takes the all state with equal probability. To implement, Hadamard gates will help you. If x takes only single state, it is same as classical computing. It's meaningless, isn't it? Ok, assume that x takes all states and y takes only 0 state. We denote Uf[b] as Uf with b. In this case, states will change like the following.
For avoiding complicated notations, we omit the brackets of ket-notation and their coefficients. The first two qubits correspond to x[0] and x[1], and the third qubit corresponds to y. For example, if b=10, then Uf(010) = 010 because 10*01=0, and Uf( 100 ) = 101 because 10*10=1. Note that the third qubit represents the value of the given function if the initial y is the 0 state. Uf is a linear function, so we can calculate the results easily by the superposition principle. Uf[00]( 000 + 010 + 100 + 110 ) = 000 + 010 + 100 + 110 Uf[01]( 000 + 010 + 100 + 110 ) = 000 + 011 + 100 + 111 Uf[10]( 000 + 010 + 100 + 110 ) = 000 + 010 + 101 + 111 Uf[11]( 000 + 010 + 100 + 110 ) = 000 + 011 + 101 + 110
So far, we fix y to the zero state. But this strategy seem to not work (I think). For that reason, you had better fix y to the minus state (clearly, the plus state is useless).
Uf[00]( 000 - 001 + 010 - 011 + 100 - 101 + 110 - 111 ) = Uf[01]( 000 - 001 + 010 - 011 + 100 - 101 + 110 - 111 ) = Uf[10]( 000 - 001 + 010 - 011 + 100 - 101 + 110 - 111 ) = Uf[11]( 000 - 001 + 010 - 011 + 100 - 101 + 110 - 111 ) = 000 - 001 + 010 - 011 + 100 - 101 + 110 - 111 000 - 001 - 010 + 011 + 100 - 101 - 110 + 111 000 - 001 + 010 - 011 - 100 + 101 - 110 + 111 000 - 001 - 010 + 011 - 100 + 101 + 110 - 111 We can factor them. = 0(00 - 01 + 10 - 11) + 1(00 - 01 + 10 - 11) = (0+1)(00 - 01 + 10 - 11) = 0(00 - 01 - 10 + 11) + 1(00 - 01 - 10 + 11) = (0+1)(00 - 01 - 10 + 11) = 0(00 - 01 + 10 - 11) - 1(00 - 01 + 10 - 11) = (0-1)(00 - 01 + 10 - 11) = 0(00 - 01 - 10 + 11) - 1(00 - 01 - 10 + 11) = (0-1)(00 - 01 - 10 + 11) Apply H to the first qubit = 0 (00 - 01 + 10 - 11) = 0 (00 - 01 - 10 + 11) = 1 (00 - 01 + 10 - 11) = 1 (00 - 01 - 10 + 11) Forget the first qubit for simplicity and then factor the remaining parts. = 0(0-1) + 1(0-1) = 0(0-1) - 1(0-1) = 0(0-1) + 1(0-1) = 0(0-1) - 1(0-1) Apply H to the second qubit = 0(0-1) = 1(0-1) = 0(0-1) = 1(0-1) Recall the first qubit = 00(0-1) = 01(0-1) = 10(0-1) = 11(0-1)
Qubit 1 and qubit 2 don't have uncertainties, so you can distinguish them definitely.
operation Solve(N: Int, Uf: ((Qubit[], Qubit) => ())): Int[] { body { mutable res = new Int[N]; using (qs = Qubit[N + 1]) { let x = qs[0 .. N - 1]; let y = qs[N]; X(y); H(y); for (i in 0 .. N - 1) { H(x[i]); } Uf(x, y); for (i in 0 .. N - 1) { H(x[i]); } for (i in 0 .. N - 1) { if M(x[i]) == One { set res[i] = 1; } } ResetAll(qs); } return res; } }
E2
Note that b is not unique generally. Let's try computing f(0000), f(0001), f(0010), ... with some fixed b. You would notice that the function value takes only two types. Actually, this problem can be solved by classical computer with only one query. So you needn't devise any quantum algorithm.
operation Solve(N: Int, Uf: ((Qubit[], Qubit) => ())): Int[] { body { mutable res = new Int[N]; using (qs = Qubit[N + 1]) { let x = qs[0 .. N - 1]; let y = qs[N]; Uf(x, y); if (M(y) == Zero) == (N % 2 == 1) { set res[0] = 1; } ResetAll(qs); } return res; } }
A4
This problem is the most difficult for me. My strategy is to make the solution of size n from the size n/2. First, you make the following state. The left factor can be obtained by solving the half size problem, and the right factor is GHZ state. The coefficients are annoying, so we omit them.
(1000 + 0100 + 0010 + 0001)(0000 + 1111)
This expression represents the superposition of the below eight states:
10000000 01000000 00100000 00010000 10001111 01001111 00101111 00011111
The aim is to transform the from 5th to 8th states into 00001000, 00000100, 00000010, 000000001 respectively. To achieve this, apply some CCNOT operations described below. It leads following changes.
You do the following operations where k += i * j means the same as CCNOT(qs[i], qs[j], qs[k]) 5+=0*4, 6+=0*4, 7+=0*4, 6+=1*5, 7+=1*5, 7+=2*6 10000000 01000000 00100000 00010000 10001000 01001100 00101110 00011111
After that, apply some CNOT. Then the states will be the following.
You do the following operations where j+=i means the same as CNOT(qs[i], qs[j]): 6+=7, 5+=7, 4+=7, 5+=6, 4+=6, 4+=5 10000000 01000000 00100000 00010000 10001000 01000100 00100010 00010001
Finally, cancel 1s appeared in the first half qubits by CNOT(qs[4],qs[0]), CNOT(qs[5],qs[1]), CNOT(qs[6],qs[2]), CNOT(qs[7],qs[3]).
10000000 01000000 00100000 00010000 00001000 00000100 00000010 00000001
These are the required results. This algorithm is complete.
operation Recur(qs: Qubit[]): () { body { if Length(qs) == 1 { X(qs[0]); return (); } let n = Length(qs) / 2; Recur(qs[0 .. n - 1]); H(qs[n]); for (i in n + 1 .. n * 2 - 1) { CNOT(qs[n], qs[i]); } for (i in n .. n * 2 - 1) { for (j in i + 1 .. n * 2 - 1) { CCNOT(qs[i - n], qs[i], qs[j]); } } for (i in n * 2 - 1 .. -1 .. n + 1) { for (j in i - 1 .. -1 .. n) { CNOT(qs[i], qs[j]); } } for (i in n .. n * 2 - 1) { CNOT(qs[i], qs[i - n]); } } } operation Solve(qs: Qubit[]): () { body { Recur(qs); } }
The editorial solution is sophisticated but requires advanced knowledge. As most of solutions try to solve each case N=1,2,4,8,16, brute force approach might be practical.