{ "cells": [ { "cell_type": "markdown", "metadata": { "tags": [ "remove_cell" ] }, "source": [ "# Deutsch-Jozsa Algorithm" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In this section, we first introduce the Deutsch-Jozsa problem, and classical and quantum algorithms to solve it. We then implement the quantum algorithm using Qiskit, and run it on a simulator and device." ] }, { "cell_type": "markdown", "metadata": { "tags": [ "contents" ] }, "source": [ "## Contents\n", "\n", "1. [Introduction](#introduction) \n", " 1.1 [Deutsch-Jozsa Problem](#djproblem) \n", " 1.2 [Deutsch-Jozsa Algorithm](#classical-solution) \n", " 1.3 [The Quantum Solution](#quantum-solution) \n", " 1.4 [Why Does This Work?](#why-does-this-work) \n", "2. [Worked Example](#example)\n", "3. [Creating Quantum Oracles](#creating-quantum-oracles) \n", "4. [Qiskit Implementation](#implementation) \n", " 4.1 [Constant Oracle](#const_oracle) \n", " 4.2 [Balanced Oracle](#balanced_oracle) \n", " 4.3 [The Full Algorithm](#full_alg) \n", " 4.4 [Generalised Circuit](#general_circs) \n", "5. [Running on Real Devices](#device) \n", "6. [Problems](#problems)\n", "7. [References](#references)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. Introduction " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The Deutsch-Jozsa algorithm, first introduced in Reference , was the first example of a quantum algorithm that performs better than the best classical algorithm. It showed that there can be advantages to using a quantum computer as a computational tool for a specific problem." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.1 Deutsch-Jozsa Problem \n", "\n", "We are given a hidden Boolean function $f$, which takes as input a string of bits, and returns either $0$ or $1$, that is:\n", "\n", "$$\n", "f(\\{x_0,x_1,x_2,...\\}) \\rightarrow 0 \\textrm{ or } 1 \\textrm{ , where } x_n \\textrm{ is } 0 \\textrm{ or } 1$$\n", "\n", "The property of the given Boolean function is that it is guaranteed to either be balanced or constant. A constant function returns all $0$'s or all $1$'s for any input, while a balanced function returns $0$'s for exactly half of all inputs and $1$'s for the other half. Our task is to determine whether the given function is balanced or constant. \n", "\n", "Note that the Deutsch-Jozsa problem is an $n$-bit extension of the single bit Deutsch problem. \n", "\n", "### 1.2 The Classical Solution \n", "\n", "Classically, in the best case, two queries to the oracle can determine if the hidden Boolean function, $f(x)$, is balanced: \n", "e.g. if we get both $f(0,0,0,...)\\rightarrow 0$ and $f(1,0,0,...) \\rightarrow 1$, then we know the function is balanced as we have obtained the two different outputs. \n", "\n", "In the worst case, if we continue to see the same output for each input we try, we will have to check exactly half of all possible inputs plus one in order to be certain that $f(x)$ is constant. Since the total number of possible inputs is $2^n$, this implies that we need $2^{n-1}+1$ trial inputs to be certain that $f(x)$ is constant in the worst case. For example, for a $4$-bit string, if we checked $8$ out of the $16$ possible combinations, getting all $0$'s, it is still possible that the $9^\\textrm{th}$ input returns a $1$ and $f(x)$ is balanced. Probabilistically, this is a very unlikely event. In fact, if we get the same result continually in succession, we can express the probability that the function is constant as a function of $k$ inputs as:\n", "\n", "\n", "\n", "$$P_\\textrm{constant}(k) = 1 - \\frac{1}{2^{k-1}} \\qquad \\textrm{for } 1 < k \\leq 2^{n-1}$$\n", "\n", "\n", "\n", "Realistically, we could opt to truncate our classical algorithm early, say if we were over x% confident. But if we want to be 100% confident, we would need to check $2^{n-1}+1$ inputs." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1.3 Quantum Solution \n", "\n", "Using a quantum computer, we can solve this problem with 100% confidence after only one call to the function $f(x)$, provided we have the function $f$ implemented as a quantum oracle, which maps the state $\\vert x\\rangle \\vert y\\rangle$ to $\\vert x\\rangle \\vert y \\oplus f(x)\\rangle$, where $\\oplus$ is addition modulo $2$. Below is the generic circuit for the Deutsch-Jozsa algorithm.\n", "\n", "![image1](images/deutsch_steps.png)\n", "\n", "Now, let's go through the steps of the algorithm:\n", "\n", "
\n", "
1. \n", " Prepare two quantum registers. The first is an $n$-qubit register initialized to $|0\\rangle$, and the second is a one-qubit register initialized to $|1\\rangle$:\n", " \n", "\n", "$$\\vert \\psi_0 \\rangle = \\vert0\\rangle^{\\otimes n} \\vert 1\\rangle$$\n", "\n", "\n", "
2. \n", " \n", "
3. \n", " Apply a Hadamard gate to each qubit:\n", " \n", "\n", "$$\\vert \\psi_1 \\rangle = \\frac{1}{\\sqrt{2^{n+1}}}\\sum_{x=0}^{2^n-1} \\vert x\\rangle \\left(|0\\rangle - |1 \\rangle \\right)$$\n", "\n", "\n", "
4. \n", " \n", "
5. \n", " Apply the quantum oracle $\\vert x\\rangle \\vert y\\rangle$ to $\\vert x\\rangle \\vert y \\oplus f(x)\\rangle$:\n", " \n", " \\begin{aligned}\n", " \\lvert \\psi_2 \\rangle \n", " & = \\frac{1}{\\sqrt{2^{n+1}}}\\sum_{x=0}^{2^n-1} \\vert x\\rangle (\\vert f(x)\\rangle - \\vert 1 \\oplus f(x)\\rangle) \\\\ \n", " & = \\frac{1}{\\sqrt{2^{n+1}}}\\sum_{x=0}^{2^n-1}(-1)^{f(x)}|x\\rangle ( |0\\rangle - |1\\rangle ) \n", " \\end{aligned}\n", "\n", " \n", "since for each $x,f(x)$ is either $0$ or $1$.\n", "
6. \n", "\n", "
7. \n", " At this point the second single qubit register may be ignored. Apply a Hadamard gate to each qubit in the first register:\n", " \n", " \\begin{aligned}\n", " \\lvert \\psi_3 \\rangle \n", " & = \\frac{1}{2^n}\\sum_{x=0}^{2^n-1}(-1)^{f(x)}\n", " \\left[ \\sum_{y=0}^{2^n-1}(-1)^{x \\cdot y} \n", " \\vert y \\rangle \\right] \\\\\n", " & = \\frac{1}{2^n}\\sum_{y=0}^{2^n-1}\n", " \\left[ \\sum_{x=0}^{2^n-1}(-1)^{f(x)}(-1)^{x \\cdot y} \\right]\n", " \\vert y \\rangle\n", " \\end{aligned}\n", "\n", " \n", "where $x \\cdot y = x_0y_0 \\oplus x_1y_1 \\oplus \\ldots \\oplus x_{n-1}y_{n-1}$ is the sum of the bitwise product.\n", "
8. \n", "\n", "
9. \n", " Measure the first register. Notice that the probability of measuring $\\vert 0 \\rangle ^{\\otimes n} = \\lvert \\frac{1}{2^n}\\sum_{x=0}^{2^n-1}(-1)^{f(x)} \\rvert^2$, which evaluates to $1$ if $f(x)$ is constant and $0$ if $f(x)$ is balanced. \n", "
10. \n", "\n", "
\n", "\n", "### 1.4 Why Does This Work? \n", "\n", "- **Constant Oracle**\n", "\n", "When the oracle is *constant*, it has no effect (up to a global phase) on the input qubits, and the quantum states before and after querying the oracle are the same. Since the H-gate is its own inverse, in Step 4 we reverse Step 2 to obtain the initial quantum state of $|00\\dots 0\\rangle$ in the first register.\n", "\n", "$$\n", "H^{\\otimes n}\\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ \\vdots \\\\ 0 \\end{bmatrix} \n", "= \n", "\\tfrac{1}{\\sqrt{2^n}}\\begin{bmatrix} 1 \\\\ 1 \\\\ 1 \\\\ \\vdots \\\\ 1 \\end{bmatrix}\n", "\\quad \\xrightarrow{\\text{after } U_f} \\quad\n", "H^{\\otimes n}\\tfrac{1}{\\sqrt{2^n}}\\begin{bmatrix} 1 \\\\ 1 \\\\ 1 \\\\ \\vdots \\\\ 1 \\end{bmatrix}\n", "= \n", "\\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ \\vdots \\\\ 0 \\end{bmatrix} \n", "$$\n", "\n", "- **Balanced Oracle**\n", "\n", "After step 2, our input register is an equal superposition of all the states in the computational basis. When the oracle is *balanced*, phase kickback adds a negative phase to exactly half these states:\n", "\n", "$$\n", "U_f \\tfrac{1}{\\sqrt{2^n}}\\begin{bmatrix} 1 \\\\ 1 \\\\ 1 \\\\ \\vdots \\\\ 1 \\end{bmatrix} \n", "= \n", "\\tfrac{1}{\\sqrt{2^n}}\\begin{bmatrix} -1 \\\\ 1 \\\\ -1 \\\\ \\vdots \\\\ 1 \\end{bmatrix}\n", "$$\n", "\n", "\n", "The quantum state after querying the oracle is orthogonal to the quantum state before querying the oracle. Thus, in Step 4, when applying the H-gates, we must end up with a quantum state that is orthogonal to $|00\\dots 0\\rangle$. This means we should never measure the all-zero state. \n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Worked Example \n", "\n", "Let's go through a specific example for a two bit balanced function: \n", "\n", "Consider a two-bit function $f(x_0,x_1)=x_0 \\oplus x_1$ such that \n", "\n", "$f(0,0)=0$\n", "\n", "$f(0,1)=1$\n", "\n", "$f(1,0)=1$\n", "\n", "$f(1,1)=0$\n", "\n", "The corresponding phase oracle of this two-bit oracle is $U_f \\lvert x_1, x_0 \\rangle = (-1)^{f(x_1, x_0)}\\lvert x \\rangle$\n", "\n", "We will now check if this oracle works as expected by taking a example state\n", "$$\\lvert \\psi_0 \\rangle = \\lvert 0 0 \\rangle_{01} \\otimes \\lvert 1 \\rangle_{2}$$\n", "\n", "
\n", "
1. The first register of two qubits is initialized to $|00\\rangle$ and the second register qubit to $|1\\rangle$ \n", " \n", "(Note that we are using subscripts 0, 1, and 2 to index the qubits. A subscript of \"01\" indicates the state of the register containing qubits 0 and 1)\n", " \n", "\n", "$$\\lvert \\psi_0 \\rangle = \\lvert 0 0 \\rangle_{01} \\otimes \\lvert 1 \\rangle_{2}$$\n", "\n", " \n", "
2. \n", " \n", "
3. Apply Hadamard on all qubits\n", " \n", "\n", "$$\\lvert \\psi_1 \\rangle = \\frac{1}{2} \\left( \\lvert 0 0 \\rangle + \\lvert 0 1 \\rangle + \\lvert 1 0 \\rangle + \\lvert 1 1 \\rangle \\right)_{01} \\otimes \\frac{1}{\\sqrt{2}} \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right)_{2}$$\n", "\n", " \n", "
4. \n", " \n", "
5. The oracle function can be implemented as $\\text{Q}_f = CX_{02}CX_{12}$, \n", " \n", " \\begin{align*}\n", " \\lvert \\psi_2 \\rangle = \\frac{1}{2\\sqrt{2}} \\left[ \\lvert 0 0 \\rangle_{01} \\otimes \\left( \\lvert 0 \\oplus 0 \\oplus 0 \\rangle - \\lvert 1 \\oplus 0 \\oplus 0 \\rangle \\right)_{2} \\\\\n", " + \\lvert 0 1 \\rangle_{01} \\otimes \\left( \\lvert 0 \\oplus 0 \\oplus 1 \\rangle - \\lvert 1 \\oplus 0 \\oplus 1 \\rangle \\right)_{2} \\\\\n", " + \\lvert 1 0 \\rangle_{01} \\otimes \\left( \\lvert 0 \\oplus 1 \\oplus 0 \\rangle - \\lvert 1 \\oplus 1 \\oplus 0 \\rangle \\right)_{2} \\\\\n", " + \\lvert 1 1 \\rangle_{01} \\otimes \\left( \\lvert 0 \\oplus 1 \\oplus 1 \\rangle - \\lvert 1 \\oplus 1 \\oplus 1 \\rangle \\right)_{2} \\right]\n", " \\end{align*}\n", "\n", "
6. \n", " \n", "
7. Simplifying this, we get the following: \n", " \n", " \\begin{aligned}\n", " \\lvert \\psi_2 \\rangle & = \\frac{1}{2\\sqrt{2}} \\left[ \\lvert 0 0 \\rangle_{01} \\otimes \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right)_{2} - \\lvert 0 1 \\rangle_{01} \\otimes \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right)_{2} - \\lvert 1 0 \\rangle_{01} \\otimes \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right)_{2} + \\lvert 1 1 \\rangle_{01} \\otimes \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right)_{2} \\right] \\\\\n", " & = \\frac{1}{2} \\left( \\lvert 0 0 \\rangle - \\lvert 0 1 \\rangle - \\lvert 1 0 \\rangle + \\lvert 1 1 \\rangle \\right)_{01} \\otimes \\frac{1}{\\sqrt{2}} \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right)_{2} \\\\\n", " & = \\frac{1}{\\sqrt{2}} \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right)_{0} \\otimes \\frac{1}{\\sqrt{2}} \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right)_{1} \\otimes \\frac{1}{\\sqrt{2}} \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right)_{2}\n", " \\end{aligned}\n", "\n", "
8. \n", " \n", "
9. Apply Hadamard on the first register\n", " \n", "\n", "$$\\lvert \\psi_3\\rangle = \\lvert 1 \\rangle_{0} \\otimes \\lvert 1 \\rangle_{1} \\otimes \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right)_{2}$$\n", "\n", "\n", "
10. \n", " \n", "
11. Measuring the first two qubits will give the non-zero $11$, indicating a balanced function.\n", "
12. \n", "
\n", "\n", "You can try out similar examples using the widget below. Press the buttons to add H-gates and oracles, re-run the cell and/or set case=\"constant\" to try out different oracles." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "scrolled": true }, "outputs": [ { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "5dfbdfcbb1ea48f2af456f2013c30f09", "version_major": 2, "version_minor": 0 }, "text/plain": [ "HBox(children=(Button(description='H⊗ⁿ', style=ButtonStyle()), Button(description='Oracle', style=ButtonStyle(…" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "519642a2d931456b9dd2230e5103ae5a", "version_major": 2, "version_minor": 0 }, "text/plain": [ "HTMLMath(value='$$|00\\\\rangle = |00\\\\rangle$$')" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "0755c206fbbf47e39428ff0ca8dec5f4", "version_major": 2, "version_minor": 0 }, "text/plain": [ "Image(value=b'\\x89PNG\\r\\n\\x1a\\n\\x00\\x00\\x00\\rIHDR\\x00\\x00\\x00\\xce\\x00\\x00\\x00\\xcc\\x08\\x06\\x00\\x00\\x00;\\xd7\\x9c…" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "from qiskit_textbook.widgets import dj_widget\n", "dj_widget(size=\"small\", case=\"balanced\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. Creating Quantum Oracles \n", "\n", "Let's see some different ways we can create a quantum oracle. \n", "\n", "For a constant function, it is simple:\n", "\n", "$\\qquad$ 1. if f(x) = 0, then apply the $I$ gate to the qubit in register 2. \n", "$\\qquad$ 2. if f(x) = 1, then apply the $X$ gate to the qubit in register 2.\n", "\n", "For a balanced function, there are many different circuits we can create. One of the ways we can guarantee our circuit is balanced is by performing a CNOT for each qubit in register 1, with the qubit in register 2 as the target. For example:\n", "\n", "![image2](images/deutsch_balanced1.svg)\n", "\n", "In the image above, the top three qubits form the input register, and the bottom qubit is the output register. We can see which input states give which output in the table below:\n", "\n", "| Input states that output 0 | Input States that output 1 |\n", "|:--------------------------:|:--------------------------:|\n", "| 000 | 001 |\n", "| 011 | 100 |\n", "| 101 | 010 |\n", "| 110 | 111 |\n", "\n", "\n", "We can change the results while keeping them balanced by wrapping selected controls in X-gates. For example, see the circuit and its results table below:\n", "\n", "![other_balanced_circuit](images/deutsch_balanced2.svg)\n", "\n", "| Input states that output 0 | Input states that output 1 |\n", "|:--------------------------:|:--------------------------:|\n", "| 001 | 000 |\n", "| 010 | 011 |\n", "| 100 | 101 |\n", "| 111 | 110 |" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 4. Qiskit Implementation \n", "\n", "We now implement the Deutsch-Jozsa algorithm for the example of a three-bit function, with both constant and balanced oracles. First let's do our imports:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "tags": [ "thebelab-init" ] }, "outputs": [], "source": [ "# initialization\n", "import numpy as np\n", "\n", "# importing Qiskit\n", "from qiskit import IBMQ, Aer\n", "from qiskit.providers.ibmq import least_busy\n", "from qiskit import QuantumCircuit, assemble, transpile\n", "\n", "# import basic plot tools\n", "from qiskit.visualization import plot_histogram" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Next, we set the size of the input register for our oracle:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "# set the length of the n-bit input string. \n", "n = 3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 4.1 Constant Oracle \n", "Let's start by creating a constant oracle, in this case the input has no effect on the output so we just randomly set the output qubit to be 0 or 1:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "tags": [ "thebelab-init" ] }, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n" ], "text/plain": [ "