# QFT Kata Workbook

**What is this workbook?**
A workbook is a collection of problems, accompanied by solutions to them. 
The explanations focus on the logical steps required to solve a problem; they illustrate the concepts that need to be applied to come up with a solution to the problem, explaining the mathematical steps required. 

Note that a workbook should not be the primary source of knowledge on the subject matter; it assumes that you've already read a tutorial or a textbook and that you are now seeking to improve your problem-solving skills. You should attempt solving the tasks of the respective kata first, and turn to the workbook only if stuck. While a textbook emphasizes knowledge acquisition, a workbook emphasizes skill acquisition.

This workbook describes the solutions to the problems offered in the [QFT kata](./QFT.ipynb). 
Since the tasks are offered as programming problems, the explanations also cover some elements of Q# that might be non-obvious for a first-time user.

**What you should know for this workbook**

You should be familiar with the following concepts before tackling the QFT kata (and this workbook):
1. Basic linear algebra
2. The concept of qubit and multi-qubit systems
3. Single-qubit and multi-qubit quantum gates
4. The discrete Fourier transform (DFT) 

## Part I. Implementing Quantum Fourier Transform

This sequence of tasks uses the implementation of QFT described in Nielsen & Chuang.
All numbers in this kata use big endian encoding: most significant bit of the number
 is stored in the first (leftmost) bit/qubit.
 
 What this means is that we can represent a state in reversed bit-string format: <br><br>
 $|x\rangle = x_1x_2..x_n$ = $x_12^{n-1} + x_22^{n-2}+...x_n2^{0}$
 
 We can also make use of the notation for decimals in binary format: 
 
 $0.x_1x_2...x_n = \frac{x_1}{2^{-1}}+ \frac{x_2}{2^{-2}}+...\frac{x_n}{2^{n}}$
 
 

### Task 1.1. 1-qubit QFT

**Input:** 

  A qubit in state $|\psi\rangle = x_0 |0\rangle + x_1 |1\rangle$.

**Goal:**

Apply QFT to this qubit, i.e., transform it to a state
$\frac{1}{\sqrt{2}} \big((x_0 + x_1) |0\rangle + (x_0 - x_1) |1\rangle\big)$.

In other words, transform a basis state $|j\rangle$ into a state $\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot \frac{j}{2}}|1\rangle\big)$ .


### Solution

First, notice that we are dealing with a *single* qubit, which has $N = 2$ possible basis states. 

The transformation of a state $x_0 |0\rangle + x_1 |1\rangle$ to a state $\frac{1}{\sqrt{2}} \big((x_0 + x_1) |0\rangle + (x_0 - x_1) |1\rangle\big)$ is actually just the expression for the transformation of an arbitrary state in the Z basis (a.k.a. the computational basis) to one in the X basis. 

For a starting state $|0\rangle$, $x_0=1$ and $x_1=0$, so the new state will be  $\frac{1}{\sqrt{2}} \big(|0\rangle +|1\rangle\big) = |+\rangle$.
Similarly, for a starting state $|1\rangle$, $x_0=0$ and $x_1=1$, so the new state will be  $\frac{1}{\sqrt{2}} \big(|0\rangle -|1\rangle\big) = |-\rangle$.

We already know a gate that will do this: the Hadamard gate!


```qsharp
%kata T11_OneQubitQFT 

operation OneQubitQFT (q : Qubit) : Unit is Adj+Ctl {
    H(q);
}
```

