Microsoft Q# Winter 2019 warmup
This article is written for my future self. The following explanation isn't clear.
Official solutions are here https://assets.codeforces.com/rounds/1115/warmup-editorial.pdf. Some of them use useful functions, especially G2 and U3. I’ll review them later. I don’t have the meaning of adjoint and controlled. So the explanation related to them is unreliable.
G1
The essential is written here: Q# standard libraries - prelude | Microsoft Docs. If n=2, we can use CCNOT gate but this problem requires n>=2. CCNOT gate can be constructed by basic quantum gates such as X,Y,Z,CNOT,H,RX,RY,RZ... and so on. Maybe, we can also construct the and gate with n terms greater than 2 but I can't realize it within the contest.
namespace Solution { open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve(x : Qubit[], y : Qubit) : Unit { body (...) { (Controlled X)(x, y); } adjoint auto; } }
G2
If we can solve G1, this problem is immediately solved. We simply apply the De' Morgan's law to the previous problem.
namespace Solution { open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve(x : Qubit[], y : Qubit) : Unit { body (...) { let n = Length(x); for (i in 0..n-1) { X(x[i]); } (Controlled X)(x, y); X(y); for (i in 0..n-1) { X(x[i]); } } adjoint auto; } }
G3
Equality can be checked by the xor operation. Thus, this problem is solved.
namespace Solution { open Microsoft.Quantum.Canon; open Microsoft.Quantum.Primitive; operation Solve(x : Qubit[], y : Qubit) : Unit { body (...) { let n = Length(x); if (n == 1) { X(y); } else { for (i in 0..n/2-1) { CNOT(x[n-1-i], x[i]); X(x[i]); } (Controlled X)(x[0..n/2-1], y); for (i in 0..n/2-1) { CNOT(x[n-1-i], x[i]); X(x[i]); } } } adjoint auto; } }
U1
Trivial.
namespace Solution { open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve(qs : Qubit[]) : Unit { let n = Length(qs); for (i in 0..n-1) { X(qs[i]); } } }
U2
This state is almost the same as Bell state. The construction method is also similar to the Bell state. The state applied H(qs[i]) for i other than 1 is the required state.
namespace Solution { open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; operation Solve(qs : Qubit[]) : Unit { let n = Length(qs); H(qs[0]); for (i in 2..n-1) { H(qs[i]); } } }
* U3
This problem is really difficult. I cannot explain clearly. Please read my code for understanding.
namespace Solution { open Microsoft.Quantum.Primitive; open Microsoft.Quantum.Canon; open Microsoft.Quantum.Extensions.Math; operation Solve(qs : Qubit[]) : Unit { let n = Length(qs); for (i in 0..n-2) { Ry(PI()/3.0, qs[i]); CNOT(qs[n-1], qs[i]); X(qs[i]); Ry(-PI()/3.0, qs[i]); CNOT(qs[n-1], qs[i]); X(qs[i]); Ry(PI()/3.0, qs[i]); CNOT(qs[n-1], qs[i]); } } }