QFT.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Transformada de Fourier Quântica\n",
    "\n",
    "## Introdução\n",
    "A Transformada de Fourier Quântica, ou simplesmente QFT (_**Q**uantum **F**ourier **T**ransform_), é uma implementação da transformada discreta de Fourier para computadores quânticos. A QFT é útil para fatoração de produtos de inteiros primos \\[2\\], para o algoritmo quântico de estimativa de fase \\[6\\], e para aritmética \\[3\\]. A criação da QFT é creditada à Coppersmith \\[1\\].\n",
    "\n",
    "QFT é um operador unitário $U_\\text{QFT}$ que performa o mapeamento $\\lvert X \\rangle \\mapsto \\lvert \\phi(X) \\rangle$, onde $\\lvert X \\rangle$ é definido como:\n",
    "\n",
    "$$\\lvert X \\rangle = \\sum_{j=0}^{M-1} x_j \\lvert j \\rangle$$\n",
    "\n",
    "e $\\lvert \\phi(X) \\rangle$ é definido como:\n",
    "\n",
    "$$\\lvert \\phi(X) \\rangle = \\sum_{k=0}^{M-1} y_k \\lvert k \\rangle, \\quad y_k = \\frac{1}{\\sqrt{N}}\\sum_{j=0}^{N-1}x_j \\omega^{jk}$$\n",
    "\n",
    "$\\omega$ é uma constante definida para $N$ qubits como $\\omega=\\frac{2\\pi i}{2^N}$.\n",
    "\n",
    "É dito que $\\lvert X \\rangle$ é um estado na base computacional e $\\lvert \\phi(X) \\rangle$ é um estado na base de Fourier \\[4\\].\n",
    "\n",
    "Para $N$ qubits, $U_\\text{QFT}$ é uma matriz unitária $\\mathbb{C}^{2^N \\times 2^N}$ que pode ser expandida como:\n",
    "\n",
    "$$U_\\text{QFT} = \\frac{1}{\\sqrt{2^N}}\\begin{bmatrix}\n",
    "    \\ddots & \\vdots & \\\\\n",
    "    \\dots & \\omega^{jk} & \\dots \\\\\n",
    "    & \\vdots & \\ddots\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "Todas as entradas da matriz são $\\omega^{jk}$, onde $j$ é o índice linha da matriz e $k$ é o índice coluna da matriz, ambos valendo de 0 a $2^N-1$.\n",
    "\n",
    "Uma vez que um estado $\\lvert x \\rangle$, tal que $x \\in \\mathbb{N}$, pode ser expandido na forma matricial como:\n",
    "\n",
    "$$\\lvert x \\rangle = \\begin{bmatrix}\\vdots\\\\\\epsilon_j\\\\ \\vdots\\end{bmatrix}, \\quad \\epsilon_j = \\begin{cases}1, \\quad j = x\\\\ 0, \\quad j \\neq x\\end{cases}$$\n",
    "\n",
    "O produto $U_\\text{QFT} \\lvert x \\rangle$ pode ser expandindo na forma matricial como:\n",
    "\n",
    "$$U_\\text{QFT} \\lvert x \\rangle = \\begin{bmatrix}\\vdots\\\\ \\omega^{jx}\\\\ \\vdots\\end{bmatrix}$$\n",
    "\n",
    "Onde $j$ é o índice linha da matriz.\n",
    "\n",
    "## Implementação\n",
    "\n",
    "A QFT é implementada como o seguinte circuito quântico:\n",
    "\n",
    "![QFT](https://upload.wikimedia.org/wikipedia/commons/thumb/6/61/Q_fourier_nqubits.png/1920px-Q_fourier_nqubits.png)\n",
    "\n",
    "Onde $R_l=\\begin{bmatrix}1 & 0 \\\\ 0 & e^{2\\pi i / 2^l}\\end{bmatrix}$.\n",
    "\n",
    "O código a seguir mostra a implementação de uma porta QFT com Qiskit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import qiskit\n",
    "from math import *\n",
    "\n",
    "def qft(n: int) -> qiskit.circuit.Gate:\n",
    "    \"\"\"Returns a QFT gate for n qubits.\n",
    "    :param n: Number of target qubits.\n",
    "    :type n: int\n",
    "    :return: QFT gate.\n",
    "    :rtype: qiskit.circuit.Gate\n",
    "    \"\"\"\n",
    "    def rotations(my_circuit: qiskit.circuit.Gate, m: int):\n",
    "        if m == 0:\n",
    "            return my_circuit\n",
    "        else:\n",
    "            my_circuit.h(m-1) #Add a Haddamard gate to the most significant qubit\n",
    "        \n",
    "            for i in range(m-1):\n",
    "                my_circuit.crz(pi/(2**(m-1-i)), i, m-1)\n",
    "\n",
    "            rotations(my_circuit, m-1) \n",
    "    \n",
    "    my_circuit = qiskit.QuantumCircuit(n, name='QFT')\n",
    "    \n",
    "    rotations(my_circuit, n)\n",
    "\n",
    "    for m in range(n//2):\n",
    "        my_circuit.swap(m, n-m-1)\n",
    "\n",
    "    return my_circuit.to_gate()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Referências\n",
    "\n",
    "1. COPPERSMITH, D. An approximate Fourier transform useful in quantum factoring. arXiv:quant-ph/0201067, 16 jan. 2002.\n",
    "\n",
    "2. SHOR, P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, v. 26, n. 5, p. 1484–1509, out. 1997.\n",
    "\n",
    "3. RUIZ-PEREZ, L.; GARCIA-ESCARTIN, J. C. Quantum arithmetic with the quantum Fourier transform. Quantum Information Processing, v. 16, n. 6, 28 abr. 2017.\n",
    "\n",
    "4. Quantum Fourier Transform. Disponível em: <https://qiskit.org/textbook/ch-algorithms/quantum-fourier-transform.html>.\n",
    "\n",
    "5. NIELSEN, M. A.; CHUANG, I. L. Quantum computation and quantum information. [s.l.] Cambridge Cambridge University Press, 2019.\n",
    "\n",
    "6. KITAEV, A. Y. Quantum measurements and the Abelian Stabilizer Problem. arXiv:quant-ph/9511026, 20 nov. 1995."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}