[Return to task 1.1 of the QFT kata.](./QFT.ipynb#Task-1.1.-1-qubit-QFT)

### Task 1.2. Rotation gate

**Inputs:** 

  1. A qubit in state $|\psi\rangle = \alpha |0\rangle + \beta |1\rangle$.

  2. An integer k $\geq$ 0.

**Goal:** 

Change the state of the qubit to $\alpha |0\rangle + \beta \cdot e^{\frac{2\pi i}{2^{k}}} |1\rangle$.

> Be careful about not introducing an extra global phase! 
This is going to be important in the later tasks.

### Solution

Let's have a look at the gates available under the [Microsoft.Quantum.Intrinsic namespace](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic). 

To avoid adding the extra global phase, we have to use a gate that does not modify the $|0\rangle$ state, and only impacts $|1\rangle$: that is, $U|\psi\rangle = \alpha|0\rangle + \beta \cdot U|1\rangle$.

The [R1Frac gate](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic.r1frac) does exactly that:

$$R1Frac(n,k) = \begin{bmatrix} 1 & 0 \\ 0 & e^{i\pi n/2^{k}} \end{bmatrix} $$

We specify $n=2$ to get the transformation required: 

$$R1Frac(2,k) = \begin{bmatrix} 1 & 0 \\ 0 & e^{2\pi i/2^{k}} \end{bmatrix} $$


```qsharp
%kata T12_Rotation 

operation Rotation (q : Qubit, k : Int) : Unit is Adj+Ctl {
    R1Frac(2, k, q);
}
```

[Return to task 1.2 of the QFT kata.](./QFT.ipynb#Task-1.2.-Rotation-gate)

### Task 1.3. Prepare binary fraction exponent (classical input)

**Inputs:** 

  1. A qubit in state $|\psi\rangle = \alpha |0\rangle + \beta |1\rangle$.

  2. An array of $n$ bits $[j_1, j_2, ..., j_n]$, stored as `Int[]` ($ j_k \in \{0,1\}$).

**Goal:** 

Change the state of the qubit to $\alpha |0\rangle + \beta \cdot e^{2\pi i \cdot 0.j_1 j_2 ... j_n} |1\rangle$,
where $0.j_1 j_2 ... j_n$ is a binary fraction, similar to decimal fractions: 

$$0.j_1 j_2 ... j_n = j_1 \cdot \frac{1}{2^1} + j_2 \cdot \frac{1}{2^2} + ... j_n \cdot \frac{1}{2^n}$$


### Solution

Since we can express the exponent of a sum as a product of exponents ($e^{a+b} = e^a \cdot e^b$), we can implement the required transformation as a sequence of rotation gates from task 1.2 with increasing **k**. 

Each of the individual rotations will use the bit $j_k$ to decide whether to apply the rotation, and the index of that bit $k$ to define the rotation angle.
Note that we only want to apply the rotation if the bit $j_k$ is not zero. 
This means that the gate we apply for each $k$ will be 

$$U_k = \begin{cases}
I, j_k=0 \\
R1Frac(2,k), j_k=1
\end{cases}$$

Recall that 

$$ R1Frac(2,k)\big( \alpha |0\rangle + \beta |1\rangle\big) = \alpha |0\rangle + \beta \cdot e^{2\pi i/2^{k}} |1\rangle = \alpha |0\rangle + \beta \cdot e^{2\pi i \cdot 0. \underset{k-1}{\underbrace{0\dots0}} 1} |1\rangle $$

This means that we can write the overall effect of the gate $U_k$ for each $k$ as 

$$U_k\big( \alpha |0\rangle + \beta |1\rangle\big) = \alpha |0\rangle + \beta \cdot e^{2\pi i \cdot 0. \underset{k-1}{\underbrace{0\dots0}} j_k} |1\rangle$$

As we iterate, the resulting state will get closer and closer to the required one:

<table style="background-color: white; border:1px solid; tr  { background-color:transparent; }">
    <col width=100>
    <col width=500>
    <tr>
        <th style="text-align:center; border:1px solid">Step $k$</th>
        <th style="text-align:center; border:1px solid">State after step $k$</th>
    </tr>
    <tr>
        <td style="text-align:center; border:1px solid">$1$</td>
        <td style="text-align:center; border:1px solid">$$ \alpha |0\rangle + \beta \cdot e^{2\pi i \cdot 0.j_1} |1\rangle $$</td>
    </tr>      
    <tr>
        <td style="text-align:center; border:1px solid">$2$</td>
        <td style="text-align:center; border:1px solid">$$\alpha |0\rangle + \beta \cdot e^{2\pi i j_1 \cdot 2^{-1} + 2\pi i j_2 \cdot 2^{-2}} |1\rangle = \alpha |0\rangle + \beta \cdot e^{2\pi i \cdot 0.j_1j_2} |1\rangle $$</td>
    </tr>      
    <tr>
        <td style="text-align:center; border:1px solid">...</td>
        <td style="text-align:center; border:1px solid">...</td>
    </tr>      
    <tr>
        <td style="text-align:center; border:1px solid">$n$</td>
        <td style="text-align:center; border:1px solid">$$\alpha |0\rangle + \beta \cdot e^{2\pi i \cdot 0.j_1j_2 \dots j_n} |1\rangle $$</td>
    </tr>      
</table>


```qsharp
%kata T13_BinaryFractionClassical 

operation BinaryFractionClassical (q : Qubit, j : Int[]) : Unit is Adj+Ctl {
    for ind in 0 .. Length(j) - 1 {
        if (j[ind] == 1) {
            Rotation(q, ind + 1);
        }
    }
}
```

[Return to task 1.3 of the QFT kata.](./QFT.ipynb#Task-1.3.-Prepare-binary-fraction-exponent-(classical-input))

### Task 1.4. Prepare binary fraction exponent (quantum input)

**Inputs:** 

  1. A qubit in state $|\psi\rangle = \alpha |0\rangle + \beta |1\rangle$.

  2. A register of $n$ qubits in state $|j_1 j_2 ... j_n\rangle$.

**Goal:** 

Change the state of the input
from $(\alpha |0\rangle + \beta |1\rangle) \otimes |j_1 j_2 ... j_n\rangle$
to $(\alpha |0\rangle + \beta \cdot e^{2\pi i \cdot 0.j_1 j_2 ... j_n} |1\rangle) \otimes |j_1 j_2 ... j_n\rangle$,

where $0.j_1 j_2 ... j_n$ is a binary fraction corresponding to the basis state $j_1 j_2 ... j_n$ of the register.

> The register of qubits can be in superposition as well;
the behavior in this case is defined by behavior on the basis states and the linearity of unitary transformations.

### Solution
From the goals section, you can see that the register of *n* qubits remains unchanged, while the qubit acquires a conditional phase that depends on the value of these bits. 

Because the register is now a quantum register and can be in a superposition of states, we cannot measure the register and then conditionally apply the operation depending on whether we measure a 1 or a 0. So, we have to convert our **Rotation** operation into a controlled operation. We can do this with the [**Controlled** functor](https://docs.microsoft.com/en-us/azure/quantum/user-guide/language/expressions/functorapplication#functor-application).

The **Rotation** operation in 1.2 was defined to be both adjointable (Adj) and controllable (Ctl) so all we need to do is go through the qubits in the register and apply the rotation operation conditionally.

A successive application of a *Controlled Rotation (controlqubit, (qubit, k))* operation will effect a controlled rotation operation *n* times, and transform the $\alpha |0\rangle + \beta |1\rangle$ state to $(\alpha |0\rangle + \beta \cdot e^{2\pi i \cdot 0.j_1 j_2 ... j_n} |1\rangle)$, while leaving the register $|j_1 j_2 ... j_n\rangle$ unchanged. 




```qsharp
%kata T14_BinaryFractionQuantum 

operation BinaryFractionQuantum (q : Qubit, jRegister : Qubit[]) : Unit is Adj+Ctl {
    for ind in 0 .. Length(jRegister) - 1 {
        Controlled Rotation([jRegister[ind]], (q, ind + 1));
    }
}
```

### Task 1.5. Prepare binary fraction exponent in place (quantum input)

**Input:** 

 A register of $n$ qubits in state $|j_1 j_2 ... j_n \rangle$.

**Goal:** 

Change the state of the register
from $|j_1\rangle \otimes |j_2 ... j_n\rangle$
to $\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_1 j_2 ... j_n} |1\rangle \otimes |j_2 ... j_n\rangle\big)$.

> The register of qubits can be in superposition as well;
the behavior in this case is defined by behavior on the basis states and the linearity of unitary transformations.

<details>
  <summary><b>Need a hint? Click here</b></summary>
  This task is very similar to task 1.4, but the digit $j_1$ is encoded in-place, using task 1.1.
</details>

### Solution

First, note that a Hadamard gate applied to a single qubit,  $H|j_1\rangle$ will give either
$\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ or $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ depending on the state of $j_1$. This operation can also be written as
$$H|j_1\rangle= \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot \frac{j_1}{2}}|1\rangle\big)= \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_1}|1\rangle\big)$$

