{ "cells": [ { "cell_type": "markdown", "id": "beneficial-movie", "metadata": {}, "source": [ "# Qiskit 8 \n", "\n", " \n", "\n", "## Contents\n", "\n", " \n", "\n", "1. [Shor's Algorithm](#sa)\n", "2. [Quantum Counting](#qcount)\n", " 1. [Implementation](#impl)" ] }, { "cell_type": "markdown", "id": "flexible-klein", "metadata": {}, "source": [ "**Module Imports**" ] }, { "cell_type": "code", "execution_count": 59, "id": "confident-latest", "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "import numpy as np\n", "import math\n", "\n", "# importing Qiskit\n", "import qiskit\n", "from qiskit import IBMQ, Aer\n", "from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister, execute\n", "\n", "# import basic plot tools\n", "from qiskit.visualization import plot_histogram" ] }, { "cell_type": "code", "execution_count": 64, "id": "enclosed-lawrence", "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": "defensive-trainer", "metadata": {}, "source": [ "# 1. [Shor's Algorithm](https://raw.githubusercontent.com/qiskit-community/intro-to-quantum-computing-and-quantum-hardware/master/lectures/introqcqh-lecture-notes-4.pdf) " ] }, { "cell_type": "markdown", "id": "organizational-calcium", "metadata": {}, "source": [ "Shor’s algorithm is famous for factoring integers in polynomial time. " ] }, { "cell_type": "markdown", "id": "nearby-survivor", "metadata": {}, "source": [ "## The problem\n", "\n", "Facturing a number $N=pq$, where $p$,$q$ are prime and large numbers.\n", "* classically - $O (\\exp[c \\cdot n ^{\\frac{1}{3}} (\\log n )^{\\frac{2}{3}}])$, using the best known methods. \n", "* Shor's algorithm - is a little faster than $O (n^3)$.\n" ] }, { "cell_type": "markdown", "id": "desirable-winner", "metadata": {}, "source": [ "### Modular arithmetics\n", "\n", "$5 / 3 \\rightarrow quotient =1 ; remainder 2 $ \n", "\n", "$5 \\equiv 2 (\\mod 3)$\n", "\n", "Generally, $x \\equiv y (\\mod 3) \\Rightarrow x = 3k + y $ for some $k \\in Z$\n", "\n", "Notice the **periodicity** of modular arithmatic!\n", "\n", "$x \\equiv y (\\mod N)$ means $y \\in \\{0,..., N\\}$" ] }, { "cell_type": "markdown", "id": "gross-valentine", "metadata": {}, "source": [ "## Protocol \n", "\n", "$$N = pq$$\n", "\n", "1. pick a number \"a\" that is a coprime with $N$. ($\\equiv gcd(a,N)=1$)\n", "2. find the \"order\" $r$ of the function $a^r (\\mod N)$. ($\\equiv$ smallest $r$ such that $a^r \\equiv 1 (\\mod N$))\n", "3. if $r$ is even:\n", " $x\\equiv a^\\frac{r}{2} (\\mod N)$\n", " \n", " if $x+q \\ne 0 (\\mod N)$ then \n", " \n", " $\\{p,q\\} =\\{ \\gcd (x+1,N) ,\\gcd (x-1),N\\}$\n", " \n", " else: find another \"a\"" ] }, { "cell_type": "markdown", "id": "pharmaceutical-location", "metadata": {}, "source": [ "## [Implemenation](https://qiskit.org/textbook/ch-algorithms/shor.html) \n", "\n", "We will focus on the quantum part of Shor’s algorithm, which actually solves the problem of period finding. Since a factoring problem can be turned into a period finding problem in polynomial time, an efficient period finding algorithm can be used to factor integers efficiently too. For now its enough to show that if we can compute the period of $a^x \\mod N$ efficiently, then we can also efficiently factor.\n", "\n", "\n", "Shor’s solution was to use quantum phase estimation on the unitary operator:\n", "$$U|y\\rangle \\equiv |ay \\mod N \\rangle$$" ] }, { "cell_type": "markdown", "id": "elegant-david", "metadata": {}, "source": [ "Quantum circuit to factoring $15$.\n", "\n", "Let \"a\" be $13$. " ] }, { "cell_type": "code", "execution_count": 5, "id": "noticed-sydney", "metadata": {}, "outputs": [], "source": [ "a=13" ] }, { "cell_type": "code", "execution_count": 6, "id": "minor-kidney", "metadata": {}, "outputs": [], "source": [ "if a not in [2,7,8,11,13]:\n", " raise ValueError(\"'a' must be 2,7,8,11 or 13\")" ] }, { "cell_type": "code", "execution_count": 7, "id": "female-democrat", "metadata": {}, "outputs": [], "source": [ "n_count = 4" ] }, { "cell_type": "markdown", "id": "varied-uzbekistan", "metadata": {}, "source": [ "**Step 0** \n", "\n", "$15 =[1111]$ start two sets of 4 qubits\n", "\n", "$$|x\\rangle |w\\rangle = |0\\rangle ^{\\otimes 4}|0\\rangle ^{\\otimes 4} $$" ] }, { "cell_type": "code", "execution_count": 48, "id": "infectious-lithuania", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "pediatric-heritage", "metadata": {}, "outputs": [], "source": [ "qc.draw(output='mpl')" ] }, { "cell_type": "markdown", "id": "cathedral-folder", "metadata": {}, "source": [ "**Step 1**\n", "\n", "Perform Hadamards on the control bits.\n", "\n", "$$[H^{\\otimes 4} |0\\rangle ^{\\otimes 4}] |0\\rangle^{\\otimes 4}$$\n", "$$\\frac{1}{4} [|0\\rangle_4 + |1\\rangle_4 + |2\\rangle_4 + ... + |15\\rangle_4]|0\\rangle_4$$" ] }, { "cell_type": "code", "execution_count": 50, "id": "silent-intake", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "bored-polymer", "metadata": {}, "outputs": [], "source": [ "qc.draw(output='mpl')" ] }, { "cell_type": "markdown", "id": "continuous-cinema", "metadata": {}, "source": [ "**Step 2**\n", "\n", "Apply the Control $U_{f_{a,N}}$.\n", "\n", "$$|x\\rangle |w\\rangle \\rightarrow |x\\rangle |w \\oplus f_{a,N}(x)\\rangle \\mbox{ where } f_{a,N}(x) \\equiv a^x(\\mod N)$$\n", "\n", "$$\\frac{1}{4}[|0\\rangle_4 |0\\oplus 13^0 (\\mod 15)\\rangle_4+|1\\rangle_4 |0\\oplus 13^1 (\\mod 15)\\rangle_4 + ...]$$\n", "\n", "Since $0 \\oplus Z =Z$\n", "\n", "$$=\\frac{1}{4}[|0\\rangle_4|1\\rangle_4 +|1\\rangle_4 |13\\rangle_4+|2\\rangle_4|4\\rangle_4 +|3\\rangle_4 |7\\rangle_4$$\n", "$$ + |4\\rangle_4 |1\\rangle_4 + |5\\rangle_4 |13\\rangle_4 + |6\\rangle_4 |4\\rangle_4 +|7\\rangle_4 |7\\rangle_4 $$\n", "$$ + |8\\rangle_4 |1\\rangle_4 + |9\\rangle_4 |13\\rangle_4 +|10\\rangle_4 |4\\rangle_4 + |11\\rangle_4 |7\\rangle_4 $$\n", "$$ + |12\\rangle_4 |1\\rangle_4 + |13\\rangle_4 |13\\rangle_4 +|14\\rangle_4 |4\\rangle_4 +|15\\rangle_4 |7\\rangle_4 ]$$" ] }, { "cell_type": "markdown", "id": "otherwise-length", "metadata": {}, "source": [ "