{ "cells": [ { "cell_type": "markdown", "metadata": { "tags": [ "remove_cell" ] }, "source": [ "# Simon's Algorithm" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In this section, we first introduce the Simon problem, and classical and quantum algorithms to solve it. We then implement the quantum algorithm using Qiskit, and run on a simulator and device.\n", "\n", "\n", "## Contents\n", "\n", "1. [Introduction](#introduction) \n", " 1.1 [Simon's Problem](#problem) \n", " 1.2 [Simon's Algorithm](#algorithm)\n", "2. [Example](#example)\n", "3. [Qiskit Implementation](#implementation) \n", " 3.1 [Simulation](#simulation) \n", " 3.2 [Device](#device) \n", "4. [Oracle](#oracle)\n", "5. [Problems](#problems)\n", "6. [References](#references)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. Introduction \n", "\n", "Simon's algorithm, first introduced in Reference , was the first quantum algorithm to show an exponential speed-up versus the best classical algorithm in solving a specific problem. This inspired the quantum algorithms based on the quantum Fourier transform, which is used in the most famous quantum algorithm: Shor's factoring algorithm.\n", "\n", "### 1a. Simon's Problem \n", "\n", "We are given an unknown blackbox function $f$, which is guaranteed to be either one-to-one ($1:1$) or two-to-one ($2:1$), where one-to-one and two-to-one functions have the following properties:\n", "\n", "- **one-to-one**: maps exactly one unique output for every input. An example with a function that takes 4 inputs is:\n", "\n", "$$f(1) \\rightarrow 1, \\quad f(2) \\rightarrow 2, \\quad f(3) \\rightarrow 3, \\quad f(4) \\rightarrow 4$$\n", "\n", "- **two-to-one**: maps exactly two inputs to every unique output. An example with a function that takes 4 inputs is:\n", "\n", "$$f(1) \\rightarrow 1, \\quad f(2) \\rightarrow 2, \\quad f(3) \\rightarrow 1, \\quad f(4) \\rightarrow 2$$\n", "\n", "This two-to-one mapping is according to a hidden bitstring, $b$, where:\n", "\n", "$$\n", "\\textrm{given }x_1,x_2: \\quad f(x_1) = f(x_2) \\\\\n", "\\textrm{it is guaranteed }: \\quad x_1 \\oplus x_2 = b\n", "$$\n", "\n", "Given this blackbox $f$, how quickly can we determine if $f$ is one-to-one or two-to-one? Then, if $f$ turns out to be two-to-one, how quickly can we determine $b$? As it turns out, both cases boil down to the same problem of finding $b$, where a bitstring of $b={000...}$ represents the one-to-one $f$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1b. Simon's Algorithm \n", "\n", "#### Classical Solution\n", "\n", "Classically, if we want to know what $b$ is with 100% certainty for a given $f$, we have to check up to $2^{n−1}+1$ inputs, where n is the number of bits in the input. This means checking just over half of all the possible inputs until we find two cases of the same output. Much like the Deutsch-Jozsa problem, if we get lucky, we could solve the problem with our first two tries. But if we happen to get an $f$ that is one-to-one, or get _really_ unlucky with an $f$ that’s two-to-one, then we’re stuck with the full $2^{n−1}+1$.\n", "There are known algorithms that have a lower bound of $\\Omega(2^{n/2})$ (see Reference 2 below), but generally speaking the complexity grows exponentially with n." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Quantum Solution\n", "\n", "The quantum circuit that implements Simon's algorithm is shown below.\n", "\n", "![image1](images/simon_steps.jpeg)\n", "\n", "Where the query function, $\\text{Q}_f$ acts on two quantum registers as:\n", "\n", "\n", "$$\\lvert x \\rangle \\lvert a \\rangle \\rightarrow \\lvert x \\rangle \\lvert a \\oplus f(x) \\rangle$$\n", "\n", "In the specific case that the second register is in the state $|0\\rangle = |00\\dots0\\rangle$ we have:\n", "\n", "$$\\lvert x \\rangle \\lvert 0 \\rangle \\rightarrow \\lvert x \\rangle \\lvert f(x) \\rangle$$\n", "\n", "The algorithm involves the following steps.\n", "
\n", "
1. Two $n$-qubit input registers are initialized to the zero state: \n", " \n", "\n", "$$\\lvert \\psi_1 \\rangle = \\lvert 0 \\rangle^{\\otimes n} \\lvert 0 \\rangle^{\\otimes n}$$\n", "\n", "
2. \n", " \n", "
3. Apply a Hadamard transform to the first register:\n", " \n", "\n", "$$\\lvert \\psi_2 \\rangle = \\frac{1}{\\sqrt{2^n}} \\sum_{x \\in \\{0,1\\}^{n} } \\lvert x \\rangle\\lvert 0 \\rangle^{\\otimes n}$$\n", "\n", " \n", "
4. \n", " \n", "
5. Apply the query function $\\text{Q}_f$: \n", " \n", "\n", "$$\\lvert \\psi_3 \\rangle = \\frac{1}{\\sqrt{2^n}} \\sum_{x \\in \\{0,1\\}^{n} } \\lvert x \\rangle \\lvert f(x) \\rangle$$\n", "\n", " \n", "
6. \n", " \n", "
7. Measure the second register. A certain value of $f(x)$ will be observed. Because of the setting of the problem, the observed value $f(x)$ could correspond to two possible inputs: $x$ and $y = x \\oplus b$. Therefore the first register becomes:\n", " \n", "\n", "$$\\lvert \\psi_4 \\rangle = \\frac{1}{\\sqrt{2}} \\left( \\lvert x \\rangle + \\lvert y \\rangle \\right)$$\n", "\n", "\n", " where we omitted the second register since it has been measured. \n", "
8. \n", " \n", "
9. Apply Hadamard on the first register:\n", " \n", "\n", "$$\\lvert \\psi_5 \\rangle = \\frac{1}{\\sqrt{2^{n+1}}} \\sum_{z \\in \\{0,1\\}^{n} } \\left[ (-1)^{x \\cdot z} + (-1)^{y \\cdot z} \\right] \\lvert z \\rangle$$\n", "\n", "\n", "
10. \n", " \n", "
11. Measuring the first register will give an output only if:\n", " \n", "\n", "$$(-1)^{x \\cdot z} = (-1)^{y \\cdot z}$$\n", "\n", "\n", " which means:\n", " $$x \\cdot z = y \\cdot z \\\\\n", " x \\cdot z = \\left( x \\oplus b \\right) \\cdot z \\\\\n", " x \\cdot z = x \\cdot z \\oplus b \\cdot z \\\\\n", " b \\cdot z = 0 \\text{ (mod 2)}$$\n", " \n", " A string $z$ will be measured, whose inner product with $b = 0$. Thus, repeating the algorithm $\\approx n$ times, we will be able to obtain $n$ different values of $z$ and the following system of equation can be written:\n", " \n", " \n", "\n", "$$\\begin{cases} b \\cdot z_1 = 0 \\\\ b \\cdot z_2 = 0 \\\\ \\quad \\vdots \\\\ b \\cdot z_n = 0 \\end{cases}$$\n", "\n", "\n", " \n", " From which $b$ can be determined, for example by Gaussian elimination.\n", "
12. \n", "
\n", "\n", "So, in this particular problem the quantum algorithm performs exponentially fewer steps than the classical one. Once again, it might be difficult to envision an application of this algorithm (although it inspired the most famous algorithm created by Shor) but it represents the first proof that there can be an exponential speed-up in solving a specific problem by using a quantum computer rather than a classical one." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Example \n", "\n", "Let's see the example of Simon's algorithm for 2 qubits with the secret string $b=11$, so that $f(x) = f(y)$ if $y = x \\oplus b$. The quantum circuit to solve the problem is:\n", "\n", "![image2](images/simon_example.jpeg)\n", "\n", "
\n", "
1. Two $2$-qubit input registers are initialized to the zero state:\n", " \n", "\n", "$$\\lvert \\psi_1 \\rangle = \\lvert 0 0 \\rangle_1 \\lvert 0 0 \\rangle_2$$\n", "\n", "
2. \n", " \n", "
3. Apply Hadamard gates to the qubits in the first register:\n", " \n", "\n", "$$\\lvert \\psi_2 \\rangle = \\frac{1}{2} \\left( \\lvert 0 0 \\rangle_1 + \\lvert 0 1 \\rangle_1 + \\lvert 1 0 \\rangle_1 + \\lvert 1 1 \\rangle_1 \\right) \\lvert 0 0 \\rangle_2$$\n", "\n", "
4. \n", " \n", "
5. For the string $b=11$, the query function can be implemented as $\\text{Q}_f = CX_{1_a 2_a}CX_{1_a 2_b}CX_{1_b 2_a}CX_{1_b 2_b}$ (as seen in the circuit diagram above):\n", " \n", "\n", "\\begin{aligned}\n", "\\lvert \\psi_3 \\rangle = \\frac{1}{2} ( \\; \n", " & \\lvert 0 0 \\rangle_1 \\; \\lvert 0\\oplus 0 \\oplus 0, & 0 \\oplus 0 \\oplus 0 \\rangle_2 &\\\\[5pt]\n", "+ & \\lvert 0 1 \\rangle_1 \\; \\lvert 0\\oplus 0 \\oplus 1, & 0 \\oplus 0 \\oplus 1 \\rangle_2 &\\\\[6pt]\n", "+ & \\lvert 1 0 \\rangle_1 \\; \\lvert 0\\oplus 1 \\oplus 0, & 0 \\oplus 1 \\oplus 0 \\rangle_2 &\\\\[6pt]\n", "+ & \\lvert 1 1 \\rangle_1 \\; \\lvert 0\\oplus 1 \\oplus 1, & 0 \\oplus 1 \\oplus 1 \\rangle_2 & \\; )\\\\\n", "\\end{aligned}\n", "\n", " \n", "Thus: \n", "\n", "\n", "\\begin{aligned} \n", "\\lvert \\psi_3 \\rangle = \\frac{1}{2} ( \\quad\n", "& \\lvert 0 0 \\rangle_1 \\lvert 0 0 \\rangle_2 & \\\\[6pt]\n", "+ & \\lvert 0 1 \\rangle_1 \\lvert 1 1 \\rangle_2 & \\\\[6pt]\n", "+ & \\lvert 1 0 \\rangle_1 \\lvert 1 1 \\rangle_2 & \\\\[6pt]\n", "+ & \\lvert 1 1 \\rangle_1 \\lvert 0 0 \\rangle_2 & \\; )\\\\\n", "\\end{aligned}\n", " \n", "
6. \n", " \n", "
7. We measure the second register. With $50\\%$ probability we will see either $\\lvert 0 0 \\rangle_2$ or $\\lvert 1 1 \\rangle_2$. For the sake of the example, let us assume that we see $\\lvert 1 1 \\rangle_2$. The state of the system is then\n", " \n", "\n", "$$\\lvert \\psi_4 \\rangle = \\frac{1}{\\sqrt{2}} \\left( \\lvert 0 1 \\rangle_1 + \\lvert 1 0 \\rangle_1 \\right)$$\n", "\n", "\n", " \n", " where we omitted the second register since it has been measured.\n", " \n", "
8. \n", " \n", " \n", " \n", "
9. Apply Hadamard on the first register\n", " $$\\lvert \\psi_5 \\rangle = \\frac{1}{2\\sqrt{2}} \\left[ \\left( \\lvert 0 \\rangle + \\lvert 1 \\rangle \\right) \\otimes \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right) + \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right) \\otimes \\left( \\lvert 0 \\rangle + \\lvert 1 \\rangle \\right) \\right] \\\\\n", " = \\frac{1}{2\\sqrt{2}} \\left[ \\lvert 0 0 \\rangle - \\lvert 0 1 \\rangle + \\lvert 1 0 \\rangle - \\lvert 1 1 \\rangle + \\lvert 0 0 \\rangle + \\lvert 0 1 \\rangle - \\lvert 1 0 \\rangle - \\lvert 1 1 \\rangle \\right] \\\\\n", " = \\frac{1}{\\sqrt{2}} \\left( \\lvert 0 0 \\rangle - \\lvert 1 1 \\rangle \\right)$$\n", " \n", "
10. \n", " \n", "
11. Measuring the first register will give either $\\lvert 0 0 \\rangle$ or $\\lvert 1 1 \\rangle$ with equal probability. \n", "
12. \n", "
13. \n", " If we see $\\lvert 1 1 \\rangle$, then: \n", " \n", "\n", "$$b \\cdot 11 = 0$$\n", "\n", "which tells us that $b \\neq 01$ or $10$, and the two remaining potential solutions are $b = 00$ or $b = 11$. Note that $b = 00$ will always be a trivial solution to our simultaneous equations. If we repeat steps 1-6 many times, we would only measure $|00\\rangle$ or $|11\\rangle$ as\n", "\n", "$$b \\cdot 11 = 0$$\n", "$$b \\cdot 00 = 0$$\n", " \n", "are the only equations that satisfy $b=11$. We can verify $b=11$ by picking a random input ($x_i$) and checking $f(x_i) = f(x_i \\oplus b)$. For example:\n", "\n", "$$01 \\oplus b = 10$$\n", "$$f(01) = f(10) = 11$$\n", "\n", "
14. \n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. Qiskit Implementation \n", "\n", "We now implement Simon's algorithm for an example with $3$-qubits and $b=110$." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "tags": [ "thebelab-init" ] }, "outputs": [], "source": [ "# importing Qiskit\n", "from qiskit import IBMQ, Aer\n", "from qiskit.providers.ibmq import least_busy\n", "from qiskit import QuantumCircuit, transpile, assemble\n", "\n", "# import basic plot tools\n", "from qiskit.visualization import plot_histogram\n", "from qiskit_textbook.tools import simon_oracle" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The function simon_oracle (imported above) creates a Simon oracle for the bitstring b. This is given without explanation, but we will discuss the method in [section 4](#oracle).\n", "\n", "In Qiskit, measurements are only allowed at the end of the quantum circuit. In the case of Simon's algorithm, we actually do not care about the output of the second register, and will only measure the first register." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n" ], "text/plain": [ "