Try it out on paper!

So if the starting register state is $|j_1 j_2 ... j_n \rangle$, application of a Hadamard gate to the first bit will result in:

$$\big(H_1\otimes I_n \big) \big(|j_1\rangle \otimes |j_2 ... j_n\rangle\big)= \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_1}|1\rangle\big) \otimes |j_2 ... j_n\rangle $$

After this, it is just a matter of repreating the loop that will add the remaining phase terms via the controlled rotation operator. 

After a repeat of the operations sequence in 1.4, applied to the first register qubit $j_1$, the qubit register's state will be $\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_1 j_2 ... j_n} |1\rangle \otimes |j_2 ... j_n\rangle\big)$




```qsharp
%kata T15_BinaryFractionQuantumInPlace 

operation BinaryFractionQuantumInPlace (register : Qubit[]) : Unit is Adj+Ctl {
     OneQubitQFT(register[0]);
    
        for ind in 1 .. Length(register) - 1 {
            Controlled Rotation([register[ind]], (register[0] , ind + 1));
            
        }
        

     
}
```

### Task 1.6. Reverse the order of qubits

**Input:** 

 A register of $n$ qubits in state $|x_1 x_2 ... x_n \rangle$.

**Goal:** 

Reverse the order of qubits, i.e., convert the state of the register to $|x_n ... x_2 x_1\rangle$.

