{ "cells": [ { "cell_type": "markdown", "id": "tested-slave", "metadata": {}, "source": [ "# Quantum Computation - Week 7" ] }, { "cell_type": "markdown", "id": "sized-meter", "metadata": {}, "source": [ " \n", "\n", "## Contents\n", "\n", " \n", "\n", "1. [Quantum Period Finding](#qpf)\n", "2. [Quantum Phase Estimation](#phase)\n", "\n", " " ] }, { "cell_type": "markdown", "id": "appointed-dylan", "metadata": {}, "source": [ "**Module Imports**" ] }, { "cell_type": "code", "execution_count": 5, "id": "chinese-intermediate", "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": "code", "execution_count": 6, "id": "cordless-campaign", "metadata": {}, "outputs": [], "source": [ "# Plot results\n", "def show_results(D):\n", " # D is a dictionary with classical bits as keys and count as value\n", " # example: D = {'000': 497, '001': 527}\n", " plt.bar(range(len(D)), list(D.values()), align='center')\n", " plt.xticks(range(len(D)), list(D.keys()))\n", " plt.show()\n", "\n", "# Execute circuit, display a histogram of the results\n", "def execute_locally(qc, draw_circuit=False):\n", " # Compile and run the Quantum circuit on a simulator backend\n", " backend_sim = Aer.get_backend('qasm_simulator')\n", " job_sim = execute(qc, backend_sim)\n", " result_sim = job_sim.result()\n", " result_counts = result_sim.get_counts(qc)\n", " \n", " # Print the results\n", " print(\"simulation: \\n\\n\", result_counts)\n", " show_results(result_counts)\n", " return result_counts" ] }, { "cell_type": "markdown", "id": "biblical-international", "metadata": {}, "source": [ "\n", " \n", "\n", "## 1. Quantum period finding \n", "\n", " \n", "\n", "Admit a function $f(x)$ from $n$-bit numbers to $m$-bit numbers. Consider $f(x)$ periodic of period $r$, meaning that $\\forall x \\in \\{0,\\cdots,N-r-1\\}$, we have that $f(x) = f(x+r)$ and the values $f(x), f(x+1), \\cdots, f(x+r-1)$ are all distinct. Suppose also that $ r \\leq \\sqrt{N}/2$\n", "\n", "\n", "In a quantum algorithm, this function translates to an $n$-qubit input register and an $m$-qubit output register. We can prepare in the state:\n", "\n", "$$ | \\psi_0 \\rangle = \\frac{1}{\\sqrt{N}} \\sum_{x=0}^{2^n-1} | x\\rangle |0\\rangle$$\n", "\n", "Using $n$ Hadamard gates.\n", "\n", "We then apply a circuit that performs the unitary $\\hat{U}_f$:\n", "\n", "$$\\hat{U}_f | \\psi_0 \\rangle =\\frac{1}{\\sqrt{N}} \\sum_{x=0}^{2^n-1} | x\\rangle | f(x) \\rangle$$\n", "\n", "If we measure the output register _only_ , we get a particular value $a$. The input register will be left in an evenly-weighted superposition of all $x$ such that $f(x) = a$:\n", "\n", "$$\\frac{1}{\\sqrt{N/r}} \\sum_{n=0}^{N/r-1} |x_0 + nr \\rangle | a \\rangle$$\n", "\n", "From now on, we will ignore the output register since the measurement has fixed its state.\n", "\n", "If we apply the QFT to the input register, we will gate a state in the form:\n", "\n", "$$\\sum_{m=0}^{r-1} \\alpha_m |m N/r\\rangle$$\n", "\n", "If we now measure the input register, we would get one value $mN/r$, for some random $m$ between $0$ and $r-1$.\n", "\n", "* This is not enough to tell us the value of $N/r$, but if we run the algorithm $d$ times, we will get a sequence of integers $m_1 N/r, \\cdots, m_d N/r$ which are all multiples of $N/r$.\n" ] }, { "cell_type": "markdown", "id": "dirty-directive", "metadata": {}, "source": [ "