{ "cells": [ { "cell_type": "markdown", "id": "60966d6f", "metadata": {}, "source": [ "# Order finding for a small modular multiplication\n", "\n", "**Level:** Undergraduate · **Book connections:** P06, P09, P11, P19, A11, A12, A13, A14\n", "\n", "After this notebook you can:\n", "\n", "- Construct a modular permutation from a and N without supplying the order.\n", "- Explain controlled powers, inverse QFT peaks and rational reconstruction.\n", "- Separate a small exact demonstration from scalable arithmetic implementation.\n", "\n", "Run cells from top to bottom in the pinned environment described in `README.md`. All default execution is local. Exact amplitudes are simulator information; a QPU supplies sampled outcomes." ] }, { "cell_type": "code", "execution_count": null, "id": "464bc0bc", "metadata": {}, "outputs": [], "source": [ "from importlib.metadata import version\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "from IPython.display import display\n", "from qiskit import QuantumCircuit\n", "from qiskit.quantum_info import Statevector\n", "\n", "EXPECTED = {\"qiskit\": \"2.6.1\", \"qiskit-aer\": \"0.18.2\", \"qiskit-ibm-runtime\": \"0.51.0\"}\n", "for package, expected in EXPECTED.items():\n", " actual = version(package)\n", " assert actual == expected, f\"Use the supplied environment: {package}={actual}, expected {expected}\"\n", "print(\"Verified package versions:\", EXPECTED)\n", "plt.rcParams.update({\"figure.figsize\": (8, 3.5), \"font.size\": 11, \"axes.spines.top\": False,\n", " \"axes.spines.right\": False, \"axes.prop_cycle\": plt.cycler(color=[\"#006DAE\", \"#00A6B2\", \"#9E4A78\"])})\n", "SEED = 20261106\n", "\n", "def draw(circuit):\n", " \"\"\"Render a real circuit; each wire is a qubit, time runs left to right.\"\"\"\n", " fig = circuit.draw(output=\"mpl\", fold=90, style=\"iqp\")\n", " display(fig)\n", " plt.close(fig)\n", "\n", "def book_label(qiskit_label):\n", " \"\"\"For a single register, show q0 first as in the book.\"\"\"\n", " return qiskit_label[::-1]" ] }, { "cell_type": "markdown", "id": "b43ca55e", "metadata": {}, "source": [ "**Read the wires and bit strings carefully.** Qiskit draws `q0` on the top wire, but a\n", "standard statevector basis label or measured single-register count key is written\n", "`q(n−1)…q1q0`: `q0` has integer weight $2^0$. The book often writes `q0` first.\n", "These notebooks keep native Qiskit labels in calculations and use `book_label`\n", "only for an explicitly labelled display. Reversing a label changes the display;\n", "it does not apply a SWAP gate. All count examples here use one classical register\n", "with measurement `qj → cj`; do not reverse arbitrary multi-register strings." ] }, { "cell_type": "markdown", "id": "90c7a848", "metadata": {}, "source": [ "## 1. The order is the output we want\n", "\n", "Given coprime integers $a,N$, find the smallest positive $r$ satisfying\n", "$a^r\\equiv1\\pmod N$. We use $N=15,a=2$ because its circuit is small enough to\n", "inspect. The circuit builder never receives $r$.\n", "\n", "On the work register, multiplication is a reversible permutation:\n", "\n", "$$U_a|x\\rangle=|ax\\bmod N\\rangle\\quad(0\\le x= 2 and gcd(a, N) = 1\")\n", " m = ceil(log2(N))\n", " matrix = np.zeros((2**m, 2**m), dtype=complex)\n", " for x in range(2**m):\n", " destination = (a*x) % N if x < N else x\n", " matrix[destination, x] = 1\n", " np.testing.assert_allclose(matrix.conj().T @ matrix, np.eye(2**m), atol=1e-12)\n", " return matrix\n", "\n", "N, a, t = 15, 2, 4\n", "m = ceil(log2(N))\n", "multiplication = modular_multiplication_matrix(a, N)\n", "for x in range(N):\n", " assert np.argmax(abs(multiplication[:, x])) == (a*x) % N\n", "print(\"Matrix shape:\", multiplication.shape, \"work qubits:\", m, \"counting qubits:\", t)" ] }, { "cell_type": "markdown", "id": "f30e6997", "metadata": {}, "source": [ "## 2. Controlled powers create the periodic structure\n", "\n", "The counting register begins in uniform superposition and the work register in\n", "$|1\\rangle$. Counting qubit $j$ controls multiplication by $a^{2^j}\\bmod N$.\n", "The joint state before inverse QFT is\n", "\n", "$$\\frac1{\\sqrt{2^t}}\\sum_{x=0}^{2^t-1}|x\\rangle|a^x\\bmod N\\rangle.$$\n", "\n", "Inverse QFT on the counting register gives peaks near integers $k\\,2^t/r$.\n", "The function below uses repeated squaring through Python's modular `pow`, not\n", "a table of peaks or a hard-coded recovered period." ] }, { "cell_type": "code", "execution_count": null, "id": "d688a96b", "metadata": {}, "outputs": [], "source": [ "def order_finding_circuit(a, N, counting_qubits):\n", " work_qubits = ceil(log2(N))\n", " counting = list(range(counting_qubits))\n", " work = list(range(counting_qubits, counting_qubits+work_qubits))\n", " circuit = QuantumCircuit(counting_qubits+work_qubits)\n", " circuit.h(counting)\n", " circuit.x(work[0]) # Little-endian work value 1.\n", " for j in counting:\n", " multiplier = pow(a, 2**j, N)\n", " gate = UnitaryGate(modular_multiplication_matrix(multiplier, N), label=f\"times {multiplier} mod {N}\")\n", " circuit.append(gate.control(1), [j]+work)\n", " circuit.append(QFTGate(counting_qubits).inverse(), counting)\n", " return circuit\n", "\n", "order_circuit = order_finding_circuit(a, N, t)\n", "draw(order_circuit)\n", "state = Statevector.from_instruction(order_circuit)\n", "counting_probabilities = state.probabilities(qargs=list(range(t)))\n", "plt.bar(range(2**t), counting_probabilities)\n", "plt.xlabel(\"Counting integer y, native binary q(t-1)...q0\")\n", "plt.ylabel(\"Exact ideal probability\")\n", "plt.xticks(range(2**t))\n", "plt.show()\n", "assert np.isclose(counting_probabilities.sum(), 1)\n", "print(\"Nonzero probabilities:\", {format(y, f\"0{t}b\"): round(float(p), 8)\n", " for y, p in enumerate(counting_probabilities) if p > 1e-10})" ] }, { "cell_type": "markdown", "id": "d0e85064", "metadata": {}, "source": [ "## 3. Use sampled data and verify candidate denominators\n", "\n", "A measured $y$ estimates a phase $y/2^t\\approx k/r$. A reduced fraction may\n", "give only a divisor of $r$; the zero peak gives no useful denominator.\n", "Here we collect denominator information and verify a candidate with modular\n", "exponentiation. A general implementation needs continued-fraction candidates,\n", "sufficient precision, repeated runs and explicit failure handling." ] }, { "cell_type": "code", "execution_count": null, "id": "b2f5bc92", "metadata": {}, "outputs": [], "source": [ "from qiskit.primitives import StatevectorSampler\n", "measured = order_circuit.copy()\n", "from qiskit import ClassicalRegister\n", "measured.add_register(ClassicalRegister(t, \"phase\"))\n", "measured.measure(range(t), measured.cregs[0])\n", "counts = StatevectorSampler(seed=SEED).run([measured], shots=128).result()[0].data.phase.get_counts()\n", "denominators = []\n", "for bits, frequency in sorted(counts.items()):\n", " y = int(bits, 2)\n", " approximation = Fraction(y, 2**t).limit_denominator(N)\n", " print(bits, frequency, \"phase:\", Fraction(y, 2**t), \"candidate:\", approximation)\n", " if y != 0:\n", " denominators.append(approximation.denominator)\n", "assert denominators, \"No useful phase observed; collect another run\"\n", "candidate = reduce(lcm, denominators, 1)\n", "assert pow(a, candidate, N) == 1, \"Candidate needs verification or another run\"\n", "# Small-instance reduction: trial-factor the candidate, then remove redundant factors.\n", "# This helper is illustrative classical work, not an efficient large-integer factoring routine.\n", "prime_factors = []\n", "remaining = candidate\n", "factor = 2\n", "while factor*factor <= remaining:\n", " if remaining % factor == 0:\n", " prime_factors.append(factor)\n", " while remaining % factor == 0:\n", " remaining //= factor\n", " factor += 1\n", "if remaining > 1:\n", " prime_factors.append(remaining)\n", "order = candidate\n", "for factor in prime_factors:\n", " while order % factor == 0 and pow(a, order//factor, N) == 1:\n", " order //= factor\n", "assert pow(a, order, N) == 1\n", "print(\"Verified order from sampled phases:\", order)\n", "if order % 2 == 0:\n", " midpoint = pow(a, order//2, N)\n", " factors = (gcd(midpoint-1, N), gcd(midpoint+1, N))\n", " print(\"Classical gcd step gives:\", factors)\n", " assert all(1 < f < N for f in factors)\n", " assert factors[0]*factors[1] == N\n", "# Instance-specific independent regression check, not a circuit input.\n", "assert order == 4" ] }, { "cell_type": "markdown", "id": "ef0272af", "metadata": {}, "source": [ "## Checkpoint and practice\n", "\n", "Is the `0000` phase outcome an algorithm bug? **No:** the zero phase is a valid\n", "peak, but its classical post-processing is uninformative. A successful single\n", "shot is probabilistic even when the ideal peak positions are exact.\n", "\n", "1. Inspect the work permutation for $a=7,N=15$ before rerunning the circuit.\n", "2. Try $a=2,N=7$ with more counting qubits. Explain why peaks no longer fall\n", " exactly on all of the finite grid points and why denominator filtering needs care.\n", "3. Report width and matrix storage for increasing $N$. Explain why dense-unitary\n", " simulation does not demonstrate an efficient factoring implementation.\n", "\n", "**Takeaway:** the period emerges from modular action and interference; the known\n", "answer is used only as an independent test on this small instance." ] }, { "cell_type": "markdown", "id": "747e5a21", "metadata": {}, "source": [ "## Sources\n", "\n", "- [IBM: bit ordering](https://quantum.cloud.ibm.com/docs/en/guides/bit-ordering)\n", "- [IBM: Statevector API](https://quantum.cloud.ibm.com/docs/en/api/qiskit/qiskit.quantum_info.Statevector)\n", "- [IBM: QFTGate API](https://quantum.cloud.ibm.com/docs/en/api/qiskit/qiskit.circuit.library.QFTGate)\n", "- [Shor: polynomial-time algorithms for prime factorization and discrete logarithms](https://arxiv.org/abs/quant-ph/9508027)" ] } ], "metadata": { "kernelspec": { "display_name": "Quantum book (pinned Python)", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3.13.2" }, "quantum_book": { "chapters": [ "P06", "P09", "P11", "P19", "A11", "A12", "A13", "A14" ], "expected_packages": { "qiskit": "2.6.1", "qiskit-aer": "0.18.2", "qiskit-ibm-runtime": "0.51.0" }, "level": "Undergraduate", "network_on_default_run": false, "verified_release_date": "2026-11-06" } }, "nbformat": 4, "nbformat_minor": 5 }