### Solution

Have a look at what the circuit looks like drawn out:

$x_1$ ---------------- <br>
$x_2$ ----------------<br>
$x_3$ ----------------<br>
...<br>
$x_n$ ----------------<br>

This will read as $|x_1 x_2 ... x_n \rangle$. To reverse the order of the qubits, SWAP operations (denoted with X) must be implemented, switching out $x_1$ with $x_n$, $x_2$ with $x_n-1$ and so on:

$x_1$ ----------------X---  ...<br>
$x_2$ ---------------|---X  ...<br>
$x_3$ ---------------|---|  ...<br>
...<br>
$x_{n-2}$ ------------|---|  ...<br>
$x_{n-1}$ ------------|---X  ...<br>
$x_n$ --------------X---  ...<br>

After N/2 of these swaps, the states will now be: 

$x_n$ ---------------- <br>
$x_{n-1}$ -------------<br>
$x_{n-2}$ -------------<br>
...<br>
$x_1$ ----------------<br>

And the state of the register will be $|x_n ... x_2 x_1\rangle$.



```qsharp
%kata T16_ReverseRegister 

operation ReverseRegister (register : Qubit[]) : Unit is Adj+Ctl {
    let N = Length(register);
    for ind in 0.. N/2-1{
    SWAP(register[ind], register[N - 1 - ind]);
    
    }
}
```

### Task 1.7. Quantum Fourier transform

**Input:** 

 A register of $n$ qubits in state $|j_1 j_2 ... j_n \rangle$.

**Goal:** 

Apply quantum Fourier transform to the input register, i.e., transform it to a state

$$\frac{1}{\sqrt{2^{n}}} \sum_{k=0}^{n-1} e^{2\pi i \cdot \frac{jk}{2^{n}}} |k\rangle = $$
$$\begin{align}= &\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_n} |1\rangle\big) \otimes \\
\otimes &\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_{n-1} j_n} |1\rangle\big) \otimes ... \\
\otimes &\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_1 j_2 ... j_{n-1} j_n} |1\rangle\big)\end{align}$$

> The register of qubits can be in superposition as well;
the behavior in this case is defined by behavior on the basis states and the linearity of unitary transformations.

> You can do this with a library call, but we recommend
implementing the algorithm yourself for learning purposes, using the previous tasks.


<details>
  <summary><b>Need a hint? Click here</b></summary>
Consider preparing a different state first and transforming it to the goal state:

$\frac{1}{\sqrt{2}} (|0\rangle + exp(2\pi i * 0.j_1 j_2 ... j_{n-1} j_n) |1\rangle) \otimes ... \otimes$
$\otimes \frac{1}{\sqrt{2}} (|0\rangle + exp(2\pi i * 0.j_{n-1} j_n) |1\rangle) \otimes$
$\otimes \frac{1}{\sqrt{2}} (|0\rangle + exp(2\pi i * 0.j_n) |1\rangle) \otimes$
</details>

### Solution

You've already found a way to prepare a binary fraction exponent in place from exercise 1.5: the state $\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_1 j_2 ... j_n} |1\rangle\big) \otimes |j_2 ... j_n\rangle$ can be created by first applying the Hadamard gate to qubit $j_1$, then applying a succession of controlled rotations using qubits $j_k$ with increasing values of k, such that an additional phase term all the way up to $e^{2\pi i \cdot j_n/2^{n}}$ is added on each time. 

