"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ax.set(xlabel='Number of applications of U', ylabel='End state of register',\n",
" title=\"Effect of Successive Applications of U\")\n",
"fig"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So a superposition of the states in this cycle ($|u_0\\rangle$) would be an eigenstate of $U$:\n",
"\n",
"$$|u_0\\rangle = \\tfrac{1}{\\sqrt{r}}\\sum_{k=0}^{r-1}{|a^k \\bmod N\\rangle} $$\n",
"\n",
"\n",
"\n",
" Click to Expand: Example with $a = 3$ and $N=35$ \n",
"\n",
"$$\\begin{aligned}\n",
"|u_0\\rangle &= \\tfrac{1}{\\sqrt{12}}(|1\\rangle + |3\\rangle + |9\\rangle \\dots + |4\\rangle + |12\\rangle) \\\\[10pt]\n",
"U|u_0\\rangle &= \\tfrac{1}{\\sqrt{12}}(U|1\\rangle + U|3\\rangle + U|9\\rangle \\dots + U|4\\rangle + U|12\\rangle) \\\\[10pt]\n",
" &= \\tfrac{1}{\\sqrt{12}}(|3\\rangle + |9\\rangle + |27\\rangle \\dots + |12\\rangle + |1\\rangle) \\\\[10pt]\n",
" &= |u_0\\rangle\n",
"\\end{aligned}$$\n",
" \n",
"\n",
"\n",
"This eigenstate has an eigenvalue of 1, which isn’t very interesting. A more interesting eigenstate could be one in which the phase is different for each of these computational basis states. Specifically, let’s look at the case in which the phase of the $k$th state is proportional to $k$:\n",
"\n",
"$$\\begin{aligned}\n",
"|u_1\\rangle &= \\tfrac{1}{\\sqrt{r}}\\sum_{k=0}^{r-1}{e^{-\\tfrac{2\\pi i k}{r}}|a^k \\bmod N\\rangle}\\\\[10pt]\n",
"U|u_1\\rangle &= e^{\\tfrac{2\\pi i}{r}}|u_1\\rangle \n",
"\\end{aligned}\n",
"$$\n",
"\n",
"\n",
" Click to Expand: Example with $a = 3$ and $N=35$ \n",
"\n",
"$$\\begin{aligned}\n",
"|u_1\\rangle &= \\tfrac{1}{\\sqrt{12}}(|1\\rangle + e^{-\\tfrac{2\\pi i}{12}}|3\\rangle + e^{-\\tfrac{4\\pi i}{12}}|9\\rangle \\dots + e^{-\\tfrac{20\\pi i}{12}}|4\\rangle + e^{-\\tfrac{22\\pi i}{12}}|12\\rangle) \\\\[10pt]\n",
"U|u_1\\rangle &= \\tfrac{1}{\\sqrt{12}}(|3\\rangle + e^{-\\tfrac{2\\pi i}{12}}|9\\rangle + e^{-\\tfrac{4\\pi i}{12}}|27\\rangle \\dots + e^{-\\tfrac{20\\pi i}{12}}|12\\rangle + e^{-\\tfrac{22\\pi i}{12}}|1\\rangle) \\\\[10pt]\n",
"U|u_1\\rangle &= e^{\\tfrac{2\\pi i}{12}}\\cdot\\tfrac{1}{\\sqrt{12}}(e^{\\tfrac{-2\\pi i}{12}}|3\\rangle + e^{-\\tfrac{4\\pi i}{12}}|9\\rangle + e^{-\\tfrac{6\\pi i}{12}}|27\\rangle \\dots + e^{-\\tfrac{22\\pi i}{12}}|12\\rangle + e^{-\\tfrac{24\\pi i}{12}}|1\\rangle) \\\\[10pt]\n",
"U|u_1\\rangle &= e^{\\tfrac{2\\pi i}{12}}|u_1\\rangle\n",
"\\end{aligned}$$\n",
"\n",
"(We can see $r = 12$ appears in the denominator of the phase.)\n",
" \n",
"\n",
"This is a particularly interesting eigenvalue as it contains $r$. In fact, $r$ has to be included to make sure the phase differences between the $r$ computational basis states are equal. This is not the only eigenstate with this behaviour; to generalise this further, we can multiply an integer, $s$, to this phase difference, which will show up in our eigenvalue:\n",
"\n",
"$$\\begin{aligned}\n",
"|u_s\\rangle &= \\tfrac{1}{\\sqrt{r}}\\sum_{k=0}^{r-1}{e^{-\\tfrac{2\\pi i s k}{r}}|a^k \\bmod N\\rangle}\\\\[10pt]\n",
"U|u_s\\rangle &= e^{\\tfrac{2\\pi i s}{r}}|u_s\\rangle \n",
"\\end{aligned}\n",
"$$\n",
"\n",
"\n",
" Click to Expand: Example with $a = 3$ and $N=35$ \n",
"\n",
"$$\\begin{aligned}\n",
"|u_s\\rangle &= \\tfrac{1}{\\sqrt{12}}(|1\\rangle + e^{-\\tfrac{2\\pi i s}{12}}|3\\rangle + e^{-\\tfrac{4\\pi i s}{12}}|9\\rangle \\dots + e^{-\\tfrac{20\\pi i s}{12}}|4\\rangle + e^{-\\tfrac{22\\pi i s}{12}}|12\\rangle) \\\\[10pt]\n",
"U|u_s\\rangle &= \\tfrac{1}{\\sqrt{12}}(|3\\rangle + e^{-\\tfrac{2\\pi i s}{12}}|9\\rangle + e^{-\\tfrac{4\\pi i s}{12}}|27\\rangle \\dots + e^{-\\tfrac{20\\pi i s}{12}}|12\\rangle + e^{-\\tfrac{22\\pi i s}{12}}|1\\rangle) \\\\[10pt]\n",
"U|u_s\\rangle &= e^{\\tfrac{2\\pi i s}{12}}\\cdot\\tfrac{1}{\\sqrt{12}}(e^{-\\tfrac{2\\pi i s}{12}}|3\\rangle + e^{-\\tfrac{4\\pi i s}{12}}|9\\rangle + e^{-\\tfrac{6\\pi i s}{12}}|27\\rangle \\dots + e^{-\\tfrac{22\\pi i s}{12}}|12\\rangle + e^{-\\tfrac{24\\pi i s}{12}}|1\\rangle) \\\\[10pt]\n",
"U|u_s\\rangle &= e^{\\tfrac{2\\pi i s}{12}}|u_s\\rangle\n",
"\\end{aligned}$$\n",
"\n",
" \n",
"\n",
"We now have a unique eigenstate for each integer value of $s$ where $$0 \\leq s \\leq r-1$$. Very conveniently, if we sum up all these eigenstates, the different phases cancel out all computational basis states except $|1\\rangle$:\n",
"\n",
"$$ \\tfrac{1}{\\sqrt{r}}\\sum_{s=0}^{r-1} |u_s\\rangle = |1\\rangle$$\n",
"\n",
"\n",
" Click to Expand: Example with $a = 7$ and $N=15$ \n",
"\n",
"For this, we will look at a smaller example where $a = 7$ and $N=15$. In this case $r=4$:\n",
"\n",
"$$\\begin{aligned}\n",
"\\tfrac{1}{2}(\\quad|u_0\\rangle &= \\tfrac{1}{2}(|1\\rangle \\hphantom{e^{-\\tfrac{2\\pi i}{12}}}+ |7\\rangle \\hphantom{e^{-\\tfrac{12\\pi i}{12}}} + |4\\rangle \\hphantom{e^{-\\tfrac{12\\pi i}{12}}} + |13\\rangle)\\dots \\\\[10pt]\n",
"+ |u_1\\rangle &= \\tfrac{1}{2}(|1\\rangle + e^{-\\tfrac{2\\pi i}{4}}|7\\rangle + e^{-\\tfrac{\\hphantom{1}4\\pi i}{4}}|4\\rangle + e^{-\\tfrac{\\hphantom{1}6\\pi i}{4}}|13\\rangle)\\dots \\\\[10pt]\n",
"+ |u_2\\rangle &= \\tfrac{1}{2}(|1\\rangle + e^{-\\tfrac{4\\pi i}{4}}|7\\rangle + e^{-\\tfrac{\\hphantom{1}8\\pi i}{4}}|4\\rangle + e^{-\\tfrac{12\\pi i}{4}}|13\\rangle)\\dots \\\\[10pt]\n",
"+ |u_3\\rangle &= \\tfrac{1}{2}(|1\\rangle + e^{-\\tfrac{6\\pi i}{4}}|7\\rangle + e^{-\\tfrac{12\\pi i}{4}}|4\\rangle + e^{-\\tfrac{18\\pi i}{4}}|13\\rangle)\\quad) = |1\\rangle \\\\[10pt]\n",
"\\end{aligned}$$\n",
"\n",
" \n",
"\n",
"Since the computational basis state $|1\\rangle$ is a superposition of these eigenstates, which means if we do QPE on $U$ using the state $|1\\rangle$, we will measure a phase:\n",
"\n",
"$$\\phi = \\frac{s}{r}$$\n",
"\n",
"Where $s$ is a random integer between $0$ and $r-1$. We finally use the [continued fractions](https://en.wikipedia.org/wiki/Continued_fraction) algorithm on $\\phi$ to find $r$. The circuit diagram looks like this (note that this diagram uses Qiskit's qubit ordering convention):\n",
"\n",
" \n",
"\n",
"We will next demonstrate Shor’s algorithm using Qiskit’s simulators. For this demonstration we will provide the circuits for $U$ without explanation, but in section 4 we will discuss how circuits for $U^{2^j}$ can be constructed efficiently."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3. Qiskit Implementation\n",
"\n",
"In this example we will solve the period finding problem for $a=7$ and $N=15$. We provide the circuits for $U$ where:\n",
"\n",
"$$U|y\\rangle = |ay\\bmod 15\\rangle $$\n",
"\n",
"without explanation. To create $U^x$, we will simply repeat the circuit $x$ times. In the next section we will discuss a general method for creating these circuits efficiently. The function `c_amod15` returns the controlled-U gate for `a`, repeated `power` times."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"tags": [
"thebelab-init"
]
},
"outputs": [],
"source": [
"def c_amod15(a, power):\n",
" \"\"\"Controlled multiplication by a mod 15\"\"\"\n",
" if a not in [2,7,8,11,13]:\n",
" raise ValueError(\"'a' must be 2,7,8,11 or 13\")\n",
" U = QuantumCircuit(4) \n",
" for iteration in range(power):\n",
" if a in [2,13]:\n",
" U.swap(0,1)\n",
" U.swap(1,2)\n",
" U.swap(2,3)\n",
" if a in [7,8]:\n",
" U.swap(2,3)\n",
" U.swap(1,2)\n",
" U.swap(0,1)\n",
" if a == 11:\n",
" U.swap(1,3)\n",
" U.swap(0,2)\n",
" if a in [7,11,13]:\n",
" for q in range(4):\n",
" U.x(q)\n",
" U = U.to_gate()\n",
" U.name = \"%i^%i mod 15\" % (a, power)\n",
" c_U = U.control()\n",
" return c_U"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We will use 8 counting qubits:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"tags": [
"thebelab-init"
]
},
"outputs": [],
"source": [
"# Specify variables\n",
"n_count = 8 # number of counting qubits\n",
"a = 7"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We also provide the circuit for the inverse QFT (you can read more about the QFT in the [quantum Fourier transform chapter](./quantum-fourier-transform.html#generalqft)):"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"tags": [
"thebelab-init"
]
},
"outputs": [],
"source": [
"def qft_dagger(n):\n",
" \"\"\"n-qubit QFTdagger the first n qubits in circ\"\"\"\n",
" qc = QuantumCircuit(n)\n",
" # Don't forget the Swaps!\n",
" for qubit in range(n//2):\n",
" qc.swap(qubit, n-qubit-1)\n",
" for j in range(n):\n",
" for m in range(j):\n",
" qc.cu1(-np.pi/float(2**(j-m)), m, j)\n",
" qc.h(j)\n",
" qc.name = \"QFT†\"\n",
" return qc"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"With these building blocks we can easily construct the circuit for Shor's algorithm:"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"scrolled": false
},
"outputs": [
{
"data": {
"text/html": [
" ┌───┐ »\n",
" q_0: ┤ H ├───────■────────────────────────────────────────────────────»\n",
" ├───┤ │ »\n",
" q_1: ┤ H ├───────┼──────────────■─────────────────────────────────────»\n",
" ├───┤ │ │ »\n",
" q_2: ┤ H ├───────┼──────────────┼──────────────■──────────────────────»\n",
" ├───┤ │ │ │ »\n",
" q_3: ┤ H ├───────┼──────────────┼──────────────┼──────────────■───────»\n",
" ├───┤ │ │ │ │ »\n",
" q_4: ┤ H ├───────┼──────────────┼──────────────┼──────────────┼───────»\n",
" ├───┤ │ │ │ │ »\n",
" q_5: ┤ H ├───────┼──────────────┼──────────────┼──────────────┼───────»\n",
" ├───┤ │ │ │ │ »\n",
" q_6: ┤ H ├───────┼──────────────┼──────────────┼──────────────┼───────»\n",
" ├───┤ │ │ │ │ »\n",
" q_7: ┤ H ├───────┼──────────────┼──────────────┼──────────────┼───────»\n",
" └───┘┌─────┴┼──────┐┌─────┴┼──────┐┌─────┴┼──────┐┌─────┴┼──────┐»\n",
" q_8: ─────┤0 │ ├┤0 │ ├┤0 │ ├┤0 │ ├»\n",
" │ ││ ││ ││ │»\n",
" q_9: ─────┤1 ├┤1 ├┤1 ├┤1 ├»\n",
" │ 7^1 mod 15 ││ 7^2 mod 15 ││ 7^4 mod 15 ││ 7^8 mod 15 │»\n",
"q_10: ─────┤2 ├┤2 ├┤2 ├┤2 ├»\n",
" ┌───┐│ ││ ││ ││ │»\n",
"q_11: ┤ X ├┤3 ├┤3 ├┤3 ├┤3 ├»\n",
" └───┘└─────────────┘└─────────────┘└─────────────┘└─────────────┘»\n",
" c_0: ═════════════════════════════════════════════════════════════════»\n",
" »\n",
" c_1: ═════════════════════════════════════════════════════════════════»\n",
" »\n",
" c_2: ═════════════════════════════════════════════════════════════════»\n",
" »\n",
" c_3: ═════════════════════════════════════════════════════════════════»\n",
" »\n",
" c_4: ═════════════════════════════════════════════════════════════════»\n",
" »\n",
" c_5: ═════════════════════════════════════════════════════════════════»\n",
" »\n",
" c_6: ═════════════════════════════════════════════════════════════════»\n",
" »\n",
" c_7: ═════════════════════════════════════════════════════════════════»\n",
" »\n",
"« »\n",
"« q_0: ─────────────────────────────────────────────────────────────────»\n",
"« »\n",
"« q_1: ─────────────────────────────────────────────────────────────────»\n",
"« »\n",
"« q_2: ─────────────────────────────────────────────────────────────────»\n",
"« »\n",
"« q_3: ─────────────────────────────────────────────────────────────────»\n",
"« »\n",
"« q_4: ───────■─────────────────────────────────────────────────────────»\n",
"« │ »\n",
"« q_5: ───────┼───────────────■─────────────────────────────────────────»\n",
"« │ │ »\n",
"« q_6: ───────┼───────────────┼───────────────■─────────────────────────»\n",
"« │ │ │ »\n",
"« q_7: ───────┼───────────────┼───────────────┼────────────────■────────»\n",
"« ┌──────┴───────┐┌──────┴───────┐┌──────┴───────┐┌──────┴┼───────┐»\n",
"« q_8: ┤0 ├┤0 ├┤0 ├┤0 │ ├»\n",
"« │ ││ ││ ││ │»\n",
"« q_9: ┤1 ├┤1 ├┤1 ├┤1 ├»\n",
"« │ 7^16 mod 15 ││ 7^32 mod 15 ││ 7^64 mod 15 ││ 7^128 mod 15 │»\n",
"«q_10: ┤2 ├┤2 ├┤2 ├┤2 ├»\n",
"« │ ││ ││ ││ │»\n",
"«q_11: ┤3 ├┤3 ├┤3 ├┤3 ├»\n",
"« └──────────────┘└──────────────┘└──────────────┘└───────────────┘»\n",
"« c_0: ═════════════════════════════════════════════════════════════════»\n",
"« »\n",
"« c_1: ═════════════════════════════════════════════════════════════════»\n",
"« »\n",
"« c_2: ═════════════════════════════════════════════════════════════════»\n",
"« »\n",
"« c_3: ═════════════════════════════════════════════════════════════════»\n",
"« »\n",
"« c_4: ═════════════════════════════════════════════════════════════════»\n",
"« »\n",
"« c_5: ═════════════════════════════════════════════════════════════════»\n",
"« »\n",
"« c_6: ═════════════════════════════════════════════════════════════════»\n",
"« »\n",
"« c_7: ═════════════════════════════════════════════════════════════════»\n",
"« »\n",
"« ┌───────┐┌─┐ \n",
"« q_0: ┤0 ├┤M├─────────────────────\n",
"« │ │└╥┘┌─┐ \n",
"« q_1: ┤1 ├─╫─┤M├──────────────────\n",
"« │ │ ║ └╥┘┌─┐ \n",
"« q_2: ┤2 ├─╫──╫─┤M├───────────────\n",
"« │ │ ║ ║ └╥┘┌─┐ \n",
"« q_3: ┤3 ├─╫──╫──╫─┤M├────────────\n",
"« │ QFT† │ ║ ║ ║ └╥┘┌─┐ \n",
"« q_4: ┤4 ├─╫──╫──╫──╫─┤M├─────────\n",
"« │ │ ║ ║ ║ ║ └╥┘┌─┐ \n",
"« q_5: ┤5 ├─╫──╫──╫──╫──╫─┤M├──────\n",
"« │ │ ║ ║ ║ ║ ║ └╥┘┌─┐ \n",
"« q_6: ┤6 ├─╫──╫──╫──╫──╫──╫─┤M├───\n",
"« │ │ ║ ║ ║ ║ ║ ║ └╥┘┌─┐\n",
"« q_7: ┤7 ├─╫──╫──╫──╫──╫──╫──╫─┤M├\n",
"« └───────┘ ║ ║ ║ ║ ║ ║ ║ └╥┘\n",
"« q_8: ──────────╫──╫──╫──╫──╫──╫──╫──╫─\n",
"« ║ ║ ║ ║ ║ ║ ║ ║ \n",
"« q_9: ──────────╫──╫──╫──╫──╫──╫──╫──╫─\n",
"« ║ ║ ║ ║ ║ ║ ║ ║ \n",
"«q_10: ──────────╫──╫──╫──╫──╫──╫──╫──╫─\n",
"« ║ ║ ║ ║ ║ ║ ║ ║ \n",
"«q_11: ──────────╫──╫──╫──╫──╫──╫──╫──╫─\n",
"« ║ ║ ║ ║ ║ ║ ║ ║ \n",
"« c_0: ══════════╩══╬══╬══╬══╬══╬══╬══╬═\n",
"« ║ ║ ║ ║ ║ ║ ║ \n",
"« c_1: ═════════════╩══╬══╬══╬══╬══╬══╬═\n",
"« ║ ║ ║ ║ ║ ║ \n",
"« c_2: ════════════════╩══╬══╬══╬══╬══╬═\n",
"« ║ ║ ║ ║ ║ \n",
"« c_3: ═══════════════════╩══╬══╬══╬══╬═\n",
"« ║ ║ ║ ║ \n",
"« c_4: ══════════════════════╩══╬══╬══╬═\n",
"« ║ ║ ║ \n",
"« c_5: ═════════════════════════╩══╬══╬═\n",
"« ║ ║ \n",
"« c_6: ════════════════════════════╩══╬═\n",
"« ║ \n",
"« c_7: ═══════════════════════════════╩═\n",
"« "
],
"text/plain": [
" ┌───┐ »\n",
" q_0: ┤ H ├───────■────────────────────────────────────────────────────»\n",
" ├───┤ │ »\n",
" q_1: ┤ H ├───────┼──────────────■─────────────────────────────────────»\n",
" ├───┤ │ │ »\n",
" q_2: ┤ H ├───────┼──────────────┼──────────────■──────────────────────»\n",
" ├───┤ │ │ │ »\n",
" q_3: ┤ H ├───────┼──────────────┼──────────────┼──────────────■───────»\n",
" ├───┤ │ │ │ │ »\n",
" q_4: ┤ H ├───────┼──────────────┼──────────────┼──────────────┼───────»\n",
" ├───┤ │ │ │ │ »\n",
" q_5: ┤ H ├───────┼──────────────┼──────────────┼──────────────┼───────»\n",
" ├───┤ │ │ │ │ »\n",
" q_6: ┤ H ├───────┼──────────────┼──────────────┼──────────────┼───────»\n",
" ├───┤ │ │ │ │ »\n",
" q_7: ┤ H ├───────┼──────────────┼──────────────┼──────────────┼───────»\n",
" └───┘┌─────┴┼──────┐┌─────┴┼──────┐┌─────┴┼──────┐┌─────┴┼──────┐»\n",
" q_8: ─────┤0 │ ├┤0 │ ├┤0 │ ├┤0 │ ├»\n",
" │ ││ ││ ││ │»\n",
" q_9: ─────┤1 ├┤1 ├┤1 ├┤1 ├»\n",
" │ 7^1 mod 15 ││ 7^2 mod 15 ││ 7^4 mod 15 ││ 7^8 mod 15 │»\n",
"q_10: ─────┤2 ├┤2 ├┤2 ├┤2 ├»\n",
" ┌───┐│ ││ ││ ││ │»\n",
"q_11: ┤ X ├┤3 ├┤3 ├┤3 ├┤3 ├»\n",
" └───┘└─────────────┘└─────────────┘└─────────────┘└─────────────┘»\n",
" c_0: ═════════════════════════════════════════════════════════════════»\n",
" »\n",
" c_1: ═════════════════════════════════════════════════════════════════»\n",
" »\n",
" c_2: ═════════════════════════════════════════════════════════════════»\n",
" »\n",
" c_3: ═════════════════════════════════════════════════════════════════»\n",
" »\n",
" c_4: ═════════════════════════════════════════════════════════════════»\n",
" »\n",
" c_5: ═════════════════════════════════════════════════════════════════»\n",
" »\n",
" c_6: ═════════════════════════════════════════════════════════════════»\n",
" »\n",
" c_7: ═════════════════════════════════════════════════════════════════»\n",
" »\n",
"« »\n",
"« q_0: ─────────────────────────────────────────────────────────────────»\n",
"« »\n",
"« q_1: ─────────────────────────────────────────────────────────────────»\n",
"« »\n",
"« q_2: ─────────────────────────────────────────────────────────────────»\n",
"« »\n",
"« q_3: ─────────────────────────────────────────────────────────────────»\n",
"« »\n",
"« q_4: ───────■─────────────────────────────────────────────────────────»\n",
"« │ »\n",
"« q_5: ───────┼───────────────■─────────────────────────────────────────»\n",
"« │ │ »\n",
"« q_6: ───────┼───────────────┼───────────────■─────────────────────────»\n",
"« │ │ │ »\n",
"« q_7: ───────┼───────────────┼───────────────┼────────────────■────────»\n",
"« ┌──────┴───────┐┌──────┴───────┐┌──────┴───────┐┌──────┴┼───────┐»\n",
"« q_8: ┤0 ├┤0 ├┤0 ├┤0 │ ├»\n",
"« │ ││ ││ ││ │»\n",
"« q_9: ┤1 ├┤1 ├┤1 ├┤1 ├»\n",
"« │ 7^16 mod 15 ││ 7^32 mod 15 ││ 7^64 mod 15 ││ 7^128 mod 15 │»\n",
"«q_10: ┤2 ├┤2 ├┤2 ├┤2 ├»\n",
"« │ ││ ││ ││ │»\n",
"«q_11: ┤3 ├┤3 ├┤3 ├┤3 ├»\n",
"« └──────────────┘└──────────────┘└──────────────┘└───────────────┘»\n",
"« c_0: ═════════════════════════════════════════════════════════════════»\n",
"« »\n",
"« c_1: ═════════════════════════════════════════════════════════════════»\n",
"« »\n",
"« c_2: ═════════════════════════════════════════════════════════════════»\n",
"« »\n",
"« c_3: ═════════════════════════════════════════════════════════════════»\n",
"« »\n",
"« c_4: ═════════════════════════════════════════════════════════════════»\n",
"« »\n",
"« c_5: ═════════════════════════════════════════════════════════════════»\n",
"« »\n",
"« c_6: ═════════════════════════════════════════════════════════════════»\n",
"« »\n",
"« c_7: ═════════════════════════════════════════════════════════════════»\n",
"« »\n",
"« ┌───────┐┌─┐ \n",
"« q_0: ┤0 ├┤M├─────────────────────\n",
"« │ │└╥┘┌─┐ \n",
"« q_1: ┤1 ├─╫─┤M├──────────────────\n",
"« │ │ ║ └╥┘┌─┐ \n",
"« q_2: ┤2 ├─╫──╫─┤M├───────────────\n",
"« │ │ ║ ║ └╥┘┌─┐ \n",
"« q_3: ┤3 ├─╫──╫──╫─┤M├────────────\n",
"« │ QFT† │ ║ ║ ║ └╥┘┌─┐ \n",
"« q_4: ┤4 ├─╫──╫──╫──╫─┤M├─────────\n",
"« │ │ ║ ║ ║ ║ └╥┘┌─┐ \n",
"« q_5: ┤5 ├─╫──╫──╫──╫──╫─┤M├──────\n",
"« │ │ ║ ║ ║ ║ ║ └╥┘┌─┐ \n",
"« q_6: ┤6 ├─╫──╫──╫──╫──╫──╫─┤M├───\n",
"« │ │ ║ ║ ║ ║ ║ ║ └╥┘┌─┐\n",
"« q_7: ┤7 ├─╫──╫──╫──╫──╫──╫──╫─┤M├\n",
"« └───────┘ ║ ║ ║ ║ ║ ║ ║ └╥┘\n",
"« q_8: ──────────╫──╫──╫──╫──╫──╫──╫──╫─\n",
"« ║ ║ ║ ║ ║ ║ ║ ║ \n",
"« q_9: ──────────╫──╫──╫──╫──╫──╫──╫──╫─\n",
"« ║ ║ ║ ║ ║ ║ ║ ║ \n",
"«q_10: ──────────╫──╫──╫──╫──╫──╫──╫──╫─\n",
"« ║ ║ ║ ║ ║ ║ ║ ║ \n",
"«q_11: ──────────╫──╫──╫──╫──╫──╫──╫──╫─\n",
"« ║ ║ ║ ║ ║ ║ ║ ║ \n",
"« c_0: ══════════╩══╬══╬══╬══╬══╬══╬══╬═\n",
"« ║ ║ ║ ║ ║ ║ ║ \n",
"« c_1: ═════════════╩══╬══╬══╬══╬══╬══╬═\n",
"« ║ ║ ║ ║ ║ ║ \n",
"« c_2: ════════════════╩══╬══╬══╬══╬══╬═\n",
"« ║ ║ ║ ║ ║ \n",
"« c_3: ═══════════════════╩══╬══╬══╬══╬═\n",
"« ║ ║ ║ ║ \n",
"« c_4: ══════════════════════╩══╬══╬══╬═\n",
"« ║ ║ ║ \n",
"« c_5: ═════════════════════════╩══╬══╬═\n",
"« ║ ║ \n",
"« c_6: ════════════════════════════╩══╬═\n",
"« ║ \n",
"« c_7: ═══════════════════════════════╩═\n",
"« "
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Create QuantumCircuit with n_count counting qubits\n",
"# plus 4 qubits for U to act on\n",
"qc = QuantumCircuit(n_count + 4, n_count)\n",
"\n",
"# Initialise counting qubits\n",
"# in state |+>\n",
"for q in range(n_count):\n",
" qc.h(q)\n",
" \n",
"# And ancilla register in state |1>\n",
"qc.x(3+n_count)\n",
"\n",
"# Do controlled-U operations\n",
"for q in range(n_count):\n",
" qc.append(c_amod15(a, 2**q), \n",
" [q] + [i+n_count for i in range(4)])\n",
"\n",
"# Do inverse-QFT\n",
"qc.append(qft_dagger(n_count), range(n_count))\n",
"\n",
"# Measure circuit\n",
"qc.measure(range(n_count), range(n_count))\n",
"qc.draw('text')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's see what results we measure:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n",
" \n"
],
"text/plain": [
""
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"backend = Aer.get_backend('qasm_simulator')\n",
"results = execute(qc, backend, shots=2048).result()\n",
"counts = results.get_counts()\n",
"plot_histogram(counts)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Since we have 3 qubits, these results correspond to measured phases of:"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" Register Output Phase\n",
"0 00000000(bin) = 0(dec) 0/256 = 0.00\n",
"1 01000000(bin) = 64(dec) 64/256 = 0.25\n",
"2 10000000(bin) = 128(dec) 128/256 = 0.50\n",
"3 11000000(bin) = 192(dec) 192/256 = 0.75\n"
]
}
],
"source": [
"rows, measured_phases = [], []\n",
"for output in counts:\n",
" decimal = int(output, 2) # Convert (base 2) string to decimal\n",
" phase = decimal/(2**n_count) # Find corresponding eigenvalue\n",
" measured_phases.append(phase)\n",
" # Add these values to the rows in our table:\n",
" rows.append([\"%s(bin) = %i(dec)\" % (output, decimal), \n",
" \"%i/%i = %.2f\" % (decimal, 2**n_count, phase)])\n",
"# Print the rows in a table\n",
"headers=[\"Register Output\", \"Phase\"]\n",
"df = pd.DataFrame(rows, columns=headers)\n",
"print(df)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can now use the continued fractions algorithm to attempt to find $s$ and $r$. Python has this functionality built in: We can use the `fractions` module to turn a float into a `Fraction` object, for example:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Fraction(5998794703657501, 9007199254740992)"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Fraction(0.666)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.666"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"5998794703657501/9007199254740992"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Because this gives fractions that return the result exactly (in this case, `0.6660000...`), this can give gnarly results like the one above. We can use the `.limit_denominator()` method to get the fraction that most closely resembles our float, with denominator below a certain value:"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Fraction(2, 3)"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Get fraction that most closely resembles 0.666\n",
"# with denominator < 15\n",
"Fraction(0.666).limit_denominator(15)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Much nicer! The order (r) must be less than N, so we will set the maximum denominator to be `15`:"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" Phase Fraction Guess for r\n",
"0 0.00 0/1 1\n",
"1 0.25 1/4 4\n",
"2 0.50 1/2 2\n",
"3 0.75 3/4 4\n"
]
}
],
"source": [
"rows = []\n",
"for phase in measured_phases:\n",
" frac = Fraction(phase).limit_denominator(15)\n",
" rows.append([phase, \"%i/%i\" % (frac.numerator, frac.denominator), frac.denominator])\n",
"# Print as a table\n",
"headers=[\"Phase\", \"Fraction\", \"Guess for r\"]\n",
"df = pd.DataFrame(rows, columns=headers)\n",
"print(df)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can see that two of the measured eigenvalues provided us with the correct result: $r=4$, and we can see that Shor’s algorithm has a chance of failing. These bad results are because $s = 0$, or because $s$ and $r$ are not coprime and instead of $r$ we are given a factor of $r$. The easiest solution to this is to simply repeat the experiment until we get a satisfying result for $r$.\n",
"\n",
"### Quick Exercise\n",
"\n",
"- Modify the circuit above for values of $a = 2, 8, 11$ and $13$. What results do you get and why?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 4. Modular Exponentiation\n",
"\n",
"You may have noticed that the method of creating the $U^{2^j}$ gates by repeating $U$ grows exponentially with $j$ and will not result in a polynomial time algorithm. We want a way to create the operator:\n",
"\n",
"$$ U^{2^j}|y\\rangle = |a^{2^j}y \\bmod N \\rangle $$\n",
"\n",
"that grows polynomially with $j$. Fortunately, calculating:\n",
"\n",
"$$ a^{2^j} \\bmod N$$\n",
"\n",
"efficiently is possible. Classical computers can use an algorithm known as _repeated squaring_ to calculate an exponential. In our case, since we are only dealing with exponentials of the form $2^j$, the repeated squaring algorithm becomes very simple:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"tags": [
"thebelab-init"
]
},
"outputs": [],
"source": [
"def a2jmodN(a, j, N):\n",
" \"\"\"Compute a^{2^j} (mod N) by repeated squaring\"\"\"\n",
" for i in range(j):\n",
" a = np.mod(a**2, N)\n",
" return a"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"47"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a2jmodN(7, 2049, 53)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If an efficient algorithm is possible in Python, then we can use the same algorithm on a quantum computer. Unfortunately, despite scaling polynomially with $j$, modular exponentiation circuits are not straightforward and are the bottleneck in Shor’s algorithm. A beginner-friendly implementation can be found in reference [1].\n",
"\n",
"## 5. Factoring from Period Finding\n",
"\n",
"Not all factoring problems are difficult; we can spot an even number instantly and know that one of its factors is 2. In fact, there are [specific criteria](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf#%5B%7B%22num%22%3A127%2C%22gen%22%3A0%7D%2C%7B%22name%22%3A%22XYZ%22%7D%2C70%2C223%2C0%5D) for choosing numbers that are difficult to factor, but the basic idea is to choose the product of two large prime numbers.\n",
"\n",
"A general factoring algorithm will first check to see if there is a shortcut to factoring the integer (is the number even? Is the number of the form $N = a^b$?), before using Shor’s period finding for the worst-case scenario. Since we aim to focus on the quantum part of the algorithm, we will jump straight to the case in which N is the product of two primes.\n",
"\n",
"### Example: Factoring 15\n",
"\n",
"To see an example of factoring on a small number of qubits, we will factor 15, which we all know is the product of the not-so-large prime numbers 3 and 5."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"tags": [
"thebelab-init"
]
},
"outputs": [],
"source": [
"N = 15"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The first step is to choose a random number, $x$, between $1$ and $N-1$:"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"tags": [
"thebelab-init"
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"7\n"
]
}
],
"source": [
"np.random.seed(1) # This is to make sure we get reproduceable results\n",
"a = randint(2, 15)\n",
"print(a)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Next we quickly check it isn't already a non-trivial factor of $N$:"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from math import gcd # greatest common divisor\n",
"gcd(a, 15)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Great. Next, we do Shor's order finding algorithm for `a = 7` and `N = 15`. Remember that the phase we measure will be $s/r$ where:\n",
"\n",
"$$ a^r \\bmod N = 1 $$\n",
"\n",
"and $s$ is a random integer between 0 and $r-1$."
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"tags": [
"thebelab-init"
]
},
"outputs": [],
"source": [
"def qpe_amod15(a):\n",
" n_count = 3\n",
" qc = QuantumCircuit(4+n_count, n_count)\n",
" for q in range(n_count):\n",
" qc.h(q) # Initialise counting qubits in state |+>\n",
" qc.x(3+n_count) # And ancilla register in state |1>\n",
" for q in range(n_count): # Do controlled-U operations\n",
" qc.append(c_amod15(a, 2**q), \n",
" [q] + [i+n_count for i in range(4)])\n",
" qc.append(qft_dagger(n_count), range(n_count)) # Do inverse-QFT\n",
" qc.measure(range(n_count), range(n_count))\n",
" # Simulate Results\n",
" backend = Aer.get_backend('qasm_simulator')\n",
" # Setting memory=True below allows us to see a list of each sequential reading\n",
" result = execute(qc, backend, shots=1, memory=True).result()\n",
" readings = result.get_memory()\n",
" print(\"Register Reading: \" + readings[0])\n",
" phase = int(readings[0],2)/(2**n_count)\n",
" print(\"Corresponding Phase: %f\" % phase)\n",
" return phase"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"From this phase, we can easily find a guess for $r$:"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Register Reading: 000\n",
"Corresponding Phase: 0.000000\n"
]
},
{
"data": {
"text/plain": [
"Fraction(0, 1)"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"np.random.seed(3) # This is to make sure we get reproduceable results\n",
"phase = qpe_amod15(a) # Phase = s/r\n",
"Fraction(phase).limit_denominator(15) # Denominator should (hopefully!) tell us r"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1\n"
]
}
],
"source": [
"frac = Fraction(phase).limit_denominator(15)\n",
"s, r = frac.numerator, frac.denominator\n",
"print(r)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we have $r$, we might be able to use this to find a factor of $N$. Since:\n",
"\n",
"$$a^r \\bmod N = 1 $$\n",
"\n",
"then:\n",
"\n",
"$$(a^r - 1) \\bmod N = 0 $$\n",
"\n",
"which mean $N$ must divide $a^r-1$. And if $r$ is also even, then we can write:\n",
"\n",
"$$a^r -1 = (a^{r/2}-1)(a^{r/2}+1)$$\n",
"\n",
"(if $r$ is not even, we cannot go further and must try again with a different value for $a$). There is then a high probability that the greatest common divisor of either $a^{r/2}-1$, or $a^{r/2}+1$ is a factor of $N$ [2]:"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[15, 1]\n"
]
}
],
"source": [
"guesses = [gcd(a**(r//2)-1, N), gcd(a**(r//2)+1, N)]\n",
"print(guesses)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The cell below repeats the algorithm until at least one factor of 15 is found. You should try re-running the cell a few times to see how it behaves."
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"Attempt 1:\n",
"Register Reading: 000\n",
"Corresponding Phase: 0.000000\n",
"Result: r = 1\n",
"\n",
"Attempt 2:\n",
"Register Reading: 100\n",
"Corresponding Phase: 0.500000\n",
"Result: r = 2\n",
"Guessed Factors: 3 and 1\n",
"*** Non-trivial factor found: 3 ***\n"
]
}
],
"source": [
"a = 7\n",
"factor_found = False\n",
"attempt = 0\n",
"while not factor_found:\n",
" attempt += 1\n",
" print(\"\\nAttempt %i:\" % attempt)\n",
" phase = qpe_amod15(a) # Phase = s/r\n",
" frac = Fraction(phase).limit_denominator(15) # Denominator should (hopefully!) tell us r\n",
" r = frac.denominator\n",
" print(\"Result: r = %i\" % r)\n",
" if phase != 0:\n",
" # Guesses for factors are gcd(x^{r/2} ±1 , 15)\n",
" guesses = [gcd(a**(r//2)-1, 15), gcd(a**(r//2)+1, 15)]\n",
" print(\"Guessed Factors: %i and %i\" % (guesses[0], guesses[1]))\n",
" for guess in guesses:\n",
" if guess != 1 and (15 % guess) == 0: # Check to see if guess is a factor\n",
" print(\"*** Non-trivial factor found: %i ***\" % guess)\n",
" factor_found = True"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 6. References\n",
"\n",
"1. Stephane Beauregard, _Circuit for Shor's algorithm using 2n+3 qubits,_ [arXiv:quant-ph/0205095](https://arxiv.org/abs/quant-ph/0205095)\n",
"\n",
"2. M. Nielsen and I. Chuang, _Quantum Computation and Quantum Information,_ Cambridge Series on Information and the Natural Sciences (Cambridge University Press, Cambridge, 2000). (Page 633)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'qiskit-terra': '0.14.2',\n",
" 'qiskit-aer': '0.5.2',\n",
" 'qiskit-ignis': '0.3.3',\n",
" 'qiskit-ibmq-provider': '0.7.2',\n",
" 'qiskit-aqua': '0.7.3',\n",
" 'qiskit': '0.19.6'}"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import qiskit\n",
"qiskit.__qiskit_version__"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.7"
}
},
"nbformat": 4,
"nbformat_minor": 4
}