# 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 has to remain unchanged, while the qubit should acquire a phase that depends on the value of the qubits in the register. 

Since the register is a quantum register and can be in a superposition of basis states, we cannot just measure the register and then conditionally apply the operation from task 1.3. So, we have to convert our solution to task 1.3 from using the `Rotation` operation with classical condition to using it as a controlled operation (with quantum control). 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 task 1.2 was defined to be both adjointable (Adj) and controllable (Ctl), so we don't need to come up with a way to implement its controlled variant manually. All we need to do is go through the qubits in the register and apply the controlled variant of the `Rotation` operation, similarly to the previous task.


```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));
    }
}
```

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

### 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 \big) \otimes |j_2 ... j_n\rangle$.

> 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

First, let's recall task 1.1: 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\rangle$. 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)$$

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

$$\big(H_1\otimes I_{n-1} \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, we can repeat the loop we used in task 1.4 for qubits $|j_2 ... j_n\rangle$ with the first qubit as the target to add the remaining phase terms via the controlled `Rotation` operation.


```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));
    }
}
```

[Return to task 1.5 of the QFT kata.](./QFT.ipynb#Task-1.5.-Prepare-binary-fraction-exponent-in-place-(quantum-input))

### 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 register looks like drawn as a circuit:



This will read as $|x_1 x_2 ... x_n \rangle$. To reverse the order of the qubits, you can use SWAP operations (denoted with double-X), to switch $x_1$ with $x_n$, $x_2$ with $x_{n-1}$, and so on:



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



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]);
    }
}
```

[Return to task 1.6 of the QFT kata.](./QFT.ipynb#Task-1.6.-Reverse-the-order-of-qubits)

### 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}^{2^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\\
\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.

### Solution

Let's use the hint and start by preparing the described state with the qubits reversed:

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

You've already found a way to prepare a binary fraction exponent in place in task 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\rangle$, then applying a succession of controlled rotations using qubits $|j_k\rangle$ with increasing values of $k$ as controls, so that an extra phase term all the way up to $e^{2\pi i \cdot j_n/2^{n}}$ is added with each rotation. 

This will prepare the first qubit in the right state. You'll see that $j_1$ doesn't appear in the rest of the expression for the target state, so we won't need to use it for the rest of the state preparation.


### Solution

Let's use the hint and start by preparing the described state with the qubits reversed:

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

You've already found a way to prepare a binary fraction exponent in place in task 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\rangle$, then applying a succession of controlled rotations using qubits $|j_k\rangle$ with increasing values of $k$ as controls, so that an extra phase term all the way up to $e^{2\pi i \cdot j_n/2^{n}}$ is added with each rotation. 

This will prepare the first qubit in the right state. You'll see that $j_1$ doesn't appear in the rest of the expression for the target state, so we won't need to use it for the rest of the state preparation.

To prepare the remaining qubits in the right states, we can work backwards from this state.
The second qubit in the sequence needs to be prepared in the state $\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_2 ... j_{n-1} j_n} |1\rangle\big)$. 
Similarly, we can do this by applying a Hadamard gate to the qubit $|j_2\rangle$ and then using qubits $|j_3\rangle$ to $|j_n\rangle$ to apply $n-2$ controlled rotation gates with $k=2^2$ to $k=2^{n-1}$ to $|j_2\rangle$. 
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$$

These two steps allow us to see a pattern: for each qubit $j_k, k = 1 .. n$ :

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

The effect of thse steps will be preparing the following 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)\otimes \\ 
\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 \\ 
\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 \\
\otimes \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_n} |1\rangle\big)
$$

The qubits of the system can then be reversed using the task 1.6.



```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);
}
```

You can simulate a circuit summary of this process using `%trace` magic command. Set the parameter **n** to the number of qubits you want to draw the QFT circuit for, then run the cells below.


```qsharp
operation DrawQFTCircuit(n : Int) : Unit {
    use qs = Qubit[n];
    QuantumFourierTransform(qs);
    ResetAll(qs);
}
```


```qsharp
%config trace.defaultDepth=3
%trace DrawQFTCircuit n=3
```

[Return to task 1.7 of the QFT kata.](./QFT.ipynb#Task-1.7.-Quantum-Fourier-transform)

### 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}^{2^n-1} e^{-2\pi i \cdot \frac{jk}{2^{n}}} |k\rangle$.

### 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 implements a unitary transformation $U$ of the quantum state, Adjoint $U$ implements $U^{\dagger}$ automatically.

This means that you can just reuse your solution to task 1.7 with an Adjoint functor!


```qsharp
%kata T18_InverseQFT 

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