A Hadamard gate on $j_1$, followed by successive application of the rotation gate as explained above covers the creation of the $\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_1 j_2 ... j_{n-1} j_n} |1\rangle\big)\otimes |j_2 ... j_n\rangle$ state. 

To create the remaining states, work backwards from this state. You can always reverse the order of the states using the operator in 1.6.

The next state in the sequence will be $\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_2 ... j_{n-1} j_n} |1\rangle\big)$. 

This is done by applying a Hadamard gate to qubit $j_2$ and then using qubits $j_3$ to $j_n$ to apply $n-1$ controlled rotation gates with $k=2^2$ to $k=2^{n-1}$ to $j_2$. After this operation, the total system state will be: 

$ \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_1 j_2 ... j_{n-1} j_n} |1\rangle\big)\otimes
\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_2 ... j_{n-1} j_n} |1\rangle\big) \otimes |j_3 ... j_n\rangle$

This creates a pattern. For any qubit $j_k, k= 1 .. n$ :

1. Apply a Hadamard gate to $j_k$
2. Apply the controlled rotation operator $n-k$ times to qubit $j_k$, using qubits $j_k+1$ through $j_n$ as the control, with a phase corresponding to $2^2$ through $2^{n-k+1}$

These two steps, applied for each qubit, create an operator $U$. The effect of the operation $U$ is to create a total system state:  

$$ U|j_1 j_2 ... j_n \rangle= \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_1 j_2 ... j_{n-1} j_n} |1\rangle\big)\otimes \\ \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_2 ... j_{n-1} j_n} |1\rangle\big)\otimes \\ \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_3 ... j_{n-1} j_n} |1\rangle\big)\otimes ... \\
\otimes \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_n} |1\rangle\big)
$$

The system state can then be flipped using the code created in 1.6.

A circuit summary of this process: <br>
<br>




```qsharp
%kata T17_QuantumFourierTransform 

operation QuantumFourierTransform (register : Qubit[]) : Unit is Adj+Ctl {
    let n = Length(register);
        for i in 0 .. n - 1 {
            BinaryFractionQuantumInPlace(register[i ...]);
        }
        ReverseRegister(register);
}
```

### Task 1.8. Inverse QFT

**Input:** 

 A register of $n$ qubits in state $|j_1 j_2 ... j_n \rangle$.

**Goal:** 

Apply inverse QFT to the input register, i.e., transform it to a state 
$\frac{1}{\sqrt{2^{n}}} \sum_{k=0}^{n-1} e^{-2\pi i \cdot \frac{jk}{2^{n}}} |k\rangle$.

<details>
  <summary><b>Need a hint? Click here</b></summary>
Inverse QFT is literally the inverse transformation of QFT.
Do you know a quantum way to express this?
</details>

### Solution

Have a look at the documentation on the [Adjoint Functor](https://docs.microsoft.com/en-us/azure/quantum/user-guide/language/expressions/functorapplication#functor-application).
For an operation that defines a unitary transformation $U$ of the quantum state, Adjoint $U$ accesses the implementation of $U^{\dagger}$.


```qsharp
%kata T18_InverseQFT 

operation InverseQFT (register : Qubit[]) : Unit is Adj+Ctl {
    Adjoint QuantumFourierTransform(register);
}
```

## Part II. Using the Quantum Fourier Transform

This section offers you tasks on state preparation and state analysis 
that can be solved using QFT (or inverse QFT). It is possible to solve them 
without QFT, but we recommend that you to try and come up with a QFT-based solution.

### Task 2.1. Prepare an equal superposition of all basis states

**Input:** 

A register of $n$ qubits in state $|0...0\rangle$.

**Goal:** 

Prepare an equal superposition of all basis vectors from $|0...0\rangle$ to $|1...1\rangle$ 
(i.e., state $\frac{1}{\sqrt{2^{n}}} \big(|0...0\rangle + ... + |1...1\rangle\big)$.

### Solution

Since the QFT of the state $|0...0\rangle$ is simply the superposition of all basis states, this exercise can be solved by simply calling the QFT library function.
Note that the library QFT function operates on a big endian register, so the input register is converted to a big endian type register first. All this does is ensure that the qubit with index 0 encodes the highest bit of an unsigned integer, becoming the state $\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_1 j_2 ... j_{n-1} j_n} |1\rangle\big)$ or $\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot \frac{\textbf{j}}{2^{n}}}|1\rangle\big)$


