Microsoft Q# coding contest winter 2019

https://codeforces.com/contest/1116

I solved 11 problems. The remaining two problems are difficult for me.

B1

Let us create a function which converts |000> to the first state, say f. We only have to apply (Adjoint f) to the given state. We can distinguish two states because the first state is converted to |000> and the second state is converted to other than |000>.

namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Extensions.Math;
    
    operation g(qs : Qubit[]) : Unit {
        body (...) {
            H(qs[0]);
            X(qs[0])
            R1(PI() * 2.0 / 3.0, qs[0]);
            X(qs[0]);
            (ControlledOnInt(0, X))([qs[0]], qs[1]);
        }
        controlled auto;
        adjoint auto;
        controlled adjoint auto;
    }

    operation f(qs : Qubit[]) : Unit {
        body (...) {
            Ry(ArcTan2(1.0, Sqrt(2.0)) * 2.0, qs[0]);
            X(qs[0]);
            R1(PI() * 2.0 / 3.0, qs[0]);
            X(qs[0]);
            (ControlledOnInt(0, g))([qs[0]], qs[1..2]);
        }
        controlled auto;
        adjoint auto;
        controlled adjoint auto;
    }

    operation Solve(qs : Qubit[]) : Int {
        Adjoint f(qs);
        if (M(qs[0]) == Zero && M(qs[1]) == Zero && M(qs[2]) == Zero) {
            return 0;
        } else {
            return 1;
        }
    }
}

C3

If we have a binary counter, this problem is immediately solved.

namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;
    
    operation inc(x : Qubit[]) : Unit {
        body (...) {
            let n = Length(x);
            for (i in n-1..-1..0) {
                (Controlled X)(x[0..i-1], x[i]);
            }
        }
        controlled auto;
        adjoint auto;
        controlled adjoint auto;
    }

    operation Solve(x : Qubit[], y : Qubit) : Unit {
        body (...) {
            using (c = Qubit[4]) {
                for (e in x) {
                    (Controlled inc)([e], c);
                }
                (ControlledOnBitString([false, false, false, false], X))(c, y);
                (ControlledOnBitString([true, true, false, false], X))(c, y);
                (ControlledOnBitString([false, true, true, false], X))(c, y);
                (ControlledOnBitString([true, false, false, true], X))(c, y);
                for (e in x) {
                    Adjoint (Controlled inc)([e], c);
                }
            }
        }
        adjoint auto;
    }
}