Processing math: 100%

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

Given classical bits b𝔹n with b[0]=1, return state 12(|b+|0), where |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
123456789101112131415161718def 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

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

WN=1N(|100...0+|010...0+...+|00...01)

Solution

The following solution in particular leverages

  • Lambda-abstraction (λ...)
123456789101112131415161718192021222324252627def 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

Determine if a given qubit is in state ψ0 (return 0) or ψ1 (return 1):

  • ψ0=13(|100+ω|010+ω2|001), where ω=e2iπ/3
  • ψ1=13(|100+ω2|010+ω|001), where ω=e2iπ/3

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

Solution

Key Insights:

  • ψ0ψ1: The two states are orthogonal.
  • ψ0 can be transformed to the W state on 3 qubits W3. This process trasnforms ψ1 to some state ψ1 orthogonal to W3.
  • We can generate W3 from |000 (see Problem A4 above). Reversing this process generates |000 from W3, and a state orthogonal to |000 from ψ1.

The following solution in particular leverages:

  • decomposing lists: (head,)~tail:=qs
  • reverse of a recursive function
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253def 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

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

solve(x)={1if x is periodic0otherwise

A bit string of length n is considered periodic with period P (1Pn1) if for all i0,,nP1, xi=xi+P.

Solution

The following solution in particular leverages

  • Automatic uncomputation of y and z when they are overwritten
1234567891011121314151617181920212223def 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

Implement a unitary operation on n qubits which is represented by a square matrix of size 2n 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:

12345678X......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 |100 basis state.

Solution

Key insight: A possible solution is mapping |b1bn to 12|b1bn±12|¯b1¯bn, where ¯bi=1bi. 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 Nv (where Nv can be computed by inverting all bits of v).

The following solution in particular leverages

  • swapping entries of a vector with other values
12345678910111213141516171819202122232425262728293031323334def 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);
}