```qsharp
%kata T21_PrepareEqualSuperposition 

operation PrepareEqualSuperposition (register : Qubit[]) : Unit is Adj+Ctl {
    QFT(BigEndian(register));
}
```

### Task 2.2. Prepare a periodic state

**Inputs:**

  1. A register of $n$ qubits in state $|0...0\rangle$.

  2. An integer frequency F ($0 \leq F \leq 2^{n}-1$).

**Goal:**

Prepare a periodic state with frequency F on this register:

$$\frac{1}{\sqrt{2^{n}}} \sum_k e^{2\pi i \cdot \frac{Fk}{2^{n}}} |k\rangle$$

> For example, for $n = 2$ and $F = 1$ the goal state is $\frac{1}{2}\big(|0\rangle + i|1\rangle - |2\rangle - i|3\rangle\big)$.

> If you're using `DumpMachine` to debug your solution, 
remember that this kata uses big endian encoding of states,
while `DumpMachine` uses little endian encoding.

<details>
  <summary><b>Need a hint? Click here</b></summary>
Which basis state can be mapped to this state using QFT?
</details>

### Solution

Recall the definition of the QFT: 

For a state $|j\rangle$ that is one of the basis of states $\{|0\rangle, |1\rangle...|N-1\rangle\}$  $\epsilon$ $|k\rangle$, the QFT can be defined as 

$$ QFT|j\rangle= \frac{1}{\sqrt{2^n}} \sum_{k=1}^{2^{n}-1} e^{2\pi i j k/2^{n}} |k\rangle$$

You can see that $F = j$. To apply the QFT an create a periodic state, the integer value of $F$ must be converted into a binary representation in the register. You can check that this is the case by writing $F=|j_1j_2\rangle = |01\rangle$ and working through the QFT operation to produce the state $\frac{1}{2}\big(|0\rangle + i|1\rangle - |2\rangle - i|3\rangle\big)$.


<details>
  <summary><b>Click to view steps </b></summary>

For $n=2$, $N=4$ and so: 

 $$QFT |1\rangle = \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_2} |1\rangle\big) \otimes \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_1j_2} |1\rangle\big) = \\
 |00\rangle+ |01\rangle e^{2\pi i \cdot 0.j_1j_2}+ |10\rangle e^{2\pi i \cdot 0.j_2}+ |11\rangle e^{2\pi i \cdot (0.j_1j_2 + 0.j_2)}$$
 
 Evaluating for $j_1=0$ and $j_2=1$ will give $\frac{1}{2}\big(|0\rangle + i|1\rangle - |2\rangle - i|3\rangle\big)$.
    
</details>

In creating the code, make sure that you pay attention to whether library functions use little or big endian!  In particular, IntAsBoolArray uses little endian encoding, so the result must be reversed. 


```qsharp
%kata T22_PreparePeriodicState 

operation PreparePeriodicState (register : Qubit[], F : Int) : Unit is Adj+Ctl {
        
        let bitsBE = Reversed(IntAsBoolArray(F, Length(register)));
        ApplyPauliFromBitString(PauliX, true, bitsBE, register);

        QFT(BigEndian(register));
}
```

### Task 2.3. Prepare a periodic state with alternating $1$ and $-1$ amplitudes

**Input:**

A register of $n$ qubits in state $|0...0\rangle$.

**Goal:**

Prepare a periodic state with alternating $1$ and $-1$ amplitudes of basis states:

$$\frac{1}{\sqrt{2^{n}}} \big(|0\rangle - |1\rangle + |2\rangle - |3\rangle + ... - |2^{n}-1\rangle\big)$$

> For example, for $n = 2$ the goal state is $\frac{1}{2} \big(|0\rangle - |1\rangle + |2\rangle - |3\rangle\big)$.

<details>
  <summary><b>Need a hint? Click here</b></summary>
Which basis state can be mapped to this state using QFT?  Which frequency would allow you to use task 2.2 here?
</details>

### Solution 

Because there is no imagimary part to this state, it is clear that the value of exponents for an arbitrary state  $\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0...j_n} |1\rangle\big)$ must be either $2\pi i$ for a coefficient of 1 or $\pi i$ for a coefficient of -1. This means that only $j_1$ can have a value of 1: all other register qubits must be in the $|0...0\rangle$ state. 

