{ "cells": [ { "cell_type": "markdown", "id": "a12d0239", "metadata": {}, "source": [ "# Arithmetic Examples\n", "\n", "**Download Notebook** - {nb-download}`arithmetic_demo.ipynb`\n", "\n", "Quantum arithmetic protocols have applications across a wide range of quantum algorithms, from solving differential equations and simulating first-quantized Hamiltonians to integer factorization with Shor’s algorithm.\n", "\n", "- [Addition](#addition)\n", " - [Subtraction](#subtraction)\n", " - [Controlled addition and subtraction](#controlled-addition-and-subtraction)\n", "- [Comparison](#comparison)\n", "- [Incrementation](#incrementation)\n", "- [Multiplication](#multiplication)\n", "- [Exponentiation](#exponentiation)" ] }, { "cell_type": "code", "execution_count": 1, "id": "9c1b2681", "metadata": {}, "outputs": [], "source": [ "from typing import no_type_check\n", "from collections.abc import Callable\n", "\n", "from guppylang import guppy\n", "from guppylang.std.builtins import array, output\n", "from guppylang.std.quantum import qubit, discard, measure_array, measure, collect_measurements, x\n", "from guppyalgos.utils import int_to_bits, bits_to_int, apply_bitstring, qarray\n", "from guppylang.defs import GuppyFunctionDefinition" ] }, { "cell_type": "markdown", "id": "76f2affa", "metadata": {}, "source": [ "## Addition\n", "\n", "The adder is a fundamental building block underlying many more sophisticated arithmetic primitives.\n", "\n", "The adders implemented here operate in place: the first input register is preserved, while the second is overwritten with the sum. For two $n$-bit integers $a$ and $b$, modular addition stores the $n$ least-significant bits and discards any overflow:\n", "\n", "$$\n", "|a\\rangle|b\\rangle\n", "\\longmapsto\n", "|a\\rangle|(a+b)\\bmod 2^n\\rangle.\n", "$$\n", "\n", "Non-modular addition retains the overflow in a separate carry qubit $z$:\n", "\n", "$$\n", "|a\\rangle|b\\rangle|z\\rangle\n", "\\longmapsto\n", "|a\\rangle|(a+b)\\bmod 2^n\\rangle\n", "\\left|z\\oplus\\left\\lfloor\\frac{a+b}{2^n}\\right\\rfloor\\right\\rangle.\n", "$$\n", "\n", "Together, the updated $b$ register and the carry qubit represent the complete $(n+1)$-bit sum. Here, $\\oplus$ denotes XOR.\n", "\n", "### Ripple-carry adders\n", "\n", "Ripple-carry adders propagate carry information sequentially from the least-significant bit to the most-significant bit. The forward pass computes the carries, while the reverse pass uses them to produce the sum and simultaneously uncomputes the intermediate carry information. This forward-and-reverse pattern gives the circuit its characteristic V-shaped structure.\n", "\n", "Together, the two passes implement the same bitwise recurrence as schoolbook binary addition. For example:\n", "\n", "```text\n", " 1111\n", " + 0110\n", " ------\n", " 10101\n", " ------\n", " 1110 <- carries\n", "```\n", "The carries are listed from the most-significant input column to the least-significant input column. The initial input carry is 0.\n", "\n", "\n", "In a standard ripple-carry implementation, each carry depends on the carry from the preceding bit, giving the circuit linear depth. The following ripple-carry adders are implemented:\n", "\n", "* **Cuccaro adder:** Uses majority (`MAJ`) operations to propagate the carries forward and unmajority-and-add (`UMAJ`) operations to uncompute them while producing the sum. See [Cuccaro *et al.*, “A new quantum ripple-carry addition circuit”](https://arxiv.org/abs/quant-ph/0410184).\n", "In this codebase, the circuit is expressed in terms of CNOT and Toffoli ladders. Using the naive, linear-depth ladders gives the standard implementation, which requires one ancilla qubit and has $\\mathcal{O}(n)$ depth. Alternative ladder implementations are available in {mod}`guppyalgos.primitives.subroutines.ladders`, and the {doc}`Toffoli ladder example notebook ` demonstrates both naive and logarithmic-depth Toffoli ladder constructions using $\\mathcal{O}(n)$ ancilla qubits. When logarithmic-depth implementations are used for both the Toffoli and CNOT ladders, the resulting adder has $\\mathcal{O}(\\log n)$ depth and $\\mathcal{O}(n)$ gate count, at the cost of $\\mathcal{O}(n)$ ancilla qubits.\n", "These depth–space trade-offs are discussed by [Remaud, “Quantum adders: on the structural link between the ripple-carry and carry-lookahead techniques”](https://arxiv.org/abs/2510.00840).\n", "\n", "* **Gidney adder:** Replaces pairs of Toffoli operations with temporary logical-AND computations and measurement-based uncomputation. This reduces the $T$-count of an $n$-bit adder from $8n+\\mathcal{O}(1)$ to $4n+\\mathcal{O}(1)$. The implementation used here requires $\\mathcal{O}(n)$ ancilla qubits and has $\\mathcal{O}(n)$ depth. See [Gidney, “Halving the cost of quantum addition”](https://quantum-journal.org/papers/q-2018-06-18-74/).\n", "\n", "\n", "Both adders are available in modular and carry-out variants:\n", "\n", "- ``adder_ripple_gidney_mod`` and ``adder_ripple_cuccaro_mod`` perform addition modulo $2^n$, discarding any overflow.\n", "- ``adder_ripple_gidney_carry_out`` and ``adder_ripple_cuccaro_carry_out`` retain the overflow in a separate carry qubit, producing the complete $(n+1)$-bit sum." ] }, { "cell_type": "code", "execution_count": 2, "id": "3743bd0d", "metadata": {}, "outputs": [], "source": [ "def run_adder_case(\n", " adder: GuppyFunctionDefinition,\n", " qubit_budget: int,\n", " n: int,\n", " a: int,\n", " b: int,\n", ") -> dict:\n", " \"\"\"Run one uncontrolled non-modular addition case and return measured bits.\"\"\"\n", " a_bit_array = array(*int_to_bits(a, n))\n", " b_bit_array = array(*int_to_bits(b, n))\n", "\n", " @guppy\n", " @no_type_check\n", " def main() -> None:\n", " # Prepare |a>|b>|0>\n", " a_reg = qarray(n)\n", " b_reg = qarray(n)\n", " carry_out = qubit()\n", "\n", " apply_bitstring(a_reg, a_bit_array)\n", " apply_bitstring(b_reg, b_bit_array)\n", "\n", " # Compute a + b. The lower n bits are written to b_reg,\n", " # and the overflow bit is written to carry_out.\n", " adder(a_reg, b_reg, carry_out)\n", "\n", " output(\"a_meas\", collect_measurements(measure_array(a_reg)))\n", " output(\"sum\", collect_measurements(measure_array(b_reg)))\n", " output(\"carry_out\", measure(carry_out).read())\n", "\n", "\n", " res = main.emulator(n_qubits=qubit_budget).run()\n", " return res.results[0].as_dict()" ] }, { "cell_type": "code", "execution_count": 3, "id": "5cf67030", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n=2, a=1, b=1 -> sum=2, carry=0, full sum=2 (expected 2)\n", "n=2, a=2, b=3 -> sum=1, carry=1, full sum=5 (expected 5)\n", "n=3, a=3, b=2 -> sum=5, carry=0, full sum=5 (expected 5)\n", "n=4, a=5, b=7 -> sum=12, carry=0, full sum=12 (expected 12)\n", "Uncontrolled adder checks passed.\n" ] } ], "source": [ "from guppyalgos.primitives.arithmetic import adder_ripple_gidney_carry_out\n", "\n", "uncontrolled_cases = [(2, 1, 1), (2, 2, 3), (3, 3, 2), (4, 5, 7)]\n", "\n", "for n, a, b in uncontrolled_cases:\n", " n_gidney_ancilla = n - 1\n", " qubit_budget = 2 * n + 1 + n_gidney_ancilla\n", " result = run_adder_case(adder_ripple_gidney_carry_out, qubit_budget, n, a, b)\n", "\n", " full_sum = a + b\n", " expected_sum = full_sum % (2**n)\n", " expected_carry = full_sum >> n\n", "\n", " assert result[\"a_meas\"] == int_to_bits(a, n)\n", " assert result[\"sum\"] == int_to_bits(expected_sum, n)\n", " assert int(result[\"carry_out\"]) == expected_carry\n", "\n", " measured_sum = bits_to_int(result[\"sum\"])\n", " measured_carry = int(result[\"carry_out\"])\n", "\n", " # The carry and low n bits reconstruct the complete sum.\n", " reconstructed_sum = measured_sum + measured_carry * (2**n)\n", " assert reconstructed_sum == full_sum\n", "\n", " print(\n", " f\"n={n}, a={a}, b={b} -> \"\n", " f\"sum={measured_sum}, carry={measured_carry}, \"\n", " f\"full sum={reconstructed_sum} (expected {full_sum})\"\n", " )\n", "\n", "print(\"Uncontrolled adder checks passed.\")" ] }, { "cell_type": "markdown", "id": "c1b9f121", "metadata": {}, "source": [ "### Subtraction\n", "\n", "Subtraction is implemented by applying the corresponding addition circuit in reverse. The first register is preserved, while the second is updated from $b$ to $b-a$.\n", "\n", "Both subtractors are available in modular and borrow-out variants:\n", "\n", "- ``subtractor_ripple_gidney_mod`` and ``subtractor_ripple_cuccaro_mod`` perform subtraction modulo $2^n$:\n", "\n", "$$\n", "|a\\rangle|b\\rangle\n", "\\longmapsto\n", "|a\\rangle|(b-a)\\bmod 2^n\\rangle.\n", "$$\n", "\n", "Any underflow is discarded.\n", "\n", "- ``subtractor_ripple_gidney_carry_out`` and ``subtractor_ripple_cuccaro_carry_out`` record underflow in a separate qubit:\n", "\n", "$$\n", "|a\\rangle|b\\rangle|z\\rangle\n", "\\longmapsto\n", "|a\\rangle|(b-a)\\bmod 2^n\\rangle\n", "|z\\oplus(b dict:\n", " \"\"\"Run one uncontrolled non-modular addition case and return measured bits.\"\"\"\n", " a_bit_array = array(*int_to_bits(a, n))\n", " b_bit_array = array(*int_to_bits(b, n))\n", "\n", " @guppy\n", " @no_type_check\n", " def main() -> None:\n", " # Prepare |a>|b>|0>\n", " a_reg = qarray(n)\n", " b_reg = qarray(n)\n", " borrow_out = qubit()\n", "\n", " apply_bitstring(a_reg, a_bit_array)\n", " apply_bitstring(b_reg, b_bit_array)\n", "\n", " # Compute b - a. The lower n bits are written to b_reg,\n", " # and the overflow bit is written to borrow_out.\n", " subtractor(a_reg, b_reg, borrow_out)\n", "\n", " output(\"a_meas\", collect_measurements(measure_array(a_reg)))\n", " output(\"diff\", collect_measurements(measure_array(b_reg)))\n", " output(\"borrow_out\", measure(borrow_out).read())\n", "\n", " res = main.emulator(n_qubits=qubit_budget).run()\n", " return res.results[0].as_dict()" ] }, { "cell_type": "code", "execution_count": 5, "id": "867ddc92", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n=2, a=1, b=1 -> diff=0, borrow=0, full diff=0 (expected 0)\n", "n=2, a=2, b=3 -> diff=1, borrow=0, full diff=1 (expected 1)\n", "n=3, a=3, b=2 -> diff=7, borrow=1, full diff=-1 (expected -1)\n", "n=4, a=5, b=7 -> diff=2, borrow=0, full diff=2 (expected 2)\n", "Uncontrolled subtractor checks passed.\n" ] } ], "source": [ "from guppyalgos.primitives.arithmetic import subtractor_ripple_gidney_carry_out\n", "\n", "uncontrolled_cases = [(2, 1, 1), (2, 2, 3), (3, 3, 2), (4, 5, 7)]\n", "\n", "for n, a, b in uncontrolled_cases:\n", " n_gidney_ancilla = n - 1\n", " qubit_budget = 2 * n + 1 + n_gidney_ancilla\n", "\n", " result = run_subtractor_case(subtractor_ripple_gidney_carry_out, qubit_budget, n, a, b)\n", "\n", " full_diff = b - a\n", " expected_diff = full_diff % (2**n)\n", " expected_borrow = int(b < a)\n", "\n", " assert result[\"a_meas\"] == int_to_bits(a, n)\n", " assert result[\"diff\"] == int_to_bits(expected_diff, n)\n", " assert int(result[\"borrow_out\"]) == expected_borrow\n", "\n", " measured_diff = bits_to_int(result[\"diff\"])\n", " measured_borrow = int(result[\"borrow_out\"])\n", "\n", " # The borrow and low n bits reconstruct the complete difference.\n", " reconstructed_diff = expected_diff - expected_borrow * (2**n)\n", " assert reconstructed_diff == full_diff\n", "\n", " print(\n", " f\"n={n}, a={a}, b={b} -> \"\n", " f\"diff={measured_diff}, borrow={measured_borrow}, \"\n", " f\"full diff={reconstructed_diff} (expected {full_diff})\"\n", " )\n", "\n", "\n", "print(\"Uncontrolled subtractor checks passed.\")" ] }, { "cell_type": "markdown", "id": "ee9f3981", "metadata": {}, "source": [ "**Note on underflow and overflow:** The $n$ result bits together with the carry-out qubit are sufficient to represent the full difference between unsigned inputs. If the input registers themselves represent signed values, they should instead be sign-extended to $n+1$ bits before subtraction." ] }, { "cell_type": "markdown", "id": "bf5e6c6f", "metadata": {}, "source": [ "### Controlled addition and subtraction\n", "\n", "A controlled adder applies the addition only when the control qubit is in the state $|1\\rangle$:\n", "\n", "$$\n", "|\\mathrm{ctrl}\\rangle|a\\rangle|b\\rangle\n", "\\longmapsto\n", "|\\mathrm{ctrl}\\rangle|a\\rangle\n", "\\left|(b+\\mathrm{ctrl} \\cdot a)\\bmod 2^n\\right\\rangle.\n", "$$\n", "\n", "When $c=0$, the input registers are unchanged; when $c=1$, the circuit adds $a$ to $b$.\n", "\n", "Controlled ripple-carry addition has an efficient V-shaped implementation. The forward `MAJ` network computes the carries as usual. During the reverse pass, the carries are always uncomputed, but the operations that write the sum are conditioned on the control qubit. These modified reverse operations can be grouped into controlled `UMAJ` blocks. This avoids adding a control to every operation in the circuit [1].\n", "\n", "Controlled subtraction is obtained by reversing the corresponding controlled addition circuit:\n", "\n", "$$\n", "|\\mathrm{ctrl}\\rangle|a\\rangle|b\\rangle\n", "\\longmapsto\n", "|\\mathrm{ctrl}\\rangle|a\\rangle\n", "\\left|(b-\\mathrm{ctrl} \\cdot a)\\bmod 2^n\\right\\rangle.\n", "$$\n", "\n", "Controlled versions of the modular and carry-out Cuccaro and Gidney adders and subtractors are provided.\n", "\n", "[1] [Cuccaro *et al.*, “A new quantum ripple-carry addition circuit”](https://arxiv.org/abs/quant-ph/0410184).\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "15f1d719", "metadata": {}, "outputs": [], "source": [ "def run_controlled_adder_case(\n", " controlled_adder: GuppyFunctionDefinition,\n", " qubit_budget: int,\n", " n: int,\n", " a: int,\n", " b: int,\n", " ctrl_active: bool,\n", " ) -> dict:\n", " \"\"\"Run one controlled modular-addition case and return measured bits.\"\"\"\n", " a_bit_array = array(*int_to_bits(a, n))\n", " b_bit_array = array(*int_to_bits(b, n))\n", "\n", " @guppy\n", " @no_type_check\n", " def main() -> None:\n", " a_reg = qarray(n)\n", " b_reg = qarray(n)\n", " carry_out = qubit()\n", "\n", " apply_bitstring(a_reg, a_bit_array)\n", " apply_bitstring(b_reg, b_bit_array)\n", "\n", " ctrl = qubit()\n", " if ctrl_active:\n", " x(ctrl)\n", "\n", " controlled_adder(ctrl, a_reg, b_reg, carry_out)\n", "\n", " discard(ctrl)\n", "\n", " output(\"a_meas\", collect_measurements(measure_array(a_reg)))\n", " output(\"sum\", collect_measurements(measure_array(b_reg)))\n", " output(\"carry_out\", measure(carry_out).read())\n", "\n", "\n", " res = main.emulator(n_qubits=qubit_budget).run()\n", " return res.results[0].as_dict()" ] }, { "cell_type": "code", "execution_count": 7, "id": "84cc388c", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "ctrl=0, n=2, a=1, b=1 -> sum=1, carry=0, full sum=1 (expected 1)\n", "ctrl=1, n=2, a=1, b=1 -> sum=2, carry=0, full sum=2 (expected 2)\n", "ctrl=0, n=2, a=2, b=3 -> sum=3, carry=0, full sum=3 (expected 3)\n", "ctrl=1, n=2, a=2, b=3 -> sum=1, carry=1, full sum=5 (expected 5)\n", "ctrl=0, n=3, a=3, b=2 -> sum=2, carry=0, full sum=2 (expected 2)\n", "ctrl=1, n=3, a=3, b=2 -> sum=5, carry=0, full sum=5 (expected 5)\n", "ctrl=0, n=4, a=5, b=7 -> sum=7, carry=0, full sum=7 (expected 7)\n", "ctrl=1, n=4, a=5, b=7 -> sum=12, carry=0, full sum=12 (expected 12)\n", "Controlled adder checks passed.\n" ] } ], "source": [ "from guppyalgos.primitives.arithmetic import cntrl_adder_ripple_gidney_carry_out\n", "controlled_cases = [(2, 1, 1), (2, 2, 3), (3, 3, 2), (4, 5, 7)]\n", "\n", "for n, a, b in controlled_cases:\n", " for ctrl_active in (False, True):\n", " n_gidney_ancilla = n\n", " qubit_budget = 2 * n + 2 + n_gidney_ancilla\n", "\n", " result = run_controlled_adder_case(\n", " cntrl_adder_ripple_gidney_carry_out, qubit_budget, n, a, b, ctrl_active\n", " )\n", "\n", " # The operation computes b + ctrl * a.\n", " expected_full_sum = b + int(ctrl_active) * a\n", " expected_sum = expected_full_sum % (2**n)\n", " expected_carry = expected_full_sum >> n\n", "\n", " assert result[\"a_meas\"] == int_to_bits(a, n)\n", " assert result[\"sum\"] == int_to_bits(expected_sum, n)\n", " assert int(result[\"carry_out\"]) == expected_carry\n", "\n", " measured_sum = bits_to_int(result[\"sum\"])\n", " measured_carry = int(result[\"carry_out\"])\n", "\n", " # The carry and low n bits reconstruct the complete sum.\n", " reconstructed_sum = measured_sum + measured_carry * (2**n)\n", " assert reconstructed_sum == expected_full_sum\n", "\n", " print(\n", " f\"ctrl={int(ctrl_active)}, n={n}, a={a}, b={b} -> \"\n", " f\"sum={measured_sum}, carry={measured_carry}, \"\n", " f\"full sum={reconstructed_sum} (expected {expected_full_sum})\"\n", " )\n", "\n", "print(\"Controlled adder checks passed.\")" ] }, { "cell_type": "markdown", "id": "b120e07e", "metadata": {}, "source": [ "## Comparison\n", "\n", "For two unsigned $n$-bit integers, the comparator determines whether $b dict:\n", " \"\"\"Run one uncontrolled comparator case and return measured bits.\"\"\"\n", " a_bit_array = array(*int_to_bits(a, n))\n", " b_bit_array = array(*int_to_bits(b, n))\n", "\n", " @guppy\n", " @no_type_check\n", " def main() -> None:\n", " # Prepare |a>|b>|0>\n", " a_reg = qarray(n)\n", " b_reg = qarray(n)\n", " target = qubit()\n", "\n", " apply_bitstring(a_reg, a_bit_array)\n", " apply_bitstring(b_reg, b_bit_array)\n", "\n", " if swap_inputs:\n", " comparator_impl(b_reg, a_reg, target)\n", " else:\n", " comparator_impl(a_reg, b_reg, target)\n", "\n", " output(\"a_meas\", collect_measurements(measure_array(a_reg)))\n", " output(\"b_meas\", collect_measurements(measure_array(b_reg)))\n", " output(\"target\", measure(target).read())\n", "\n", "\n", " res = main.emulator(n_qubits=qubit_budget).run()\n", " return res.results[0].as_dict()" ] }, { "cell_type": "code", "execution_count": 9, "id": "c551aeaa", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n=2, a=1, b=1 -> b < a: 0 (expected 0)\n", "n=2, a=2, b=3 -> b < a: 0 (expected 0)\n", "n=3, a=3, b=2 -> b < a: 1 (expected 1)\n", "n=4, a=5, b=7 -> b < a: 0 (expected 0)\n", "Comparator checks passed.\n" ] } ], "source": [ "from guppyalgos.primitives.arithmetic.comparator import comparator_vandaele\n", "\n", "uncontrolled_cases = [(2, 1, 1), (2, 2, 3), (3, 3, 2), (4, 5, 7)]\n", "\n", "for n, a, b in uncontrolled_cases:\n", " n_vandaele_ancilla = 0\n", " qubit_budget = 2 * n + 1 + n_vandaele_ancilla\n", " swap_inputs = True\n", " result = run_comparator_case(\n", " comparator_vandaele(n), qubit_budget, n, a, b, swap_inputs=swap_inputs\n", " )\n", "\n", " expected_sign = int(b < a)\n", "\n", " assert result[\"a_meas\"] == int_to_bits(a, n)\n", " assert result[\"b_meas\"] == int_to_bits(b, n)\n", " assert int(result[\"target\"]) == expected_sign\n", "\n", " measured_sign = int(result[\"target\"])\n", "\n", " print(\n", " f\"n={n}, a={a}, b={b} -> \"\n", " f\"b < a: {measured_sign} \"\n", " f\"(expected {expected_sign})\"\n", " )\n", "\n", "print(\"Comparator checks passed.\")" ] }, { "cell_type": "markdown", "id": "fbaf19f8", "metadata": {}, "source": [ "## Incrementation\n", "\n", "An $n$-bit incrementer adds one to a quantum register modulo $2^n$:\n", "\n", "$$\n", "|x\\rangle\n", "\\longmapsto\n", "|(x+1)\\bmod 2^n\\rangle.\n", "$$\n", "\n", "The implementation must flip bit $i$ precisely when all less-significant bits are $1$. Consequently, incrementing $11\\ldots1$ wraps the register around to $00\\ldots0$.\n", "\n", "The following incrementer constructions are provided:\n", "\n", "* **Linear-depth incrementer:** Bit $x_j$ is flipped exactly when all lower-order bits are $1$. The carry into bit $j$ is therefore\n", "\n", " $$\n", " c_j=x_0x_1\\cdots x_{j-1}=c_{j-1}x_{j-1}.\n", " $$\n", "\n", " These prefix-AND carries are computed and then uncomputed using a V-shaped staircase of temporary logical-AND operations, giving $\\mathcal{O}(n)$ gate count, depth, and ancilla usage. `linear_depth_incrementer_1` acts on the full register, whereas `linear_depth_incrementer_2` accepts an upper bound on the value currently held in the register, `max_value`, and omits higher-order bits that cannot be affected by the increment.\n", "\n", "* **Conditionally clean ancilla incrementer:** `cca_incrementer` implements the linear-depth construction from Section 6.2 of [Khattar and Gidney, “Rise of conditionally clean ancillae for efficient quantum circuit constructions”](https://arxiv.org/abs/2407.17966). It computes and consumes the prefix ANDs that determine which bits must be flipped. The construction uses $3n+\\mathcal{O}(1)$ Toffoli-type operations, has $\\mathcal{O}(n)$ depth, and requires $\\mathcal{O}(\\log_2^* n)$ clean ancilla qubits.\n", "\n", "Controlled versions of both incrementers are also provided. They implement\n", "\n", "$$\n", "|\\mathrm{ctrl}\\rangle|x\\rangle\n", "\\longmapsto\n", "|\\mathrm{ctrl}\\rangle|(x+\\mathrm{ctrl})\\bmod 2^n\\rangle.\n", "$$\n", "\n", "A controlled incrementer on an $n$-bit register can be expressed as an incrementer on the combined $(n+1)$-bit little-endian register in which the control is the least-significant bit, followed by an $X$ gate on the control. The final $X$ restores the control while leaving the target register incremented exactly when the original control was $1$." ] }, { "cell_type": "code", "execution_count": 10, "id": "e9570ff2", "metadata": {}, "outputs": [], "source": [ "def run_cca_incrementer_case(\n", " incrementer: GuppyFunctionDefinition,\n", " qubit_budget: int,\n", " n: int,\n", " value: int,\n", " ) -> dict:\n", " \"\"\"Increment an n-bit register modulo 2**n and return its measurement.\"\"\"\n", " value_bit_array = array(*int_to_bits(value, n))\n", "\n", " @guppy\n", " @no_type_check\n", " def main() -> None:\n", " register = qarray(n)\n", " apply_bitstring(register, value_bit_array)\n", "\n", " incrementer(register)\n", "\n", " output(\n", " \"incremented\",\n", " collect_measurements(measure_array(register)),\n", " )\n", "\n", " # The CCA construction uses O(log*(n)) clean ancillas.\n", " # Allocating up to n additional qubits is a conservative bound.\n", " result = main.emulator(n_qubits=qubit_budget).run()\n", " return result.results[0].as_dict()" ] }, { "cell_type": "code", "execution_count": 11, "id": "5ba7e657", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n=1, value=0 -> incremented=1 (expected 1)\n", "n=1, value=1 -> incremented=0 (expected 0)\n", "n=3, value=3 -> incremented=4 (expected 4)\n", "n=4, value=7 -> incremented=8 (expected 8)\n", "n=4, value=15 -> incremented=0 (expected 0)\n", "Incrementer checks passed.\n" ] } ], "source": [ "from guppyalgos.primitives.arithmetic.incrementer.incrementer_cca import cca_incrementer\n", "\n", "incrementer_cases = [(1, 0), (1, 1), (3, 3), (4, 7), (4, 15)]\n", "\n", "for n, value in incrementer_cases:\n", " qubit_budget = 2 * n\n", " result = run_cca_incrementer_case(cca_incrementer, qubit_budget, n, value)\n", "\n", " expected = (value + 1) % (2**n)\n", " expected_bits = int_to_bits(expected, n)\n", "\n", " assert result[\"incremented\"] == expected_bits\n", "\n", " measured = bits_to_int(result[\"incremented\"])\n", " print(\n", " f\"n={n}, value={value} -> \"\n", " f\"incremented={measured} (expected {expected})\"\n", " )\n", "\n", "print(\"Incrementer checks passed.\")" ] }, { "cell_type": "markdown", "id": "2f09e0a4", "metadata": {}, "source": [ "## Multiplication\n", "\n", "`multiplier_ripple_gidney_mod` implements textbook out-of-place multiplication modulo $2^n$ using a sequence of shifted, controlled Gidney additions. For little-endian $n$-bit registers $a$ and $b$, it performs\n", "\n", "$$\n", "|a\\rangle|b\\rangle|p\\rangle\n", "\\longmapsto\n", "|a\\rangle|b\\rangle\n", "|(p+ab)\\bmod 2^n\\rangle.\n", "$$\n", "\n", "When the accumulator $p$ is initialized to zero, it contains $ab\\bmod 2^n$ after the operation.\n", "\n", "Writing the multiplier as\n", "\n", "$$\n", "b=\\sum_{i=0}^{n-1}b_i2^i\n", "$$\n", "\n", "gives\n", "\n", "$$\n", "ab=\\sum_{i=0}^{n-1}b_i(a\\ll i).\n", "$$\n", "\n", "The circuit therefore iterates over the bits $b_i$. At step $i$, it constructs the partial product $b_i(a\\ll i)$, adds it into $p$ modulo $2^n$, and then uncomputes the temporary partial-product register. Equivalently, bit $j$ of this partial product is\n", "\n", "$$\n", "b_i a_{j-i}\n", "$$\n", "\n", "when $j\\geq i$, and zero otherwise. Bits shifted beyond the $n$-bit accumulator are discarded by the modular arithmetic.\n", "\n", "The following variants are provided:\n", "\n", "* **Uncontrolled multiplication:** `multiplier_ripple_gidney_mod` adds $(a\\ll i)$ into $p$ whenever $b_i=1$.\n", "\n", "* **Controlled multiplication:** `controlled_multiplier_ripple_gidney_mod` performs the same multiplication only when an additional control qubit $c$ is set:\n", "\n", " $$\n", " |c\\rangle|a\\rangle|b\\rangle|p\\rangle\n", " \\longmapsto\n", " |c\\rangle|a\\rangle|b\\rangle\n", " |(p+cab)\\bmod 2^n\\rangle.\n", " $$\n", "\n", "At any one step, the uncontrolled construction uses:\n", "\n", "* $n$ qubits for $a$;\n", "* $n$ qubits for $b$;\n", "* $n$ qubits for the accumulator $p$;\n", "* up to $n$ temporary qubits for the current partial product; and\n", "* the ancilla qubits required by the Gidney adder.\n", "\n", "The temporary partial-product and adder work qubits are uncomputed before they are discarded. The controlled variant additionally requires the global control qubit.\n", "\n", "This construction follows the standard reversible shift-and-add decomposition described by [Vedral, Barenco, and Ekert, “Quantum networks for elementary arithmetic operations”](https://doi.org/10.1103/PhysRevA.54.147)." ] }, { "cell_type": "code", "execution_count": 12, "id": "f61c9498", "metadata": {}, "outputs": [], "source": [ "def run_multiplier_case(\n", " multiplier: GuppyFunctionDefinition,\n", " qubit_budget: int,\n", " n: int,\n", " a: int,\n", " b: int,\n", ") -> dict:\n", " \"\"\"Multiply two n-bit values modulo 2**n and return the measurements.\"\"\"\n", " a_bit_array = array(*int_to_bits(a, n))\n", " b_bit_array = array(*int_to_bits(b, n))\n", "\n", " @guppy\n", " @no_type_check\n", " def main() -> None:\n", " a_reg = qarray(n)\n", " b_reg = qarray(n)\n", " product_reg = qarray(n)\n", "\n", " apply_bitstring(a_reg, a_bit_array)\n", " apply_bitstring(b_reg, b_bit_array)\n", "\n", " multiplier(a_reg, b_reg, product_reg)\n", "\n", " output(\"a_meas\", collect_measurements(measure_array(a_reg)))\n", " output(\"b_meas\", collect_measurements(measure_array(b_reg)))\n", " output(\"product\", collect_measurements(measure_array(product_reg)))\n", "\n", " result = main.emulator(n_qubits=qubit_budget).run()\n", " return result.results[0].as_dict()" ] }, { "cell_type": "code", "execution_count": 13, "id": "ecb61476", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n=2, a=1, b=1 -> product=1 (expected 1)\n", "n=2, a=2, b=3 -> product=2 (expected 2)\n", "n=3, a=3, b=2 -> product=6 (expected 6)\n", "n=4, a=5, b=7 -> product=3 (expected 3)\n", "Multiplier checks passed.\n" ] } ], "source": [ "from guppyalgos.primitives.arithmetic import multiplier_ripple_gidney_mod\n", "\n", "multiplier_cases = [(2, 1, 1), (2, 2, 3), (3, 3, 2), (4, 5, 7)]\n", "\n", "for n, a, b in multiplier_cases:\n", " qubit_budget = 5 * n - 1\n", " result = run_multiplier_case(multiplier_ripple_gidney_mod, qubit_budget, n, a, b)\n", "\n", " expected_product = (a * b) % (2**n)\n", " expected_product_bits = int_to_bits(expected_product, n)\n", "\n", " # Both input registers are preserved.\n", " assert result[\"a_meas\"] == int_to_bits(a, n)\n", " assert result[\"b_meas\"] == int_to_bits(b, n)\n", "\n", " # The output register contains a * b modulo 2**n.\n", " assert result[\"product\"] == expected_product_bits\n", "\n", " measured_product = bits_to_int(result[\"product\"])\n", " print(\n", " f\"n={n}, a={a}, b={b} -> \"\n", " f\"product={measured_product} \"\n", " f\"(expected {expected_product})\"\n", " )\n", "\n", "print(\"Multiplier checks passed.\")" ] }, { "cell_type": "markdown", "id": "25969eaa", "metadata": {}, "source": [ "## Exponentiation\n", "\n", "For a classical base $b$, an $m$-bit quantum exponent $x$, and an $n$-bit output register $a$, `exponentiator_ripple_gidney_mod` performs\n", "\n", "$$\n", "|x\\rangle|a\\rangle\n", "\\longmapsto\n", "|x\\rangle\n", "|a\\,b^x\\bmod 2^n\\rangle.\n", "$$\n", "\n", "When the output register is initialized to $|1\\rangle$, it contains $b^x\\bmod 2^n$ after the operation.\n", "\n", "Writing the little-endian exponent as\n", "\n", "$$\n", "x=\\sum_{i=0}^{m-1}x_i2^i,\n", "$$\n", "\n", "we have\n", "\n", "$$\n", "b^x\\bmod 2^n\n", "=\n", "\\prod_{i=0}^{m-1}\n", "\\left(b^{2^i}\\bmod 2^n\\right)^{x_i}.\n", "$$\n", "\n", "The constants\n", "\n", "$$\n", "b_i=b^{2^i}\\bmod 2^n\n", "$$\n", "\n", "are computed classically at compile time.\n", "\n", "For each exponent bit $x_i$, the circuit applies\n", "\n", "```python\n", "controlled_multiplier_ripple_gidney_mod_in_place(\n", " exponent_reg[i], output_reg, b_i\n", ")\n", "```\n", "\n", "This multiplies the output register by $b_i$ when $x_i=1$ and leaves it unchanged when $x_i=0$. The complete exponentiator therefore consists of $m$ controlled in-place multipliers, one controlled by each qubit of the exponent register.\n", "\n", "The base must be odd because multiplication by $b$ modulo $2^n$ is reversible in place only when $b$ is coprime to $2^n$. This condition is equivalent to requiring $b$ to be odd.\n" ] }, { "cell_type": "code", "execution_count": 14, "id": "3bae38c4", "metadata": {}, "outputs": [], "source": [ "def run_exponentiator_case(\n", " exponentiator: GuppyFunctionDefinition,\n", " qubit_budget: int,\n", " n: int,\n", " base: int,\n", " exponent: int,\n", ") -> dict:\n", " \"\"\"Compute base**exponent modulo 2**n and return the measurements.\"\"\"\n", " exponent_reg_size = max(1, exponent.bit_length())\n", "\n", " exponent_bit_array = array(*int_to_bits(exponent, exponent_reg_size))\n", " initial_output_bit_array = array(*int_to_bits(1, n))\n", "\n", " exponentiator_impl = exponentiator\n", "\n", " @guppy\n", " @no_type_check\n", " def main() -> None:\n", " exponent_reg = qarray(exponent_reg_size)\n", " output_reg = qarray(n)\n", "\n", " apply_bitstring(exponent_reg, exponent_bit_array)\n", " apply_bitstring(output_reg, initial_output_bit_array)\n", "\n", " exponentiator_impl(exponent_reg, output_reg, base)\n", "\n", " output(\"exponent_meas\", collect_measurements(measure_array(exponent_reg)))\n", " output(\"power\", collect_measurements(measure_array(output_reg)))\n", "\n", " result = main.emulator(n_qubits=qubit_budget).run()\n", "\n", " return result.results[0].as_dict()" ] }, { "cell_type": "code", "execution_count": 15, "id": "5a540c71", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "n=3, base=3, exponent=0 -> power=1 (expected 1)\n", "n=3, base=3, exponent=1 -> power=3 (expected 3)\n", "n=3, base=3, exponent=2 -> power=1 (expected 1)\n", "n=4, base=3, exponent=3 -> power=11 (expected 11)\n", "Exponentiator checks passed.\n" ] } ], "source": [ "from guppyalgos.primitives.arithmetic import exponentiator_ripple_gidney_mod\n", "\n", "exponentiator_cases = [(3, 3, 0), (3, 3, 1), (3, 3, 2), (4, 3, 3)]\n", "\n", "for n, base, exponent in exponentiator_cases:\n", " exponent_reg_size = max(1, exponent.bit_length())\n", " expected_exponent_bits = int_to_bits(exponent, exponent_reg_size)\n", "\n", " expected_power = pow(base, exponent, 2**n)\n", " expected_power_bits = int_to_bits(expected_power, n)\n", "\n", " qubit_budget = exponent_reg_size + 5 * n\n", " result = run_exponentiator_case(exponentiator_ripple_gidney_mod, qubit_budget, n, base, exponent)\n", "\n", " # The exponent register is preserved.\n", " assert result[\"exponent_meas\"] == expected_exponent_bits\n", "\n", " # The output contains base**exponent modulo 2**n.\n", " assert result[\"power\"] == expected_power_bits\n", "\n", " measured_power = bits_to_int(result[\"power\"])\n", " print(\n", " f\"n={n}, base={base}, exponent={exponent} -> \"\n", " f\"power={measured_power} \"\n", " f\"(expected {expected_power})\"\n", " )\n", "\n", "print(\"Exponentiator checks passed.\")" ] }, { "cell_type": "code", "execution_count": null, "id": "69bb3566", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "guppyalgos (3.13.12)", "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.13.12" } }, "nbformat": 4, "nbformat_minor": 5 }