[Return to task 1.8 of the QFT kata.](./QFT.ipynb#Task-1.8.-Inverse-QFT)

## Part II. Using the Quantum Fourier Transform

### 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

We can think of the required equal superposition of all basis states as the QFT of the state $|0...0\rangle$. Indeed, if $j_1 = j_2 = ... = j_n = 0$, we get 

$$\frac{1}{\sqrt{2^{n}}} \sum_{k=0}^{2^n-1} e^{2\pi i \cdot \frac{jk}{2^{n}}} |k\rangle = \frac{1}{\sqrt{2^{n}}} \sum_{k=0}^{2^n-1} e^{0} |k\rangle = \frac{1}{\sqrt{2^{n}}} \sum_{k=0}^{2^n-1} |k\rangle$$

This means that we can solve this task by simply calling the QFT on the given register, either the implementation from task 1.7 or the [library function](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.canon.qft).

Note that the library function QFT operates on a big endian register (most significant bit of the number stored first), so the input qubit array has to be converted to a [BigEndian type](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.arithmetic.bigendian) first.


```qsharp
%kata T21_PrepareEqualSuperposition 

open Microsoft.Quantum.Arithmetic;

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

[Return to task 2.1 of the QFT kata.](./QFT.ipynb#Task-2.1.-Prepare-an-equal-superposition-of-all-basis-states)

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

### Solution

Recall the definition of the QFT: 
for a basis state $|j\rangle \in \{|0\rangle, |1\rangle...|2^n-1\rangle\}$, the QFT is defined as 

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

You can see that using $j = F$ will produce the required state. 

You can check that this is the case by going though the example $F=1$ given in the task, by writing $|F\rangle = |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 the 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>

To prepare the state $|F\rangle$ on the input register, you need to convert the integer value $F$ into a binary representation and encode it in the register. 
When writing the code, make sure that you pay attention to whether library functions use little or big endian!  In particular, [IntAsBoolArray](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.convert.intasboolarray) uses little endian encoding, so the result must be reversed before encoding it in the register. 


```qsharp
%kata T22_PreparePeriodicState 

open Microsoft.Quantum.Arithmetic;
open Microsoft.Quantum.Arrays;
open Microsoft.Quantum.Convert;

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));
}
```

[Return to task 2.2 of the QFT kata.](./QFT.ipynb#Task-2.2.-Prepare-a-periodic-state)

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

### Solution 

Since the amplitudes of this state have no imaginary parts, it is clear that the value of exponents for an arbitrary amplitude $e^{2\pi i \cdot \frac{Fk}{2^{n}}}$ 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 be 1: all other bits of $F$ must be $0$. 
Indeed, you can check that using $F = 1$ (in terms of task 2.2) yields the required state.

You can simplify preparing this state: instead of using the general encoding of $F$ in the register, 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](https://docs.microsoft.com/en-us/qsharp/api/qsharp/microsoft.quantum.arrays.head) returns the first element of an array. 


```qsharp
%kata T23_PrepareAlternatingState 

open Microsoft.Quantum.Arithmetic;
open Microsoft.Quantum.Arrays;

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

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