To prepare this state, you can apply an X gate to the first qubit of the register, either as X(qubit[0]) or as X(Head(register)). The *Head* function returns the first element of an array. 


```qsharp
%kata T23_PrepareAlternatingState 

operation PrepareAlternatingState (register : Qubit[]) : Unit is Adj+Ctl {
    X(Head(register));

    QFT(BigEndian(register));
    

}


```

### Task 2.4. Prepare an equal superposition of all even basis states

**Input:** 

A register of $n$ qubits in state $|0...0\rangle$.

**Goal:** 

Prepare an equal superposition of all even basis vectors:
$\frac{1}{\sqrt{2^{n-1}}} \big(|0\rangle + |2\rangle + ... + |2^{n}-2\rangle\big)$.

<details>
  <summary><b>Need a hint? Click here</b></summary>
Which superposition of two basis states can be mapped to this state using QFT?
    Use the solutions to tasks 2.1 and 2.3 to figure out the answer.
</details>

### Solution
You can see that the superposition of two states will give this result. If the periodic state of 2.3 is added to a simple QFT of the $|0....0\rangle$ given in 2.1,

$$\frac{1}{\sqrt{2^{n-1}}} \big(|0\rangle + |2\rangle + ... + |2^{n}-2\rangle\big)= \frac{1}{\sqrt{2^{n}}} \big(|0\rangle - |1\rangle + |2\rangle - |3\rangle + ... - |2^{n}-1\rangle\big) + \frac{1}{\sqrt{2^{n}}} \big(|0\rangle +|1\rangle + |2\rangle + |3\rangle + ... + |2^{n}-1\rangle\big)$$

The periodic state of 2.3 is created by applying the QFT to the $|100...0\rangle$ state, while the state of 2.1 is created by applying the QFT to the $|000...0\rangle$ state. To do both of these simultaneously and observe the cancellation effect, we can use the power of superpositions. Namely. we can create a superposition of the form:

$$ \frac{1}{\sqrt{2^{n}}} \big(|0\rangle + |1\rangle\big) \otimes |000...0\rangle $$
This can be done by applying a Hadamard gate to the first qubit in the register.
Then, by applying the QFT to the entire register, you will get: 

$$ QFT\big(\frac{1}{\sqrt{2^{n}}} (|0\rangle + |1\rangle) \otimes |000...0\rangle\big)= QFT\big(\frac{1}{\sqrt{2^{n}}} \big(|000...0\rangle\big)|\big)+ QFT\big(\frac{1}{\sqrt{2^{n}}} \big(|100...0\rangle\big)\big)$$

This results in the desired end state. 


```qsharp
%kata T24_PrepareEqualSuperpositionOfEvenStates 

operation PrepareEqualSuperpositionOfEvenStates (register : Qubit[]) : Unit is Adj+Ctl {

    H(Head(register));
    QFT(BigEndian(register));
}


```

### Task 2.5. Prepare a square-wave signal

**Input:** 

A register of $n\geq2$ qubits in state $|0...0\rangle$.

**Goal:** 

Prepare a periodic state with alternating $1, 1, -1, -1$ amplitudes of basis states:
$$\frac{1}{\sqrt{2^{n}}} \big(|0\rangle + |1\rangle - |2\rangle - |3\rangle + ... - |2^{n}-2\rangle - |2^{n}-1\rangle\big)$$

<details>
  <summary><b>Need a hint? Click here</b></summary>
Which superposition of two basis states can be mapped to this state using QFT?
    Remember that sum of two complex amplitudes can be a real number if their imaginary parts cancel out.
</details>

### Solution



Writing out the state that we want to achieve will give:

$$ |0...00\rangle + |0...01\rangle - |0...10\rangle - |0...11\rangle $$
Written as a tensor product of single-qubit states, this gives:

$$\frac{1}{\sqrt{2^{n}}} \big(|0\rangle + |1\rangle) \otimes (|0\rangle + |1\rangle) ... \otimes (|0\rangle - |1\rangle) \otimes (|0\rangle + |1\rangle)$$

When expanded, this will give the state required: alternating positive and negative states with a period of 2.

