# Superposition Kata Workbook, Part 2

The [Superposition Kata Workbook, Part 1](./Workbook_Superposition.ipynb) includes the solutions of kata tasks 1 - 7.  Part 2 continues the explanations for the rest of the tasks.

To begin, first prepare this notebook for execution (if you skip this step, you'll get "Syntax does not match any known patterns" error when you try to execute Q# code in the next cells):


```qsharp
%package Microsoft.Quantum.Katas::0.11.2004.2825
```

> The package versions in the output of the cell above should always match. If you are running the Notebooks locally and the versions do not match, please install the IQ# version that matches the version of the `Microsoft.Quantum.Katas` package.
> <details>
> <summary><u>How to install the right IQ# version</u></summary>
> For example, if the version of `Microsoft.Quantum.Katas` package above is 0.1.2.3, the installation steps are as follows:
>
> 1. Stop the kernel.
> 2. Uninstall the existing version of IQ#:
>        dotnet tool uninstall microsoft.quantum.iqsharp -g
> 3. Install the matching version:
>        dotnet tool install microsoft.quantum.iqsharp -g --version 0.1.2.3
> 4. Reinstall the kernel:
>        dotnet iqsharp install
> 5. Restart the Notebook.
> </details>


## <a name="greenberger-horne-zeilinger"></a> Task 8. Greenberger-Horne-Zellinger state.

**Input:** $N$ ($N \ge 1$) qubits in the $|0 \dots 0\rangle$ state (stored in an array of length $N$).

**Goal:**  Change the state of the qubits to the GHZ state $\frac{1}{\sqrt{2}} \big (|0\dots0\rangle + |1\dots1\rangle\big)$.

### Solution

The single-qubit GHZ state is the plus state $\frac{1}{\sqrt{2}} \big (|0\rangle + |1\rangle\big)$ that we've discussed in [task 1](./Workbook_Superposition.ipynb#plus-state). As a reminder, that state is prepared by applying a Hadamard gate.

The 2-qubit GHZ state is the Bell state $\frac{1}{\sqrt{2}} \big (|00\rangle + |11\rangle\big)$ that we've discussed in [task 6](./Workbook_Superposition.ipynb#bell-state). That state can been prepared using the following circuit:



The next one is the 3-qubit GHZ state:
$$|GHZ\rangle = \frac{1}{\sqrt{2}} \big (|000\rangle + |111\rangle\big)$$

Let's use the 2-qubit circuit as a building block to construct the circuit for 3 qubits. First, let's add a third qubit to the above circuit:



Comparing the state prepared by this circuit with the desired end state, we see that they differ only in the third (rightmost) qubit:

$$|\Phi^+\rangle |0\rangle = \frac{1}{\sqrt{2}} \big (|000\rangle + |11\color{red}0\rangle\big)$$
$$|GHZ\rangle = \frac{1}{\sqrt{2}} \big (|000\rangle + |11\color{red}1\rangle\big)$$


Applying a controlled NOT operation using the first (leftmost) qubit as the control bit and the third (rightmost) qubit as the target qubit allows us to fix this difference: 

<table style="background-color: white; border:0 solid; tr  { background-color:white; }">
    <col width=30%>
    <col width=70%>
        <td style="text-align:center; background-color:white; border:0"></td>
        <td style="text-align:left; background-color:white; border:0"></td>       
</table>

Similarly, the following circuit will prepare the GHZ state on four qubits $\frac{1}{\sqrt2} (|0000\rangle + |1111\rangle$:


Thus we can come to the general solution: apply Hadamard gate to the first qubit and do a series of CNOT gates with the first qubit as control and each of the other qubits as targets.


```qsharp
%kata T08_GHZ_State_Test

open Microsoft.Quantum.Arrays;

operation GHZ_State (qs : Qubit[]) : Unit {
    H(qs[0]);
    
    // Library function Rest returns all array elements except for the first one
    for (q in Rest(qs)) {
        CNOT(qs[0], q);
    }
}
```

[Return to task 8 of the Superposition kata.](./Superposition.ipynb#greenberger-horne-zeilinger)

## <a name="superposition-of-all-basis-vectors"></a>  Task 9. Superposition of all basis vectors.

**Input:** $N$ ($N \ge 1$) qubits in the $|0 \dots 0\rangle$ state.

**Goal:**  Change the state of the qubits to an equal superposition of all basis vectors $\frac{1}{\sqrt{2^N}} \big (|0 \dots 0\rangle + \dots + |1 \dots 1\rangle\big)$. 

> For example, for $N = 2$ the final state should be  $\frac{1}{\sqrt{2}} \big (|00\rangle + |01\rangle + |10\rangle + |11\rangle\big)$.

### Solution

As we've seen in [task 4](./Workbook_Superposition.ipynb#superposition-of-all-basis-vectors-on-two-qubits), to prepare a superposition of all basis vectors on 2 qubits we need to apply a Hadamard gate to each of the qubits.

It seems that the solution for the general case might be to apply a Hadamard gate to every qubit as well. Let's check the first few examples:

\begin{align*}
   H|0\rangle &= \frac{1}{\sqrt2}\big(|0\rangle + |1\rangle\big)\\
   H|0\rangle \otimes H|0\rangle &= \frac{1}{\sqrt2} \big(|0\rangle + |1\rangle\big) \otimes \frac{1}{\sqrt2} \big(|0\rangle + |1\rangle\big)\\   
               &= \frac{1}{\sqrt{2^2}}\big(|00\rangle + |01\rangle+ |10\rangle+ |11\rangle\big)\\
   H|0\rangle \otimes H|0\rangle \otimes H|0\rangle &= \frac{1}{\sqrt{2^2}}\big(|00\rangle + |01\rangle+ |10\rangle+ |11\rangle\big) \otimes \frac{1}{\sqrt2}\big(|0\rangle + |1\rangle\big)\\
               &= \frac{1}{\sqrt{2^3}}\big(|000\rangle + |001\rangle + |010\rangle+ |100\rangle+ |110\rangle + |101\rangle+ |011\rangle+ |111\rangle\big)\\
    \underset{N}{\underbrace{H|0\rangle \otimes \dots \otimes H|0\rangle}} 
               &= \frac{1}{\sqrt{2^{N-1}}}  \big( |\underset{N-1}{\underbrace{0 \cdots 0}}\rangle + \cdots + |\underset{N-1}{\underbrace{1 \cdots 1}}\rangle \big) \otimes \frac{1}{\sqrt2}\big(|0\rangle + |1\rangle\big) = \\
               &= \frac{1}{\sqrt{2^N}} \big( |\underset{N}{\underbrace{0 \cdots 0}}\rangle + \cdots + |\underset{N}{\underbrace{1 \cdots 1}}\rangle \big)\\    
\end{align*}

Thus, the solution requires us to iterate over the qubit array and to apply the Hadamard gate to each element as follows:


```qsharp
%kata T09_AllBasisVectorsSuperposition_Test

operation AllBasisVectorsSuperposition (qs : Qubit[]) : Unit {
    for (q in qs) {
        H(q);
    }
}
```

[Return to task 9 of the Superposition kata.](./Superposition.ipynb#superposition-of-all-basis-vectors)

## <a name="superposition-of-all-even-or-all-odd-numbers"></a>Task 10. Superposition of all even or all odd numbers.

**Inputs:** 

1. $N$ ($N \ge 1$) qubits in the $|0 \dots 0\rangle$ state (stored in an array of length $N$).
2. A boolean `isEven`.

**Goal:**  Prepare a superposition of all *even* numbers if `isEven` is `true`, or of all *odd* numbers if `isEven` is `false`.  
A basis state encodes an integer number using [big-endian](https://en.wikipedia.org/wiki/Endianness) binary notation: state $|01\rangle$ corresponds to the integer $1$, and state $|10 \rangle$ - to the integer $2$.  

> For example, for $N = 2$ and `isEven = false` you need to prepare superposition $\frac{1}{\sqrt{2}} \big (|01\rangle + |11\rangle\big )$,  
and for $N = 2$ and `isEven = true` - superposition $\frac{1}{\sqrt{2}} \big (|00\rangle + |10\rangle\big )$.
</details>

### Solution

Let’s look at some examples of basis states to illustrate the binary numbering system. 

The 4 basis states on $N = 2$ qubits can be split in two columns, where the left column represents the basis states that form the required superposition state for `isEven = false` and the right column - the basis states that form the required superposition state for `isEven = true`:


 
If we do the same basis state split for $N = 3$ qubits, the pattern becomes more obvious:
 


The two leftmost qubits go through all possible basis states for `isEven = false` and for `isEven = true`, and the rightmost qubit stays in the $|1\rangle$ state for `isEven = false` and in the $|0\rangle$ state for `isEven = true`. 

A quick sanity check for $N = 4$ qubits re-confirms the pattern:
 

 
Again, the three leftmost qubits go through all possible basis states in both columns, and the rightmost qubit stays in the same state in each column. 

The solution is to put all qubits except the rightmost one into an equal superposition (similar to what we did in Task 9) and to set the rightmost qubit to $|0\rangle$ or $|1\rangle$ depending on the `isEven` flag, using the X operator to convert $|0\rangle$ to $|1\rangle$ if `isEven = false`.


```qsharp
%kata T10_EvenOddNumbersSuperposition_Test

operation EvenOddNumbersSuperposition (qs : Qubit[], isEven : Bool) : Unit is Adj {
    let N = Length(qs);
    for (i in 0 .. N-2) {
        H(qs[i]);
    }
    // for odd numbers, flip the last bit to 1
    if (not isEven) {
        X(qs[N-1]);
    }
}
```

[Return to task 10 of the Superposition kata.](./Superposition.ipynb#superposition-of-all-even-or-all-odd-numbers)

## <a name="threestates-twoqubits"></a>Task 11*. $\frac{1}{\sqrt{3}} \big(|00\rangle + |01\rangle + |10\rangle\big)$ state.

**Input:** Two qubits in the $|00\rangle$ state.

**Goal:**  Change the state of the qubits to $\frac{1}{\sqrt{3}} \big(|00\rangle + |01\rangle + |10\rangle\big)$.

### Solution

*Coming up soon... Meanwhile, follow Niel's answer at https://quantumcomputing.stackexchange.com/a/2313/*


```qsharp
%kata T11_ThreeStates_TwoQubits_Test

open Microsoft.Quantum.Math;

operation ThreeStates_TwoQubits (qs : Qubit[]) : Unit {
    // Rotate first qubit to (sqrt(2) |0⟩ + |1⟩) / sqrt(3) (task 1.4 from BasicGates kata)
    let theta = ArcSin(1.0 / Sqrt(3.0));
    Ry(2.0 * theta, qs[0]);

    // Split the state sqrt(2) |0⟩ ⊗ |0⟩ into |00⟩ + |01⟩
    (ControlledOnInt(0, H))([qs[0]], qs[1]);
}
```

[Return to task 11 of the Superposition kata.](./Superposition.ipynb#threestates-twoqubits)

## <a name="hardy-state"></a>Task 12*. Hardy state.

**Input:** Two qubits in the $|00\rangle$ state.

**Goal:** Change the state of the qubits to $\frac{1}{\sqrt{12}} \big(3|00\rangle + |01\rangle + |10\rangle + |11\rangle \big)$.

### Solution

> This solution is a detailed explanation of [this StackExchange answer](https://quantumcomputing.stackexchange.com/a/6844/2879).

We start with the state $|\psi_0\rangle=|00\rangle$.

**Step 1:** Start by putting the first qubit in the state $\alpha|0\rangle + \beta|1\rangle$, where $\alpha$ and $\beta$ are the square roots of relative weights of all basis states which start with 0 and with 1, respectively.  

In case of Hardy state, two basis states start with 0: $\frac{1}{\sqrt{12}} \big (3|00\rangle + |01\rangle\big )$ and two basis states start with 1: $\frac{1}{\sqrt{12}} \big (|10\rangle + |11\rangle\big )$.
The relative weights of 0 and 1 are just the sums of squares of their amplitudes: 
$\alpha^2 = \frac{9}{12} + \frac{1}{12} = \frac{10}{12}$ and $\beta^2 = \frac{1}{12} + \frac{1}{12} = \frac{2}{12}$, respectively. 
So we'll need to put the first qubit in the state $\sqrt{\frac{10}{12}}|0\rangle + \sqrt{\frac{2}{12}}|1\rangle$ using the $R_y$ gate:

$$|00\rangle \overset{R_{y_1}}\rightarrow \big (\sqrt{\frac{10}{12}}|0\rangle + \sqrt{\frac{2}{12}}|1\rangle \big ) \otimes |0\rangle =: |\psi_1\rangle$$

Here $R_{y_1} := R_y(2\arccos \frac{10}{12}) \otimes I$.

<details>
  <summary><b>Click here for the same computation in matrix representation</b></summary>
$\begin{equation}
R_{y_1} := R_y(\theta_1) \otimes I = 
\begin{bmatrix} 
\cos\frac{\theta_1}{2} & 0 & -\sin\frac{\theta_1}{2} & 0 \\ 
0 & \cos\frac{\theta_1}{2} & 0 & -\sin\frac{\theta_1}{2} \\ 
\sin\frac{\theta_1}{2} & 0 & \cos\frac{\theta_1}{2} & 0 \\ 
0 & \sin\frac{\theta_1}{2} & 0 & \cos\frac{\theta_1}{2}  
\end{bmatrix}
\text{, where } \cos\frac{\theta_1}{2}=\sqrt{\frac{10}{12}} \text{ and } \sin\frac{\theta_1}{2}=\sqrt{\frac{2}{12}}\end{equation}$.
    
$\begin{equation}
R_{y_1}|00\rangle = \frac{1}{\sqrt{12}} \begin{bmatrix} 
\sqrt{10} & 0 & -\sqrt{2} & 0 \\ 
0 & \sqrt{10} & 0 & -\sqrt{2} \\ 
\sqrt{2} & 0 & \sqrt{10} & 0 \\ 
0 & \sqrt{2} & 0 & \sqrt{10} 
\end{bmatrix} 
\begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}
= \frac{1}{\sqrt{12}} \begin{bmatrix} \sqrt{10} \\ 0 \\ \sqrt{2} \\ 0 \end{bmatrix}
= \big (\sqrt{\frac{10}{12}}|0\rangle + \sqrt{\frac{2}{12}}|1\rangle \big ) \otimes |0\rangle =: |\psi_1\rangle
\end{equation}$    
</details>

**Step 2:** Finish the preparation by putting the second qubit in the right state, applying controlled Ry gates with the first qubit as the control. 
To get the first two terms right, you need to convert the terms

$$\big (\sqrt{\frac{10}{12}}|0\rangle \big) \otimes |0\rangle \overset{R_{y_2}}\rightarrow \frac{1}{\sqrt{12}} \big (3|00\rangle + |01\rangle \big) \text{  (2.a) }$$ 
and
$$\big (\sqrt{\frac{2}{12}}|1\rangle \big) \otimes |0\rangle \overset{R_{y_3}}\rightarrow \frac{1}{\sqrt{12}} \big (|10\rangle+|11\rangle \big) \text{  (2.b) }$$

**Step 2.a:** The transformation
$$\big (\sqrt{\frac{10}{12}}|0\rangle \big) \otimes |0\rangle \overset{R_{y_2}}\rightarrow \frac{1}{\sqrt{12}} \big (3|00\rangle + |01\rangle \big)$$

is equivalent to the following transformation (to see this, just multiply both sides by $\sqrt{\frac{12}{10}}$):

$$|0\rangle \otimes |0\rangle \overset{R_{y_2}}\rightarrow \frac{1}{\sqrt{10}} \big (3|00\rangle + |01\rangle \big) = |0\rangle \otimes \frac{1}{\sqrt{10}} \big (3|0\rangle + |1\rangle \big)$$

This rotation should only be applied if the first qubit is in state $|0\rangle$, i.e., we need a conditional-on-zero rotation. The rotation angle can be determined by $\cos\frac{\theta_2}{2} = \frac{3}{\sqrt{10}}$ and $\sin\frac{\theta_2}{2} = \frac{1}{\sqrt{10}}$.

<details>
  <summary><b>Click here for the same computation in matrix representation</b></summary>
A regular conditional-on-one rotation (controlled rotation or $CR_y$) is defined by 

$$C_1R_y := CR_y =
\begin{bmatrix}
1 & 0 & 0 & 0 \\ 
0 & 1 & 0 & 0 \\ 
0 & 0 & \cos\frac{\theta}{2} & -\sin\frac{\theta}{2} \\ 
0 & 0 & \sin\frac{\theta}{2} & \cos\frac{\theta}{2}
\end{bmatrix}$$

To perform a conditional-on-zero rotation, we have to apply an $X$ gate to the first qubit to transform $|0\rangle\rightarrow|1\rangle$ and $|1\rangle\rightarrow|0\rangle$, perform the conditional-on-one rotation $CR_y$ and apply another $X$ gate to the first qubit to undo the first $X$.

$$C_0R_y:=\big (X\otimes I \big )CRy\big (X\otimes I \big )=
\begin{bmatrix} 
0 & 0 & 1 & 0 \\ 
0 & 0 & 0 & 1 \\ 
1 & 0 & 0 & 0 \\ 
0 & 1 & 0 & 0
\end{bmatrix} \begin{bmatrix} 
1 & 0 & 0 & 0 \\ 
0 & 1 & 0 & 0 \\ 
0 & 0 & \cos\frac{\theta}{2} & -\sin\frac{\theta}{2} \\ 
0 & 0 & \sin\frac{\theta}{2} & \cos\frac{\theta}{2}
\end{bmatrix} \begin{bmatrix} 
0 & 0 & 1 & 0 \\ 
0 & 0 & 0 & 1 \\ 
1 & 0 & 0 & 0 \\ 
0 & 1 & 0 & 0
\end{bmatrix} = \\ 
= \begin{bmatrix} 
0 & 0 & \cos\frac{\theta}{2} & -\sin\frac{\theta}{2} \\ 
0 & 0 & \sin\frac{\theta}{2} & \cos\frac{\theta}{2} \\ 
1 & 0 & 0 & 0 \\ 
0 & 1 & 0 & 0 
\end{bmatrix} \begin{bmatrix} 
0 & 0 & 1 & 0 \\ 
0 & 0 & 0 & 1 \\ 
1 & 0 & 0 & 0 \\ 
0 & 1 & 0 & 0
\end{bmatrix} = \begin{bmatrix} 
\cos\frac{\theta}{2} & -\sin\frac{\theta}{2} & 0 & 0 \\ 
\sin\frac{\theta}{2} & \cos\frac{\theta}{2} & 0 & 0 \\ 
0 & 0 & 1 & 0 \\ 
0 & 0 & 0 & 1 \end{bmatrix}$$

Applying $C_0R_{y_2}$ (with angle parameter $\theta_2$ defined by $\cos\frac{\theta_2}{2} = \frac{3}{\sqrt{10}}$ and $\sin\frac{\theta_2}{2} = \frac{1}{\sqrt{10}}$) to $|\psi_1\rangle$ leads to: 

$$|\psi_2\rangle:=C_0R_{y_2} |\psi_1\rangle = 
\begin{bmatrix} \frac{3}{\sqrt{10}} & -\frac{1}{\sqrt{10}} & 0 & 0 \\ \frac{1}{\sqrt{10}} & \frac{3}{\sqrt{10}} & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}\frac{1}{\sqrt{12}}\begin{bmatrix} \sqrt{10} \\ 0 \\ \sqrt{2} \\ 0 \end{bmatrix}=\frac{1}{\sqrt{12}}\begin{bmatrix} 3 \\ 1 \\ \sqrt{2} \\ 0 \end{bmatrix}$$  
</details>

**Step 2.b:** Similarly, the transformation

$$\big (\sqrt{\frac{2}{12}}|1\rangle \big) \otimes |0\rangle \overset{R_{y_3}}\rightarrow \frac{1}{\sqrt{12}} \big (|10\rangle+|11\rangle \big)$$

is equivalent to 

$$|1\rangle \otimes |0\rangle \overset{R_{y_3}}\rightarrow \frac{1}{\sqrt{2}} \big (|10\rangle+|11\rangle \big)$$

and can be done using a controlled rotation, applied if first qubit is $|1\rangle$, i.e., a conditional-on-one rotation. The rotation angle can be determined by $\cos\frac{\theta_3}{2} = \frac{1}{\sqrt{2}}$ and $\sin\frac{\theta_3}{2} = \frac{1}{\sqrt{2}}$.

<details>
  <summary><b>Click here for the same computation in matrix representation</b></summary>

Using the definition of $CR_{y_3}$ we've seen previously for $\frac{\theta_3}{2} = \frac{\pi}{4}$, we finally get our target state:

$$|\psi_3\rangle := CR_{y_3}|\psi_2\rangle=
\begin{bmatrix} 
1 & 0 & 0 & 0 \\ 
0 & 1 & 0 & 0 \\ 
0 & 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ 
0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}
\end{bmatrix} \frac{1}{\sqrt{12}} \begin{bmatrix} 3 \\ 1 \\ \sqrt{2} \\ 0 \end{bmatrix}=
\frac{1}{\sqrt{12}}\begin{bmatrix} 3 \\ 1 \\ 1 \\ 1 \end{bmatrix}=
\frac{1}{\sqrt{12}} \big (3|00\rangle+|01\rangle+|10\rangle+|11\rangle\big )$$    
</details>


```qsharp
%kata T12_Hardy_State_Test

open Microsoft.Quantum.Math;

operation Hardy_State (qs : Qubit[]) : Unit {
    Ry(2.0 * ArcCos(Sqrt(10.0 / 12.0)), qs[0]);
    (ControlledOnInt(0, Ry))([qs[0]], (2.0 * ArcCos(Sqrt(9.0 / 10.0)), qs[1]));
    (ControlledOnInt(1, Ry))([qs[0]], (2.0 * PI()/4.0, qs[1]));
    // In this special case the second Controlled Ry is eqivalent to a Controlled H:
    // Controlled H([qs[0]], qs[1]);
}
```

[Return to task 12 of the Superposition kata.](./Superposition.ipynb#hardy-state)

## <a name="superposition-of-zero-and-given-bit-string"></a> Task 13. Superposition of $|0 \dots 0\rangle$ and the given bit string.

**Inputs:** 

1. $N$ ($N \ge 1$) qubits in the $|0 \dots 0\rangle$ state.
2. A bit string of length $N$ represented as `Bool[]`. Bit values `false` and `true` correspond to $|0\rangle$ and $|1\rangle$ states. You are guaranteed that the first bit of the bit string is `true`.

**Goal:**  Change the state of the qubits to an equal superposition of $|0 \dots 0\rangle$ and the basis state given by the bit string.

> For example, for the bit string `[true, false]` the state required is $\frac{1}{\sqrt{2}}\big(|00\rangle + |10\rangle\big)$.

### Solution

> A common strategy for preparing a superposition state in a qubit register is using an auxiliary qubit (or several, for more complicated states). The auxiliary qubit can be put into a superposition state through the usual means of applying a Hadamard gate (or a rotation about the Y axis for an uneven superposition). 
> Then the basis states of the desired superposition are prepared individually based on the auxiliary qubit state by using it as the control qubit for a CNOT gate. One of the basis states will be prepared controlled on the $|0\rangle$ component of the auxiliary state, and the other - controlled on the $|1\rangle$ component. 
> Finally, you have to return the auxiliary qubit to the $|0\rangle$ state by uncomputing it, i.e., by using the basis state prepared from the $|1\rangle$ component as the control qubits for a CNOT gate with the auxiliary qubit as the target. 
>
> More details on using this approach can be found in the solution to tasks [15](#superposition-of-four-bit-strings) and [16](#wstate-on-2k-qubits). However, for this task we can come up with a simpler solution. 
> Instead of allocating a new qubit to use as the auxiliary, we can use the first qubit in the register for this purpose, because we are guaranteed that the first bit in the two basis vectors that comprise the required superposition is different.
> This saves us the need to allocate a new qubit and lets us skip the uncomputing step, as the qubit acting as the control for the next preparation steps is part of the desired result.

Consider the earlier tasks in this kata that asked to prepare Bell states and GHZ state; the structure of the superposition state in this task is a more general case of those scenarios: all of them ask to prepare an equal superposition of two different basis states.

The first step of the solution is the same as in those tasks: put the first qubit in the register into an equal superposition of $|0\rangle$ and $|1\rangle$ using the H gate to get the following state:

$$\frac{1}{\sqrt2} (|0\rangle + |1\rangle) \otimes |0 \dots 0\rangle = \frac{1}{\sqrt2} (|00 \dots 0\rangle + |10 \dots 0\rangle)$$

The first term of the superposition already matches the desired state, so we need to fix the second term.
To do that, we will walk through the remaining qubits in the register, checking if the bit in the corresponding position of the bit string `bits` is `true`. 
If it is, that qubit's state needs to be adjusted from $0$ to $1$ in the second term of our superposition (and left unchanged in the first term). 
We can do this change using the CNOT gate with the first qubit as the control and the current qubit as the target.
When we have finished walking through the register like this, the register will be in the desired superposition.


```qsharp
%kata T13_ZeroAndBitstringSuperposition_Test

operation ZeroAndBitstringSuperposition (qs : Qubit[], bits : Bool[]) : Unit {
    H(qs[0]);

    for (i in 1 .. Length(qs) - 1) {
        if (bits[i]) {
            CNOT(qs[0], qs[i]);
        }
    }
}
```

[Return to task 13 of the Superposition kata.](./Superposition.ipynb#superposition-of-zero-and-given-bit-string)

### <a name="superposition-of-two-bit-strings"></a> Task 14. Superposition of two bit strings.

**Inputs:** 

1. $N$ ($N \ge 1$) qubits in the $|0 \dots 0\rangle$ state.
2. Two bit strings of length $N$ represented as `Bool[]`s. Bit values `false` and `true` correspond to $|0\rangle$ and $|1\rangle$ states. You are guaranteed that the two bit strings differ in at least one bit.

**Goal:**  Change the state of the qubits to an equal superposition of the basis states given by the bit strings.

> For example, for bit strings `[false, true, false]` and `[false, false, true]` the state required is $\frac{1}{\sqrt{2}}\big(|010\rangle + |001\rangle\big)$.

### Solution

The strategy of using an auxiliary qubit to control the preparation process described in the previous task can be applied to this task as well. 

We will start by allocating an auxiliary qubit and preparing it in the $\frac{1}{\sqrt2} (|0\rangle + |1\rangle)$ state using the H gate. The overall state of the system will be 

$$\frac{1}{\sqrt2} (|0\rangle + |1\rangle)_a \otimes |0 \dots 0\rangle_r = \frac{1}{\sqrt2} (|0\rangle_a \otimes |0 \dots 0\rangle_r + |1\rangle_a \otimes |0 \dots 0\rangle_r)$$

At this point, we can prepare the two basis states of the target state separately, bit by bit, controlling the preparation of one of them on the $|0\rangle$ state of the auxiliary qubit and the preparation of the other one - on the $|1\rangle$ state. 
If a bit in one of the bit strings is `true`, we will apply a controlled X gate with the auxiliary qubit as control, the qubit in the corresponding position of the register as target, and control it on the $|0\rangle$ or the $|1\rangle$ state depending on which bit string we are considering at the moment. 
Such controlled gate can be implemented using [`ControlledOnInt`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonint) library function.

After this the state of the system will be 
$$\frac{1}{\sqrt2} (|0\rangle_a \otimes |bits_1\rangle_r + |1\rangle_a \otimes |bits_2\rangle_r)$$

Finally, we will uncompute the auxiliary qubit by using [`ControlledOnBitString`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonbitstring) library function with the second bit string and the `X` operation as arguments, the quantum register as the control, and the auxiliary qubit as the target. 
This will affect only the $|1\rangle_a \otimes |bits_2\rangle_r$ term, flipping the state of the auxiliary qubit in it and bringing the system to its final state:

$$|0\rangle_a \otimes \frac{1}{\sqrt2} (|bits_1\rangle + |bits_2\rangle)_r$$


```qsharp
%kata T14_TwoBitstringSuperposition_Test

operation TwoBitstringSuperposition (qs : Qubit[], bits1 : Bool[], bits2 : Bool[]) : Unit {
    using (q = Qubit()) {
        H(q);
        
        for (i in 0 .. Length(qs) - 1) {
            if (bits1[i]) {
                (ControlledOnInt(0, X))([q], qs[i]);
            }
            if (bits2[i]) {
                (ControlledOnInt(1, X))([q], qs[i]);
            }
        }
        
        // uncompute the auxiliary qubit to release it
        (ControlledOnBitString(bits2, X))(qs, q);
    }
}
```

It is also possible to solve the task without using an extra qubit, if instead we use one of the qubits in the register in this role. 
While walking through the register and bit strings, the first time the bit strings disagreed, the qubit in the corresponding position would take on the role of the auxiliary qubit; we would put it in superposition using the H gate and perform all subsequent bit flips using that qubit as the control. 

This saves us an additional qubit and allows to skip the uncomputing step, though the code becomes less elegant. 
We will move the classical logic of comparing two bit strings to find the first position in which they differ to a function `FindFirstDiff`; note that it has to be defined in a separate code cell.


```qsharp
function FindFirstDiff (bits1 : Bool[], bits2 : Bool[]) : Int {
    for (i in 0 .. Length(bits1) - 1) {
        if (bits1[i] != bits2[i]) {
            return i;
        }
    }
    return -1;
}
```


```qsharp
%kata T14_TwoBitstringSuperposition_Test

operation TwoBitstringSuperposition (qs : Qubit[], bits1 : Bool[], bits2 : Bool[]) : Unit {
    // find the index of the first bit at which the bit strings are different
    let firstDiff = FindFirstDiff(bits1, bits2);

    // Hadamard corresponding qubit to create superposition
    H(qs[firstDiff]);

    // iterate through the bit strings again setting the final state of qubits
    for (i in 0 .. Length(qs) - 1) {
        if (bits1[i] == bits2[i]) {
            // if two bits are the same, apply X or nothing
            if (bits1[i]) {
                X(qs[i]);
            }
        } else {
            // if two bits are different, set their difference using CNOT
            if (i > firstDiff) {
                CNOT(qs[firstDiff], qs[i]);
                if (bits1[i] != bits1[firstDiff]) {
                    X(qs[i]);
                }
            }
        }
    }
}
```

[Return to task 14 of the Superposition kata.](./Superposition.ipynb#superposition-of-two-bit-strings)

### <a name="superposition-of-four-bit-strings"></a>Task 15*. Superposition of four bit strings.

**Inputs:** 

1. $N$ ($N \ge 1$) qubits in the $|0 \dots 0\rangle$ state.
2. Four bit strings of length $N$, represented as `Bool[][]` `bits`. `bits` is an $4 \times N$ array which describes the bit strings as follows: `bits[i]` describes the `i`-th bit string and has $N$ elements. You are guaranteed that all four bit strings will be distinct.

**Goal:**  Change the state of the qubits to an equal superposition of the four basis states given by the bit strings.

> For example, for $N = 3$ and `bits = [[false, true, false], [true, false, false], [false, false, true], [true, true, false]]` the state required is $\frac{1}{2}\big(|010\rangle + |100\rangle + |001\rangle + |110\rangle\big)$.

### Solutions
#### Solution 1

We are going to use the same trick of auxiliary qubits that we used in [the previous task](#superposition-of-two-bit-strings). 
Since the desired superposition has 4 basis states with equal amplitudes, we are going to need two qubits to define a unique basis to control preparation of each of the basis states in the superposition. 

We start by allocating two extra qubits and preparing an equal superposition of all 2-qubit states on them by applying an H gate to each of them:

$$\frac12 (|00\rangle + |01\rangle + |10\rangle + |11\rangle)_a \otimes |0 \dots 0\rangle_r$$

Then, for each of the four given bit strings, we walk through it and prepare the matching basis state on the main register of qubits, using controlled X gates with the corresponding basis state of the auxiliary qubits as control. 
For example, when preparing the bit string `bits[0]`, we apply X gates controlled on the basis state $|00\rangle$; when preparing the bit string `bits[1]`, we apply X gates controlled on $|10\rangle$, and so on.

> We can choose an arbitrary matching of the 2-qubit basis states used as controls and the bit strings prepared on the main register. 
> Since all amplitudes are the same, the result does not depend on which state controlled which bit string preparation.
> It can be convenient to use indices of the bit strings, converted to little-endian, to control preparation of the bit strings.
> Q# library function [`ControlledOnInt`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonint) does exactly that.

After this the system will be in the state 

$$\frac12 (|00\rangle_a |bits_0\rangle_r + |10\rangle_a |bits_1\rangle_r + |01\rangle_a |bits_2\rangle_r + |11\rangle_a |bits_3\rangle_r)$$

As the last step, we must uncompute the auxiliary qubits, i.e., return them to the $|00\rangle$ state to unentangle them from the main register. 
Same as we did in the previous task, we will use [`ControlledOnBitString`](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.canon.controlledonbitstring) with the corresponding bit string and the X operation as arguments, the quantum register as the control, and the auxiliary qubits as the target. 
We will uncompute each of them separately, so one of the auxiliary qubits will be uncomputed with the `bits[1]` and `bits[3]` bit strings as controls, and the other - with the `bits[2]` and `bits[3]`.


```qsharp
%kata T15_FourBitstringSuperposition_Test

operation FourBitstringSuperposition (qs : Qubit[], bits : Bool[][]) : Unit {
    using (anc = Qubit[2]) {
        // Put two ancillas into equal superposition of 2-qubit basis states
        ApplyToEachA(H, anc);

        // Set up the right pattern on the main qubits with control on ancillas
        for (i in 0 .. 3) {
            for (j in 0 .. Length(qs) - 1) {
                if (bits[i][j]) {
                    (ControlledOnInt(i, X))(anc, qs[j]);
                }
            }
        }

        // Uncompute the ancillas, using patterns on main qubits as control
        for (i in 0 .. 3) {
            if (i % 2 == 1) {
                (ControlledOnBitString(bits[i], X))(qs, anc[0]);
            }
            if (i / 2 == 1) {
                (ControlledOnBitString(bits[i], X))(qs, anc[1]);
            }
        }
    }
}
```

#### Solution 2

We are going to leverage the recursion abilities of Q# to create a superposition of the four bit strings.  This solution also extends to an arbitrary number of bit strings with no code changes.

For this process we will look at the first bits of each string and adjust the probability of measuring a $|0\rangle$ or $|1\rangle$ accordingly on the first qubit of our answer.  We will then recursively call (as needed) the process again to adjust the probabilities of measurement on the second bit depending on the first bit.  This process recurses until no more input bits are provided.

Consider for example the following four bit strings on which to create a superposition: 
$|001\rangle, |101\rangle, |111\rangle, |110\rangle$.

We can rewrite the superposition state we need to prepare as

$$\frac12 \big(|001\rangle + |101\rangle + |111\rangle + |110\rangle \big) = \frac12 |0\rangle \otimes |01\rangle + \frac{\sqrt3}{2} |1\rangle \otimes \frac{1}{\sqrt3} \big(|10\rangle + |11\rangle + |10\rangle \big)$$

As the first step of the solution, we need to prepare a state $\frac12 |0\rangle + \frac{\sqrt3}{2} |1\rangle$ on the first qubit (to measure $|0\rangle$ with $\frac14$ probability and to measure $|1\rangle$ with $\frac34$ probability).  To do this, we will apply an [`Ry`](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic.ry) rotation to the first qubit.

After this, we'll need to prepare the rest of the qubits in appropriate states depending on the state of the first qubit - state $|01\rangle$ if the first qubit is in state $|0\rangle$ and state $\frac{1}{\sqrt3} \big(|10\rangle + |11\rangle + |10\rangle \big)$ if the first qubit is in state $|1\rangle$. We can do this recursively using the same logic. Let's finish walking through this example in detail.

The second qubit of the recursion follows similarly but depends on the first qubit.  If the first qubit measures $|0\rangle$, then we want the second qubit to measure $|0\rangle$ with 100% probability, but if it measures $|1\rangle$, we want it to measure $|0\rangle$ with $\frac13$ probability and $|1\rangle$ with $\frac23$ probability.  For this, we can do a controlled [`Ry`](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic.ry) rotation on the second qubit with the first qubit as control.

The third qubit in this example will have three cases because it depends on the first two qubits; this follows naturally from the recursion.

1. If the first two qubits measure $|00\rangle$, then we need the third qubit to measure $|0\rangle$ with 100% probability.  
2. If the first two qubits measure $|10\rangle$, then we need the third qubit to measure $|1\rangle$ with 100% probability.  
3. If the first two qubits measure $|11\rangle$, then we need the third qubit to measure $|0\rangle$ with $\frac12$ probability and $|1\rangle$ with $\frac12$ probability.  Just as with the second qubit, a controlled [`Ry`](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic.ry) rotation on the third qubit will accomplish this goal.  

> We will use [ControlledOnBitString](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.canon.controlledonbitstring) operation to perform rotations depending on the state of several previous qubits.


```qsharp
%kata T15_FourBitstringSuperposition_Test

open Microsoft.Quantum.Convert;
open Microsoft.Quantum.Math;

operation FourBitstringSuperposition (qs : Qubit[], bits : Bool[][]) : Unit {
    FourBitstringSuperposition_Recursive(new Bool[0], qs, bits);
}

operation FourBitstringSuperposition_Recursive (currentBitString : Bool[], qs : Qubit[], bits : Bool[][]) : Unit {
    // an array of bit strings whose columns we are considering begin with |0⟩
    mutable zeroLeads = new Bool[][0];
    // an array of bit strings whose columns we are considering begin with |1⟩
    mutable oneLeads = new Bool[][0];
    // the number of bit strings we're considering
    let rows = Length(bits);
    // the current position we're considering
    let currentIndex = Length(currentBitString);
    
    if (rows >= 1 and currentIndex < Length(qs)) {
        // figure out what percentage of the bits should be |0⟩
        for (row in 0..rows-1) {
            if (bits[row][currentIndex]) {
                set oneLeads = oneLeads + [bits[row]];
            } else {
                set zeroLeads = zeroLeads + [bits[row]];
            }
        }       
        // rotate the qubit to adjust coefficients based on the previous bit string
        // for the first path through, when the bit string has zero length, 
        // the Controlled version of the rotation will perform a regular rotation
        let theta = ArcCos(Sqrt(IntAsDouble(Length(zeroLeads)) / IntAsDouble(rows)));
        (ControlledOnBitString(currentBitString, Ry))(qs[0 .. currentIndex - 1], 
                                                      (2.0 * theta, qs[currentIndex]));
        
        // call state preparation recursively based on the bit strings so far
        FourBitstringSuperposition_Recursive(currentBitString + [false], qs, zeroLeads);
        FourBitstringSuperposition_Recursive(currentBitString + [true], qs, oneLeads);
    } 
}
```

[Return to task 15 of the Superposition kata.](./Superposition.ipynb#superposition-of-two-bit-strings)

### <a name="wstate-on-2k-qubits"></a>Task 16**. W state on $2^k$ qubits.

**Input:** $N = 2^k$ qubits in the $|0 \dots 0\rangle$ state.

**Goal:**  Change the state of the qubits to the [W state](https://en.wikipedia.org/wiki/W_state) - an equal superposition of $N$ basis states on $N$ qubits which have Hamming weight of 1.

> For example, for $N = 4$ the required state is $\frac{1}{2}\big(|1000\rangle + |0100\rangle + |0010\rangle + |0001\rangle\big)$.

### Solution

The problem becomes more manageable if broken down into the simplest cases and built up from there. 

1. The smallest instance of the problem, $N = 1$, requires preparing $|W_1\rangle = |1\rangle$; this can be done trivially using an X gate.

2. The next instance, $N = 2$, requires preparing $|W_2\rangle = \frac{1}{\sqrt2}\big(|10\rangle + |01\rangle\big)$. 
It matches one of the Bell states we've seen earlier, but preparing it will be more interesting (and more useful for the next steps!) if we think of it in recursive terms.
Let see how to express $|W_2\rangle$ in terms of $|W_1\rangle$:

$$|W_2\rangle = \frac{1}{\sqrt2}\big(|10\rangle + |01\rangle\big) = \frac{1}{\sqrt2}\big(|W_1\rangle \otimes |0\rangle + |0\rangle \otimes |W_1\rangle\big)$$

This representation suggests us a solution: "split" the starting state $|00\rangle$ in two terms, prepare $|W_1\rangle$ on the first qubit for the first term and on the second qubit - for the second term. 
To do this, we can again use an auxiliary qubit prepared in the $|+\rangle$ state and control the preparation of $|W_1\rangle$ state on the first or the second qubit based on the state of the auxiliary qubit:

$$|0\rangle_{aux} |00\rangle_{reg} \overset{H}{\longrightarrow} 
\frac{1}{\sqrt2}(|0\rangle + |1\rangle)_{aux} \otimes |00\rangle_{reg} = 
\frac{1}{\sqrt2}(|0\rangle_{aux} |00\rangle_{reg} + |1\rangle_{aux} |00\rangle_{reg})
\overset{CNOT_0}{\longrightarrow} \\ {\longrightarrow}
\frac{1}{\sqrt2}(|0\rangle_{aux} |W_1\rangle|0\rangle_{reg} + |1\rangle_{aux} |00\rangle_{reg})
\overset{CNOT_1}{\longrightarrow} \\ {\longrightarrow}
\frac{1}{\sqrt2}(|0\rangle_{aux} |W_1\rangle|0\rangle_{reg} + |1\rangle_{aux} |0\rangle|W_1\rangle_{reg})
$$

> The auxiliary qubit is now entangled with the rest of the qubits, so we can't simply reset it without it affecting the superposition we have prepared using it.

The last step to bring the register to the desired state is to uncompute the auxiliary qubit for the term $|1\rangle_{aux} |0\rangle|W_1\rangle_{reg}$ (the other term already has it in state $|0\rangle$).

To do this, we need to consider the explicit expression of the state $|0\rangle|W_1\rangle = |01\rangle$.
Similarly to the previous tasks, we'll uncompute the auxiliary qubit for this term by using a controlled X gate, with the auxiliary qubit as the target and the main register in the $|01\rangle$ state as a control.
This will make sure that the gate is applied only for this term and not for any others.

The last step can be simplified to use fewer qubits as controls: we can use just the second qubit of the main register in state $|1\rangle$ as control, since we know that if the second qubit is in state $|1\rangle$, the first one has to be in state $|0\rangle$ (we don't need to use both of them as the control pattern).

3. If we take this one step further, to $N = 4$, we'll see that the same recursive logic can be applied to the larger and larger sizes of the problem. Indeed,

$$|W_4\rangle = \frac{1}{2}\big(|1000\rangle + |0100\rangle + |0010\rangle + |0001\rangle\big) = \\
= \frac{1}{\sqrt2} \big(\frac{1}{\sqrt2}(|10\rangle + |01\rangle) \otimes |00\rangle + |00\rangle \otimes \frac{1}{\sqrt2}(|10\rangle + |01\rangle) = \\
= \frac{1}{\sqrt2} \big(|W_2\rangle \otimes |00\rangle + |00\rangle \otimes |W_2\rangle\big)
$$

We can use the same approach for this case: prepare an auxiliary qubit in $|+\rangle$ state and use it to control preparation of $W_2$ state on the first and the second half of the register. 
The last step will be uncomputing the $|1\rangle$ state of the auxiliary qubit using two controlled X gates with each of the qubits of the second half of the register in state $|1\rangle$ as controls. 

The same recursive approach can be generalized for arbitrary powers of 2 as the register size.


```qsharp
%kata T16_WState_PowerOfTwo_Test

operation WState_PowerOfTwo (qs : Qubit[]) : Unit is Adj+Ctl {
    let N = Length(qs);

    if (N == 1) {
        // base of recursion: |1⟩
        X(qs[0]);
    } else {
        let K = N / 2;
        using (anc = Qubit()) {
            H(anc);
            
            (ControlledOnInt(0, WState_PowerOfTwo))([anc], qs[0 .. K - 1]);
            (ControlledOnInt(1, WState_PowerOfTwo))([anc], qs[K .. N - 1]);

            for (i in K .. N - 1) {
                CNOT(qs[i], anc);
            }
        }
    }
}
```

This implementation of the recursion requires $\log_2 N = k$ extra qubits allocated for controlling the preparation (one per level of recursion). 
We can modify our approach to use just one extra qubit at a time.

To do this, let's notice that to prepare $|W_{N}\rangle$ we need to prepare the $|W_{N-1}\rangle$ state on half of the qubits for both states of the auxiliary qubit, the difference is just in which half of the register we're using. 
This means that we can prepare the $|W_{N-1}\rangle$ state on the first half of the qubits, and use an auxiliary qubit in superposition to control SWAP-ing the first half of the register with the second half.
The uncomputation of the auxiliary qubit happens in the same way as in the first approach.


```qsharp
%kata T16_WState_PowerOfTwo_Test

operation WState_PowerOfTwo (qs : Qubit[]) : Unit is Adj+Ctl {
    let N = Length(qs);

    if (N == 1) {
        // base of recursion: |1⟩
        X(qs[0]);
    } else {
        let K = N / 2;
        WState_PowerOfTwo(qs[0 .. K - 1]);

        using (anc = Qubit()) {
            H(anc);

            for (i in 0 .. K - 1) {
                Controlled SWAP([anc], (qs[i], qs[i + K]));
            }
            for (i in K .. N - 1) {
                CNOT(qs[i], anc);
            }
        }
    }
}
```

[Return to task 16 of the Superposition kata.](./Superposition.ipynb#wstate-on-2k-qubits)

### <a name="wstate-on-arbitray-number-of-qubits"></a>Task 17**. W state on an arbitrary number of qubits.

**Input:** $N$ qubits in the $|0 \dots 0\rangle$ state ($N$ is not necessarily a power of 2).

**Goal:**  Change the state of the qubits to the [W state](https://en.wikipedia.org/wiki/W_state) - an equal superposition of $N$ basis states on $N$ qubits which have Hamming weight of 1.

> For example, for $N = 3$ the required state is $\frac{1}{\sqrt{3}}\big(|100\rangle + |010\rangle + |001\rangle\big)$.

### Solution

This problem allows a variety of solutions that rely on techniques from arbitrary rotations to recursion to postselection. 

The first approach we will describe relies on performing a sequence of controlled rotations.

To prepare a weighted superposition $\cos \theta |0\rangle + \sin \theta |1\rangle$ on a single qubit, we need to start with the $|0\rangle$ state and apply the [Ry gate](https://docs.microsoft.com/qsharp/api/qsharp/microsoft.quantum.intrinsic.ry) to it with the angle parameter equal to $2 \theta$. 
We'll apply the Ry gate with angle $2 \theta_1 = 2\arcsin \frac{1}{\sqrt{N}}$ to the first qubit of the register to prepare the following state:

$$(\cos \theta_1 |0\rangle + \sin \theta_1 |1\rangle) \otimes |0 \dots 0\rangle = \frac{1}{\sqrt{N}}|10 \dots 0\rangle + \frac{\sqrt{N-1}}{\sqrt{N}}|00 \dots 0\rangle $$

The first term $\frac{1}{\sqrt{N}}|10 \dots 0\rangle$ already matches the first term of the $|W_N\rangle$ state; now we need to convert the second term $\frac{\sqrt{N-1}}{\sqrt{N}}|00 \dots 0\rangle$ into the rest of the $|W_N\rangle$ terms.

To prepare a term that matches the second term of the $|W_N\rangle$ state, we can apply another Ry gate to the term $|00 \dots 0\rangle$, this time to the second qubit, with an angle $2 \theta_2 = 2\arcsin \frac{1}{\sqrt{N-1}}$.
To make sure it doesn't affect the term that we're already happy with, we will apply a controlled version of the Ry gate, with the first qubit of the register in state $|0\rangle$ as control.
This will change our state to

$$\frac{1}{\sqrt{N}}|10 \dots 0\rangle + \frac{\sqrt{N-1}}{\sqrt{N}} |0\rangle \otimes (\cos \theta_2 |0\rangle + \sin \theta_2 |1\rangle) \otimes |0 \dots 0\rangle = \\ 
= \frac{1}{\sqrt{N}}|10 \dots 0\rangle + \frac{\sqrt{N-1}}{\sqrt{N}} \frac{1}{\sqrt{N-1}} |010 \dots 0\rangle + \frac{\sqrt{N-1}}{\sqrt{N}} \frac{\sqrt{N-2}}{\sqrt{N-1}} |000 \dots 0\rangle$$

Now we have two terms that match the terms of the $|W_N\rangle$ state, and need to convert the third term $\frac{\sqrt{N-2}}{\sqrt{N}}|00 \dots 0\rangle$ into the rest of terms.

We will keep going like this, preparing one term of the $|W_N\rangle$ state at a time, until the rotation on the last qubit will be an X gate, controlled on all previous qubits being in the $|0 \dots 0\rangle$ state.


```qsharp
%kata T17_WState_Arbitrary_Test

open Microsoft.Quantum.Convert;
open Microsoft.Quantum.Math;

operation WState_Arbitrary (qs : Qubit[]) : Unit {
    let N = Length(qs);
    Ry(2.0 * ArcSin(Sqrt(1.0/IntAsDouble(N))), qs[0]);
    for (i in 1 .. N-1) {
        (ControlledOnInt(0, Ry(2.0 * ArcSin(Sqrt(1.0/IntAsDouble(N - i))), _)))(qs[0 .. i-1], qs[i]);
    }
}
```

We can express the same sequence of gates using recursion, if we notice that 

$$|W_N\rangle = \frac{1}{\sqrt{N}}|10 \dots 0\rangle + \frac{\sqrt{N-1}}{\sqrt{N}}|0\rangle \otimes |W_{N-1}\rangle$$

The first step of the solution would still be applying the Ry gate with angle $2 \theta_1 = 2\arcsin \frac{1}{\sqrt{N}}$ to the first qubit of the register to prepare the following state:

$$\frac{1}{\sqrt{N}}|10 \dots 0\rangle + \frac{\sqrt{N-1}}{\sqrt{N}}|00 \dots 0\rangle $$

But we would express the rest of the controlled rotations as the operation that prepares the $|W_{N-1}\rangle$ state, controlled on the $|0\rangle$ state of the first qubit.

> Note that you don't have to implement the controlled version of the gate yourself; it is sufficient to add `is Adj+Ctl` to the signature of the operation `WState_Arbitrary` to specify that controlled variant has to be generated automatically.


```qsharp
%kata T17_WState_Arbitrary_Test

open Microsoft.Quantum.Convert;
open Microsoft.Quantum.Math;

operation WState_Arbitrary (qs : Qubit[]) : Unit is Adj+Ctl {
    let N = Length(qs);
    Ry(2.0 * ArcSin(Sqrt(1.0/IntAsDouble(N))), qs[0]);
    if (N > 1) {
        (ControlledOnInt(0, WState_Arbitrary))(qs[0 .. 0], qs[1 ...]);
    }
}
```

The last approach we will describe uses a technique that is completely different from the ones you've seen before in this kata: postselection. 

> Note that this approach requires familiarity with measurements of quantum systems, in particular with the effect of partial measurement on a multi-qubit system; you might want to return to it after you've covered the relevant tutorials and katas.

*Coming up soon...*

[Return to task 17 of the Superposition kata.](./Superposition.ipynb#wstate-on-arbitray-number-of-qubits)

41e97fca2142266373f75f42466cad3b9dda2047
ipynb
Jupyter Notebook
Superposition/Workbook_Superposition_Part2.ipynb
KalifiaBillal/QuantumKatas
289997754f30e96dd20dd732188db7ecb44bd390
MIT
Superposition/Workbook_Superposition_Part2.ipynb
KalifiaBillal/QuantumKatas
289997754f30e96dd20dd732188db7ecb44bd390
MIT
Superposition/Workbook_Superposition_Part2.ipynb
KalifiaBillal/QuantumKatas
289997754f30e96dd20dd732188db7ecb44bd390
MIT
Qwen/Qwen-72B
1. YES
2. YES