Examples of Q# Programs

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

Original source of task: Problem A2 (2018) on https://codeforces.com/contest/1002/problem/A2

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.

Solution

The following solution in particular leverages

vectors (𝔹^n),
Hadamard transform (H)
inline conditionals (if-then-else)
type annotations (0:𝔹)
type casts (as int[n] and as 𝔹^n), and
forget

def solve[n:!ℕ](bits:!𝔹^n){
  // prepare superposition between 0 and 1
  x:=H(0:𝔹);
  // prepare superposition between bits and 0
  qs := if x then bits else (0:int[n]) as 𝔹^n;
  // uncompute x
  forget(x=qs[0]); // valid because `bits[0]==1`
  return qs;
}

// EXAMPLE CALL

def main(){
  // example usage for bits=1, n=2
  x := 1:!int[2];
  y := x as !𝔹^2;
  return solve(y);
}

Generate W State

Original source of task: Problem A4 (2018) on https://codeforces.com/contest/1002/problem/A4

Generate a generalized W state in $N=2^k$ qubits:

\[W_N = \frac{1}{\sqrt{N}} \Big( \ket{100...0}+\ket{010...0} + ...+\ket{00...01}\Big)\]

Solution

The following solution in particular leverages

Lambda-abstraction (λ...)

def solve(k:!ℕ){
  // produce uniform superposition over k-bit uints
  i:=0:uint[k];
  for j in [0..k){ i[j]:=H(i[j]); }
  // invert i-th qubits (results in correct state, but entangled with i)
  qs:=vector(2^k,0:𝔹);
  qs[i]=X(qs[i]);
  // uncompute i
  forget(i=λ(qs:𝔹^(2^k))lifted{ // function to reconstruct i from qs
    i:=0:uint[k];
    for j in [0..2^k){
      if qs[j]{ // in the superposition's summand where qs[j]==1, i==j
        i=j as uint[k];
      }
    }
    return i;
  }(qs));
  // return result
  return qs;
}

// EXAMPLE CALL

def main(){
  // example usage for k=2
  return solve(2);
}

Distinguish 3-qubit States

Original source of task: Problem B1 (2019) on https://codeforces.com/contest/1116/problem/B1

Determine if a given qubit is in state $\psi_0$ (return 0) or $\psi_1$ (return 1):

$\psi_0=\frac{1}{\sqrt{3}} \Big( \ket{100} + \omega \ket{010} + \omega^2 \ket{001} \Big)$, where $\omega=e^{2i\pi/3}$
$\psi_1=\frac{1}{\sqrt{3}} \Big( \ket{100} + \omega^2 \ket{010} + \omega \ket{001} \Big)$, where $\omega=e^{2i\pi/3}$

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’$.

The following solution in particular leverages:

decomposing lists: (head,)~tail:=qs
reverse of a recursive function

def toW[n:!ℕ](qs:𝔹^n)mfree:𝔹^n{
  // for a single bit, prepare |1⟩
  if n==1{ qs[0]:=X(qs[0]); }
  else if n>1{
    // split qs into head (first element) and tail (rest)
    (head,)~tail:=qs;
    // prepare first bit
    θ:=2·asin(1/sqrt(n)); // sin(θ/2)=1/sqrt(n), cos(θ/2)=sqrt((n-1)/n)
    head:=rotY(θ,head); // |0⟩ ↦ cos(θ/2)|0⟩ + sin(θ/2)|1⟩ = cos(θ/2) |0⟩ + 1/sqrt(n)|1⟩
    // prepare remaining bits
    if !head { tail := toW(tail); }
    // combine head and tail again
    qs:=(head,)~tail;
  }
  return qs;
}

def solve(qs:𝔹^3):!ℕ{
  // transform ψ₀ to W₃
  if qs[1]{ phase(-2·π/3); } // exp(2*i*π/3)*exp(i*-2*π/3)=1
  if qs[2]{ phase(-4·π/3); } // exp(4*i*π/3)*exp(i*-4*π/3)=1
  // map W₃ to |000⟩
  qs:=reverse(toW[3])(qs);
  // check if obtained |000⟩
  return measure(qs as int[3])!=0;
}

// EXAMPLE CALL

def generate_input_state(state:!𝔹){
  // prepare ψ_0 (state=false) or ψ_1 (state=true)
  qs:=vector(3,0:𝔹);
  qs:=toW[3](qs);
  if state{
    if qs[1]{ phase(4·π/3); }
    else if qs[2]{ phase(2·π/3); }
  }else{
    if qs[1]{ phase(2·π/3); }
    else if qs[2]{ phase(4·π/3); }
  }
  return qs;
}

def main(){
  // expected outcome: (0,1)

  // prepare both states
  ψ_0:=generate_input_state(false);
  ψ_1:=generate_input_state(true);
  check0:=solve(ψ_0);
  check1:=solve(ψ_1);
  return (check0,check1);
}

Check if String is Periodic

Original source of task: Problem C2 (2019) on https://codeforces.com/contest/1116/problem/C2

Implement a function solve with signature solve[n:!ℕ](x:𝔹^n):𝔹 and

\[\text{solve}(\vec{x})=\begin{cases} 1 & \text{if } \vec{x} \text{ is periodic} \\\\ 0 & \text{otherwise} \end{cases}\]

A bit string of length $n$ is considered periodic with period $P$ ($1 \leq P \leq n-1$) if for all $i \in {0,\dots, n-P-1}$, $x_i=x_{i+P}$.

Solution

The following solution in particular leverages

Automatic uncomputation of y and z when they are overwritten

def solve[n:!ℕ](x:𝔹^n)lifted{
  y:=0:𝔹;
  // Check all possible periods.
  // Periods with P<(n+1)/2 are implicitly detected by period 2P because P<=(n+1)/2-1 implies 2P<=n-1.
  for p in [(n+1) div 2..n){
    // check period p
    z := 1:𝔹;
    for i in [0..n-p){
      z&=x[i]==x[i+p];
    }
    y|=z;
  }
  return y;
}

// EXAMPLE CALL

def main(){
  // expected outcome: (0,1)
  ap:=solve((true,true,false));
  p:=solve((false,false,false));
  return (ap,p);
}

X-wing Fighter

Original source of task: Problem D3 (2019) on https://codeforces.com/contest/1116/problem/D3

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:

X......X
.X....X.
..X..X..
...XX...
...XX...
..X..X..
.X....X.
X......X

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$).

The following solution in particular leverages

swapping entries of a vector with other values

def solve[n:!ℕ](qs:𝔹^n){
  x:=0:𝔹;
  // swap x with LSB of qs
  // necessary because Silq would block `qs` in the body of `if qs[0] {...}`
  (x,qs[0]):=(qs[0],x);
  if x{ // flip all other bits if LSB=1
    for i in [1..n){
      qs[i]:=X(qs[i]);
    }
  }
  x:=H(x); // map LSB to 1/√̅2 (|0⟩±|1⟩)
  if x{
    // flip all other bits if LSB=1
    // - if LSB was originally 0, this flips the bits iff H flipped the LSB
    // - if LSB was originally 1, this leaves the other bits flipped
    //   if H flipped the LSB and restores the other bits otherwise
    for i in [1..n){
      qs[i]:=X(qs[i]);
    }
  }
  // swap x back
  (qs[0],x):=(x,qs[0]);
  forget(x=0);
  return qs;
}

// EXAMPLE CALL

def main(){
  // example usage for N=3
  x := 0:!int[3];
  y := x as 𝔹^3;
  return solve(y);
}