This superposition state can be created by setting only $j_2$ to be 1, then applying the QFT. This will add the required phase of -1 on the second-to-last bit, but will also add a phase term of $i$ on the last bit.
$$QFT(|010...0\rangle) = \frac{1}{\sqrt{2^{n}}}  \big(|0\rangle + |1\rangle) \otimes (|0\rangle + |1\rangle) ... \otimes (|0\rangle - |1\rangle) \otimes (|0\rangle + i|1\rangle)$$
To counter this last phase term, we need cancel out that last $i$ in some form. This can be achieved by creating a superposition state $\frac{e^{(-i\pi/4)}}{\sqrt{2^{n}}} |010...0\rangle + \frac{e^{(i\pi/4)}}{\sqrt{2^{n}}} |110...0\rangle$.

Then,

$$ QFT\big(\frac{e^{(-i\pi/4)}}{\sqrt{2^{n}}} |010...0\rangle + \frac{e^{(i\pi/4)}}{\sqrt{2^{n}}} |110...0\rangle\big) = \\
\frac{(1-i)}{\sqrt{2^{n}}} \big( |0\rangle + |1\rangle) \otimes (|0\rangle + |1\rangle)... |0\rangle - |1\rangle) \otimes (|0\rangle + i|1\rangle)  \big) + \\
\frac{(1+i)}{\sqrt{2^{n}}} \big( |0\rangle + |1\rangle) \otimes (|0\rangle + |1\rangle)... |0\rangle - |1\rangle) \otimes (|0\rangle - i|1\rangle)  \big) $$
 
 This gives a final state of $$\frac{1}{\sqrt{2^{n}}} \big(|0\rangle + |1\rangle) \otimes (|0\rangle + |1\rangle) ... \otimes (|0\rangle - |1\rangle) \otimes (|0\rangle + |1\rangle)$$
 
 Creating the required superposition state is fairly easy; it can be done by using the [T gate](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.intrinsic.t) and its adjoint. 
 You can use the within...apply statements to avoid writing down the X() operator twice. 



```qsharp
%kata T25_PrepareSquareWaveSignal 

operation PrepareSquareWaveSignal (register : Qubit[]) : Unit is Adj+Ctl {
        X(register[1]);
        // |010...0⟩
        H(register[0]);
        // |010...0⟩ + |110...0⟩
        T(register[0]);
        within { X(register[0]); }
        apply { Adjoint T(register[0]); }

        QFT(BigEndian(register));
}
```

### Task 2.6. Get the frequency of a signal

**Input:** 

A register of $n\geq2$ qubits in state 
$\frac{1}{\sqrt{2^{n}}} \sum_k e^{2\pi i \cdot \frac{Fk}{2^{n}}} |k\rangle$, $0\leq F\leq 2^{n}-1$.

**Goal:** 

Return the frequency F of the "signal" encoded in this state.

## Solution

The original Fourier transform will give a time-domain signal's decomposition in the frequency domain, and the inverse Fourier transform will give a frequency-domain signal's time-domain representation.

Keeping this in mind, if we already have the QFT of a state *F* in standard format, the value of *F* can be found by applying the inverse QFT to this register and then measuring the qubits. Since the [QFT](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.canon.qft) operation is adjointable, this is very easy to do. 

Note that the iQFT takes a big endian register as input, but the  **[ResultArrayAsInt](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.convert.resultarrayasint)** function produces a non-negative integer in little endian format. 


```qsharp
 %kata T26_Frequency 

operation Frequency (register : Qubit[]) : Int {
         Adjoint QFT(BigEndian(register));
        let bitsBE = MultiM(register);
        return ResultArrayAsInt(Reversed(bitsBE));
        }
        
        
```


```qsharp

```

1ad03663dfbc9cd071f7345453c95e1b1c3f1d65
ipynb
Jupyter Notebook
QFT/Workbook_QFT.ipynb
WaywardPhoton/QuantumKatas
b04218392c52ee5e655386b4c7f852d8b1cc5ec4
MIT
QFT/Workbook_QFT.ipynb
WaywardPhoton/QuantumKatas
b04218392c52ee5e655386b4c7f852d8b1cc5ec4
MIT
QFT/Workbook_QFT.ipynb
WaywardPhoton/QuantumKatas
b04218392c52ee5e655386b4c7f852d8b1cc5ec4
MIT
Qwen/Qwen-72B
1. YES
2. YES