{ "cells": [ { "cell_type": "markdown", "id": "extraordinary-aside", "metadata": {}, "source": [ "# Qiskit 6 - 2020/2021" ] }, { "cell_type": "markdown", "id": "bibliographic-butter", "metadata": {}, "source": [ " \n", "\n", "## Contents\n", "\n", " \n", "1. [Simon's Algorithm](#simon)\n", "\n", "2. [Quantum Fourier Transform](#qft)\n", "\n", " " ] }, { "cell_type": "markdown", "id": "smart-suggestion", "metadata": {}, "source": [ "#### Module imports" ] }, { "cell_type": "code", "execution_count": 3, "id": "opposite-sociology", "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "%matplotlib inline\n", "\n", "# importing Qiskit\n", "from qiskit import Aer, IBMQ\n", "from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister\n", "from qiskit import execute, transpile\n", "\n", "from qiskit.tools.visualization import plot_histogram\n", "\n", "#IBMQ.load_account()\n", "\n", "import math\n", "from math import pi" ] }, { "cell_type": "markdown", "id": "metric-trance", "metadata": {}, "source": [ "# 1. [Simon's Algorithm](https://qiskit.org/textbook/ch-algorithms/simon.html) \n", "\n", " \n", " \n", "\n", "## The problem \n", "\n", "Let $f$ be a blackbox function, $f:\\{0,1\\}^n \\rightarrow \\{0,1\\}^n$.\n", "\n", "$$ f(x) = f(y) \\mbox{ iff } x=y \\mbox{ or } x= y \\oplus s$$\n", "\n", "Find $s$.\n", "\n", "\n", "\n", "\n", "**Exercise:** Implement\n", "\n", "n = 2 and s = 11\n" ] }, { "cell_type": "markdown", "id": "discrete-carnival", "metadata": {}, "source": [ "Two n-qubit input registers are initialized to the zero state: \n", "$$ |\\psi_1 \\rangle = |0\\rangle ^{\\otimes n}|0\\rangle ^{\\otimes n} = |00\\rangle_1 |00\\rangle_2 $$" ] }, { "cell_type": "code", "execution_count": null, "id": "parental-guinea", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "pleased-instruction", "metadata": {}, "source": [ " Apply a Hadamard transform to the first register: \n", " $$ |\\psi_2 \\rangle = \\frac{1}{\\sqrt{2^n}} \\sum _{x \\in \\{0,1\\}^n } |x\\rangle|0\\rangle ^{\\otimes n}$$\n", " \n", " $$\\frac{1}{\\sqrt{2}} ( |00\\rangle_1 + | 01\\rangle_1 + |10\\rangle_1 + |11\\rangle_1 )|00\\rangle_2$$" ] }, { "cell_type": "code", "execution_count": null, "id": "cleared-priority", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "metropolitan-generator", "metadata": {}, "source": [ "Appy oracle:\n", " $$ |\\psi_3 \\rangle = \\frac{1}{\\sqrt{2^n}} \\sum _{x \\in \\{0,1\\}^n } |x\\rangle|f(x)\\rangle $$\n", " \n", " \n", " $$\\frac{1}{2} ( |00\\rangle_1| 00\\rangle_2 + | 10\\rangle_1 |11\\rangle_2 + |10\\rangle_1|11\\rangle_2 +| 11\\rangle |00\\rangle_2)$$" ] }, { "cell_type": "raw", "id": "technological-committee", "metadata": {}, "source": [] }, { "cell_type": "code", "execution_count": null, "id": "basic-stockholm", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "native-stamp", "metadata": {}, "source": [ "Measure the second register. \n", "\n", "$$ |\\psi_4 \\rangle = \\frac{1}{\\sqrt{2}}(|x\\rangle + |y\\rangle )$$\n", "\n", "For instance, if the measument is $11$ then:\n", " $$\\frac{1}{\\sqrt{2}} ( |01 \\rangle_1 + |10 \\rangle_1)$$" ] }, { "cell_type": "code", "execution_count": null, "id": "chronic-uncle", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "mexican-printing", "metadata": {}, "source": [ "Apply Hadamard on the first register:\n", "\n", "$$|\\psi_5 \\rangle =\\frac{1}{\\sqrt{2^{n+1}}}\\sum_{z \\in\\{ 0,1\\}^n}((-1)^{x\\cdot z}+(-1)^{y \\cdot z}) | z \\rangle $$\n", "\n", "$$ \\frac{1}{\\sqrt{2}} (|00\\rangle - |11\\rangle )$$" ] }, { "cell_type": "code", "execution_count": null, "id": "whole-american", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "brazilian-blake", "metadata": {}, "source": [ "Measuring the first register\n", "\n", "$$(-1)^{x \\cdot z} = (-1)^{y \\cdot z}$$" ] }, { "cell_type": "code", "execution_count": null, "id": "satisfactory-vintage", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "capable-hospital", "metadata": {}, "source": [ "\n", "## . Quantum Fourier Transform\n", "\n", " \n", "\n", "The quantum Fourier transform is analogue to the discrete Fourier transform (DFT). Similarly to the classical case, it is a very useful mathematical tool, and a building block in many quantum algorithms, such as quantum phase estimation, computing the discrete logarithm, and Shor's algorithm for factoring.\n", "\n", " \n", "\n", "### (Classical) Fourier Transform\n", "\n", "In modern science and engineering, the Fourier transform is essential for signal processing and communications.\n", "\n", "The FT allows us to extract the underlying periodic behaviour of a function, by decomposing it into its constituent frequencies.\n", "\n", " \n", "\n", "