[Return to task 2.3 of the QFT kata.](./QFT.ipynb#Task-2.3.-Prepare-a-periodic-state-with-alternating-$1$-and-$-1$-amplitudes)

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

### Solution
You can see that the superposition of two states from tasks 2.1 and 2.3 will give this result. Indeed,

$$\frac{1}{\sqrt{2^{n-1}}} \big(|0\rangle + |2\rangle + ... + |2^{n}-2\rangle\big)= 
\frac{1}{\sqrt{2}} \bigg( \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)\bigg)$$

Now, we can use the fact that QFT is a linear transformation.
The periodic state from task 2.3 is created by applying the QFT to the $|100...0\rangle$ state, while the state from task 2.1 is created by applying the QFT to the $|000...0\rangle$ state. 
To prepare an equal superposition of these two states, we can create a superposition by applying a Hadamard gate to the first qubit in the register:

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

And then applying the QFT to the register: 

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

This results in the desired end state. 


```qsharp
%kata T24_PrepareEqualSuperpositionOfEvenStates 

open Microsoft.Quantum.Arithmetic;
open Microsoft.Quantum.Arrays;

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

[Return to task 2.4 of the QFT kata.](./QFT.ipynb#Task-2.4.-Prepare-an-equal-superposition-of-all-even-basis-states)

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

### Solution

Writing out the state that we want to get gives us:

$$ |0...00\rangle + |0...01\rangle - |0...10\rangle - |0...11\rangle $$

The states which have 1 as their second-least significant bit have the -1 phase. Written as a tensor product of single-qubit states, this gives:

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

We could try to prepare this state by setting only $j_2$ to 1 and the rest of bits to 0, 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 fix this last phase term, we need cancel out that last $i$ phase in some form. This can be achieved by using the following state as the start:

$$\frac{1}{\sqrt{2}} \big(e^{-i\pi/4} |010...0\rangle + e^{i\pi/4} |110...0\rangle\big)$$

Then,

$$ QFT\bigg(\frac{1}{\sqrt{2}} \big(e^{-i\pi/4} |010...0\rangle + e^{i\pi/4} |110...0\rangle\big)\bigg) = \\
= \frac{1}{\sqrt{2}}\bigg( \frac{1-i}{\sqrt2}QFT|010...0\rangle + \frac{1+i}{\sqrt2}QFT|110...0\rangle \bigg) = \\
= \frac{(1-i)}{2\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)}{2\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}{\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 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 gate twice. 


```qsharp
%kata T25_PrepareSquareWaveSignal 

open Microsoft.Quantum.Arithmetic;

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));
}
```

[Return to task 2.5 of the QFT kata.](./QFT.ipynb#Task-2.5.-Prepare-a-square-wave-signal)

### 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 assumes little endian format of the bit string representation, so you'll need to reverse the array before converting it to an integer. 


```qsharp
%kata T26_Frequency 

open Microsoft.Quantum.Arithmetic;
open Microsoft.Quantum.Arrays;
open Microsoft.Quantum.Measurement;

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

[Return to task 2.6 of the QFT kata.](./QFT.ipynb#Task-2.6.-Get-the-frequency-of-a-signal)

## Part III. Powers and roots of the QFT

*Coming soon...*

37a49f20c7feed66d70570a77718ea9284878be8
ipynb
Jupyter Notebook
QFT/Workbook_QFT.ipynb
TheGupta2012/QuantumKatas
2939724d5c83a8147df97651876e3d2f64f64c56
MIT
2021-08-08T20:30:01.000Z
2021-08-08T20:30:01.000Z
QFT/Workbook_QFT.ipynb
TheGupta2012/QuantumKatas
2939724d5c83a8147df97651876e3d2f64f64c56
MIT
QFT/Workbook_QFT.ipynb
TheGupta2012/QuantumKatas
2939724d5c83a8147df97651876e3d2f64f64c56
MIT
Qwen/Qwen-72B
1. YES
2. YES