- \n",
"
- After the first Hadamard gate on qubit 1, the state is transformed from the input state to \n", "\n", "$$\n", "H_1\\vert x_1x_2\\ldots x_n\\rangle = \n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\\vert0\\rangle + \\exp\\left(\\frac{2\\pi i}{2}x_1\\right)\\vert1\\rangle\\right]\n", "\\otimes\n", "\\vert x_2x_3\\ldots x_n\\rangle\n", "$$\n", "\n", "
- After the $UROT_2$ gate on qubit 1 controlled by qubit 2, the state is transformed to\n", "\n", "$$\n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\\vert0\\rangle + \\exp\\left(\\frac{2\\pi i}{2^2}x_2 + \\frac{2\\pi i}{2}x_1\\right)\\vert1\\rangle\\right]\n", "\\otimes\n", "\\vert x_2x_3\\ldots x_n\\rangle\n", "$$\n", "\n", "
- After the application of the last $UROT_n$ gate on qubit 1 controlled by qubit $n$, the state becomes\n", "\n", "$$\n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\\vert0\\rangle + \n", "\\exp\\left(\n", "\\frac{2\\pi i}{2^n}x_n + \n", "\\frac{2\\pi i}{2^{n-1}}x_{n-1} + \n", "\\ldots + \n", "\\frac{2\\pi i}{2^2}x_2 + \n", "\\frac{2\\pi i}{2}x_1\n", "\\right)\n", "\\vert1\\rangle\\right]\n", "\\otimes\n", "\\vert x_2x_3\\ldots x_n\\rangle\n", "$$\n", "\n", "Noting that \n", "\n", "$$\n", "x = 2^{n-1}x_1 + 2^{n-2}x_2 + \\ldots + 2^1x_{n-1} + 2^0x_n\n", "$$\n", "\n", "we can write the above state as \n", "\n", "$$\n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\\vert0\\rangle + \n", "\\exp\\left(\n", "\\frac{2\\pi i}{2^n}x \n", "\\right)\n", "\\vert1\\rangle\\right]\n", "\\otimes\n", "\\vert x_2x_3\\ldots x_n\\rangle\n", "$$\n", "\n", "
- After the application of a similar sequence of gates for qubits $2\\ldots n$, we find the final state to be:\n", "\n", "$$\n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\\vert0\\rangle + \n", "\\exp\\left(\n", "\\frac{2\\pi i}{2^n}x \n", "\\right)\n", "\\vert1\\rangle\\right]\n", "\\otimes\n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\\vert0\\rangle + \n", "\\exp\\left(\n", "\\frac{2\\pi i}{2^{n-1}}x \n", "\\right)\n", "\\vert1\\rangle\\right]\n", "\\otimes\n", "\\ldots\n", "\\otimes\n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\\vert0\\rangle + \n", "\\exp\\left(\n", "\\frac{2\\pi i}{2^{2}}x \n", "\\right)\n", "\\vert1\\rangle\\right]\n", "\\otimes\n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\\vert0\\rangle + \n", "\\exp\\left(\n", "\\frac{2\\pi i}{2^{1}}x \n", "\\right)\n", "\\vert1\\rangle\\right]\n", "$$\n", "\n", "which is exactly the QFT of the input state as derived above with the caveat that the order of the qubits is reversed in the output state.\n", "

