In the following, we review some Silq solutions to Microsoft’s Q# Summer
2018 and Winter
2019 coding contest on Codeforces.
Detailed solutions targeted for Q# programmers are available for both
2018
and 2019.

Generate Superposition of Zero State and a Basis State

Given classical bits $b \in 𝔹^n$ with $b[0]=1$, return state $\frac{1}{\sqrt{2}}
\Big(\ket{b}+\ket{0} \Big)$, where $\ket{0}$ is represented using $n$ bits.

You may modify the given qubit arbitrarily (including measurements).

Solution

Key Insights:

$\psi_0 \perp \psi_1$: The two states are orthogonal.

$\psi_0$ can be transformed to the W state on 3 qubits $W_3$. This process
trasnforms $\psi_1$ to some state $\psi_1’$ orthogonal to $W_3$.

We can generate $W_3$ from $\ket{000}$ (see Problem A4
above). Reversing this process generates $\ket{000}$
from $W_3$, and a state orthogonal to $\ket{000}$ from $\psi_1’$.

Implement a unitary operation on $n$ qubits which is represented by a square
matrix of size $2^n$ which has non-zero elements on both main diagonal and
anti-diagonal and zero elements everywhere else.

For example, for $n=3$, the matrix of the operation should have the following
shape:

Here, X denotes a “non-zero” element of the matrix, and . denotes a “zero”
element of the matrix.

The row and column indices of the matrix follow little endian format: The least
significant bit of the index is stored first in the qubit array. Thus, the
second column of the matrix gives you the coefficients of the basis states
you’ll get if you apply the unitary to the $\ket{10…0}$ basis state.

Solution

Key insight: A possible solution is mapping $\ket{b_1 \cdots b_n}$ to
$\frac{1}{\sqrt{2}}\ket{b_1 \cdots b_n} \pm
\frac{1}{\sqrt{2}}\ket{\overline{b_1} \cdots \overline{b_n}}$, where
$\overline{b_i}=1-b_i$. This is because the diagonal from top-left to
bottom-right captures the identity, and the diagonal from bottom-left to
top-right captures the mapping from $v$ to $N-v$ (where $N-v$ can be computed by
inverting all bits of $v$).