# Quantum Fourier Transform

https://en.wikipedia.org/wiki/Quantum_Fourier_transform

## Imports


```python
%matplotlib inline
```


```python
from sympy import init_printing
init_printing(use_latex=True)
```


```python
from ipywidgets import interact, interactive
from IPython.display import clear_output, display, HTML, Audio
```


```python
from sympy import sqrt, symbols, Rational
from sympy import expand, Eq, Symbol, simplify, exp, sin
from sympy.physics.quantum import *
from sympy.physics.quantum.qubit import *
from sympy.physics.quantum.gate import *
from sympy.physics.quantum.grover import *
from sympy.physics.quantum.qft import QFT, IQFT, Fourier
from sympy.physics.quantum.circuitplot import circuit_plot
```

## QFT Gate and Circuit

The Quantum Fourier Transform (QFT) is useful for a quantum algorithm for factoring numbers which is exponentially faster than what is thought to be possible on a classical machine. The transform does a DFT on the state of a quantum system. There is a simple decomposition of the QFT in terms of a few elementary gates.

Build a 3 qubit QFT and decompose it into primitive gates:


```python
fourier = QFT(0,3).decompose()
fourier
```


```python
circuit_plot(fourier, nqubits=3);
```


```python
def plot_qft(n):
    circuit_plot(QFT(0,n).decompose(), nqubits=n)
```


```python
interact(plot_qft, n=(2,8));
```

The QFT circuit can be represented in various symbolic forms.


```python
m = represent(QFT(0,3), nqubits=3)
m
```


```python
represent(Fourier(0,3), nqubits=3)*4/sqrt(2)
```

## QFT in action

Build a 3 qubit state to take the QFT of:


```python
state = (Qubit('000') + Qubit('010') + Qubit('100') + Qubit('110'))/sqrt(4)
state
```

Perform the QFT:


```python
qapply(fourier*state)
```


```python
def apply_qft(n):
    state = Qubit(IntQubit(n, 3))
    result = qapply(QFT(0,3).decompose()*state)
    display(state)
    display(result)
```


```python
interact(apply_qft, n=(0,7));
```

59ed721fae6807065baca27f3837752ee1474699
ipynb
Jupyter Notebook
notebooks/qft.ipynb
gvvynplaine/quantum_notebooks
58783823596465fe2d6c494c2cc3a53ae69a9752
BSD-3-Clause
2017-10-17T22:44:27.000Z
2022-03-28T06:26:46.000Z
notebooks/qft.ipynb
gvvynplaine/quantum_notebooks
58783823596465fe2d6c494c2cc3a53ae69a9752
BSD-3-Clause
2017-10-09T05:16:41.000Z
2018-09-22T03:08:29.000Z
notebooks/qft.ipynb
gvvynplaine/quantum_notebooks
58783823596465fe2d6c494c2cc3a53ae69a9752
BSD-3-Clause
2017-10-09T04:22:19.000Z
2022-03-28T06:25:21.000Z
Qwen/Qwen-72B
1. YES
2. YES