- \n",
"
- Apply a Hadamard gate to $\\vert x_1 \\rangle$\n", "\n", "$$\n", "|\\psi_1\\rangle = \n", "\\vert x_3\\rangle\n", "\\otimes\n", "\\vert x_2\\rangle\n", "\\otimes\n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\n", "\\vert0\\rangle + \n", "\\exp\\left(\\frac{2\\pi i}{2}x_1\\right) \n", "\\vert1\\rangle\\right]\n", "$$\n", "\n", "
- Apply a $UROT_2$ gate to $\\vert x_1\\rangle$ depending on $\\vert x_2\\rangle$\n", "\n", "$$\n", "|\\psi_2\\rangle = \n", "\\vert x_3\\rangle\n", "\\otimes\n", "\\vert x_2\\rangle\n", "\\otimes\n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\n", "\\vert0\\rangle + \n", "\\exp\\left(\n", "\\frac{2\\pi i}{2^2}x_2 + \\frac{2\\pi i}{2}x_1\n", "\\right) \n", "\\vert1\\rangle\\right]\n", "$$\n", "\n", "
- Apply a $UROT_3$ gate to $\\vert x_1\\rangle$ depending on $\\vert x_3\\rangle$\n", "\n", "$$\n", "|\\psi_3\\rangle = \n", "\\vert x_3\\rangle\n", "\\otimes\n", "\\vert x_2\\rangle\n", "\\otimes\n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\n", "\\vert0\\rangle + \n", "\\exp\\left(\n", "\\frac{2\\pi i}{2^3}x_3 + \\frac{2\\pi i}{2^2}x_2 + \\frac{2\\pi i}{2}x_1\n", "\\right) \n", "\\vert1\\rangle\\right]\n", "$$\n", "\n", "
- Apply a Hadamard gate to $\\vert x_2 \\rangle$\n", "\n", "$$\n", "|\\psi_4\\rangle = \n", "\\vert x_3\\rangle\n", "\\otimes\n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\n", "\\vert0\\rangle + \n", "\\exp\\left(\n", "\\frac{2\\pi i}{2}x_2\n", "\\right) \n", "\\vert1\\rangle\\right]\n", "\\otimes\n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\n", "\\vert0\\rangle + \n", "\\exp\\left(\n", "\\frac{2\\pi i}{2^3}x_3 + \\frac{2\\pi i}{2^2}x_2 + \\frac{2\\pi i}{2}x_1\n", "\\right) \n", "\\vert1\\rangle\\right]\n", "$$\n", "\n", "
- Apply a $UROT_2$ gate to $\\vert x_2\\rangle$ depending on $\\vert x_3\\rangle$\n", "\n", "$$\n", "|\\psi_5\\rangle = \n", "\\vert x_3\\rangle\n", "\\otimes\n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\n", "\\vert0\\rangle + \n", "\\exp\\left(\n", "\\frac{2\\pi i}{2^2}x_3 + \\frac{2\\pi i}{2}x_2\n", "\\right) \n", "\\vert1\\rangle\\right]\n", "\\otimes\n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\n", "\\vert0\\rangle + \n", "\\exp\\left(\n", "\\frac{2\\pi i}{2^3}x_3 + \\frac{2\\pi i}{2^2}x_2 + \\frac{2\\pi i}{2}x_1\n", "\\right) \n", "\\vert1\\rangle\\right]\n", "$$\n", "\n", "
- Apply a Hadamard gate to $\\vert x_3\\rangle$\n", "\n", "$$\n", "|\\psi_6\\rangle = \n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\n", "\\vert0\\rangle + \n", "\\exp\\left(\n", "\\frac{2\\pi i}{2}x_3\n", "\\right) \n", "\\vert1\\rangle\\right]\n", "\\otimes\n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\n", "\\vert0\\rangle + \n", "\\exp\\left(\n", "\\frac{2\\pi i}{2^2}x_3 + \\frac{2\\pi i}{2}x_2\n", "\\right) \n", "\\vert1\\rangle\\right]\n", "\\otimes\n", "\\frac{1}{\\sqrt{2}}\n", "\\left[\n", "\\vert0\\rangle + \n", "\\exp\\left(\n", "\\frac{2\\pi i}{2^3}x_3 + \\frac{2\\pi i}{2^2}x_2 + \\frac{2\\pi i}{2}x_1\n", "\\right) \n", "\\vert1\\rangle\\right]\n", "$$\n", "\n", "\n", "
- Keep in mind the reverse order of the output state relative to the desired QFT. Therefore, we must reverse the order of the qubits (in this case swap $y_1$ and $y_3$)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 7. Some Notes About the Form of the QFT Circuit " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The example above demonstrates a very useful form of the QFT for $N=2^n$. Note that only the last qubit depends on the values of all the other input qubits and each further bit depends less and less on the input qubits. This becomes important in physical implementations of the QFT, where nearest-neighbor couplings are easier to achieve than distant couplings between qubits.\n", "\n", "Additionally, as the QFT circuit becomes large, an increasing amount of time is spent doing increasingly slight rotations. It turns out that we can ignore rotations below a certain threshold and still get decent results, this is known as the approximate QFT. This is also important in physical implementations, as reducing the number of operations can greatly reduce decoherence and potential gate errors. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 8. Qiskit Implementation\n", "\n", "In Qiskit, the implementation of the $CROT$ gate used in the discussion above is a controlled phase rotation gate. This gate is defined in [OpenQASM](https://github.com/QISKit/openqasm) as\n", "\n", "$$\n", "CP(\\theta) =\n", "\\begin{bmatrix} 1 & 0 & 0 & 0 \\\\ 0 & 1 & 0 & 0 \\\\ 0 & 0 & 1 & 0 \\\\ 0 & 0 & 0 & e^{i\\theta}\\end{bmatrix}\n", "$$\n", "\n", "Hence, the mapping from the $CROT_k$ gate in the discussion above into the $CP$ gate is found from the equation\n", "\n", "$$\n", "\\theta = 2\\pi/2^k = \\pi/2^{k-1}\n", "$$\n", "\n", "### 8.1 Example on 3 Qubits " ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "from numpy import pi\n", "# importing Qiskit\n", "from qiskit import QuantumCircuit, transpile, assemble, Aer, IBMQ\n", "from qiskit.providers.ibmq import least_busy\n", "from qiskit.tools.monitor import job_monitor\n", "from qiskit.visualization import plot_histogram, plot_bloch_multivector" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It is useful to work out the relevant code for the 3-qubit case before generalizing to the $n$-qubit case. First, we must define our quantum circuit:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "qc = QuantumCircuit(3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Note**: Remember that Qiskit's least significant bit has the lowest index (0), thus the circuit will be mirrored through the horizontal in relation to the image in section 5. First, we apply a H-gate to qubit 2 :" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n" ], "text/plain": [ "