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]);
        }
    }
}