Arithmetic Examples

Download Notebook - arithmetic_demo.ipynb

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.

from typing import no_type_check
from collections.abc import Callable

from guppylang import guppy
from guppylang.std.builtins import array, output
from guppylang.std.quantum import qubit, discard, measure_array, measure, collect_measurements, x
from guppyalgos.utils import int_to_bits, bits_to_int, apply_bitstring, qarray
from guppylang.defs import GuppyFunctionDefinition

Addition

The adder is a fundamental building block underlying many more sophisticated arithmetic primitives.

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:

\[ |a\rangle|b\rangle \longmapsto |a\rangle|(a+b)\bmod 2^n\rangle. \]

Non-modular addition retains the overflow in a separate carry qubit \(z\):

\[ |a\rangle|b\rangle|z\rangle \longmapsto |a\rangle|(a+b)\bmod 2^n\rangle \left|z\oplus\left\lfloor\frac{a+b}{2^n}\right\rfloor\right\rangle. \]

Together, the updated \(b\) register and the carry qubit represent the complete \((n+1)\)-bit sum. Here, \(\oplus\) denotes XOR.

Ripple-carry adders

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.

Together, the two passes implement the same bitwise recurrence as schoolbook binary addition. For example:

      1111
    + 0110
     ------
     10101
     ------
     1110   <- carries

The carries are listed from the most-significant input column to the least-significant input column. The initial input carry is 0.

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:

  • 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”. 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 guppyalgos.primitives.subroutines.ladders, and the 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. These depth–space trade-offs are discussed by Remaud, “Quantum adders: on the structural link between the ripple-carry and carry-lookahead techniques”.

  • 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”.

Both adders are available in modular and carry-out variants:

  • adder_ripple_gidney_mod and adder_ripple_cuccaro_mod perform addition modulo \(2^n\), discarding any overflow.

  • 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.

def run_adder_case(
    adder: GuppyFunctionDefinition,
    qubit_budget: int,
    n: int,
    a: int,
    b: int,
) -> dict:
    """Run one uncontrolled non-modular addition case and return measured bits."""
    a_bit_array = array(*int_to_bits(a, n))
    b_bit_array = array(*int_to_bits(b, n))

    @guppy
    @no_type_check
    def main() -> None:
        # Prepare |a>|b>|0>
        a_reg = qarray(n)
        b_reg = qarray(n)
        carry_out = qubit()

        apply_bitstring(a_reg, a_bit_array)
        apply_bitstring(b_reg, b_bit_array)

        # Compute a + b. The lower n bits are written to b_reg,
        # and the overflow bit is written to carry_out.
        adder(a_reg, b_reg, carry_out)

        output("a_meas", collect_measurements(measure_array(a_reg)))
        output("sum", collect_measurements(measure_array(b_reg)))
        output("carry_out", measure(carry_out).read())


    res = main.emulator(n_qubits=qubit_budget).run()
    return res.results[0].as_dict()

from guppyalgos.primitives.arithmetic import adder_ripple_gidney_carry_out

uncontrolled_cases = [(2, 1, 1), (2, 2, 3), (3, 3, 2), (4, 5, 7)]

for n, a, b in uncontrolled_cases:
    n_gidney_ancilla = n - 1
    qubit_budget = 2 * n + 1 + n_gidney_ancilla
    result = run_adder_case(adder_ripple_gidney_carry_out, qubit_budget, n, a, b)

    full_sum = a + b
    expected_sum = full_sum % (2**n)
    expected_carry = full_sum >> n

    assert result["a_meas"] == int_to_bits(a, n)
    assert result["sum"] == int_to_bits(expected_sum, n)
    assert int(result["carry_out"]) == expected_carry

    measured_sum = bits_to_int(result["sum"])
    measured_carry = int(result["carry_out"])

    # The carry and low n bits reconstruct the complete sum.
    reconstructed_sum = measured_sum + measured_carry * (2**n)
    assert reconstructed_sum == full_sum

    print(
        f"n={n}, a={a}, b={b} -> "
        f"sum={measured_sum}, carry={measured_carry}, "
        f"full sum={reconstructed_sum} (expected {full_sum})"
    )

print("Uncontrolled adder checks passed.")

n=2, a=1, b=1 -> sum=2, carry=0, full sum=2 (expected 2)
n=2, a=2, b=3 -> sum=1, carry=1, full sum=5 (expected 5)
n=3, a=3, b=2 -> sum=5, carry=0, full sum=5 (expected 5)
n=4, a=5, b=7 -> sum=12, carry=0, full sum=12 (expected 12)
Uncontrolled adder checks passed.

Subtraction

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\).

Both subtractors are available in modular and borrow-out variants:

  • subtractor_ripple_gidney_mod and subtractor_ripple_cuccaro_mod perform subtraction modulo \(2^n\):

\[ |a\rangle|b\rangle \longmapsto |a\rangle|(b-a)\bmod 2^n\rangle. \]

Any underflow is discarded.

  • subtractor_ripple_gidney_carry_out and subtractor_ripple_cuccaro_carry_out record underflow in a separate qubit:

\[ |a\rangle|b\rangle|z\rangle \longmapsto |a\rangle|(b-a)\bmod 2^n\rangle |z\oplus(b<a)\rangle, \]

where \((b<a)\) is \(1\) when the subtraction requires a borrow and \(0\) otherwise.

def run_subtractor_case(
    subtractor: GuppyFunctionDefinition,
    qubit_budget: int,
    n: int,
    a: int,
    b: int,
) -> dict:
    """Run one uncontrolled non-modular addition case and return measured bits."""
    a_bit_array = array(*int_to_bits(a, n))
    b_bit_array = array(*int_to_bits(b, n))

    @guppy
    @no_type_check
    def main() -> None:
        # Prepare |a>|b>|0>
        a_reg = qarray(n)
        b_reg = qarray(n)
        borrow_out = qubit()

        apply_bitstring(a_reg, a_bit_array)
        apply_bitstring(b_reg, b_bit_array)

        # Compute b - a. The lower n bits are written to b_reg,
        # and the overflow bit is written to borrow_out.
        subtractor(a_reg, b_reg, borrow_out)

        output("a_meas", collect_measurements(measure_array(a_reg)))
        output("diff", collect_measurements(measure_array(b_reg)))
        output("borrow_out", measure(borrow_out).read())

    res = main.emulator(n_qubits=qubit_budget).run()
    return res.results[0].as_dict()

from guppyalgos.primitives.arithmetic import subtractor_ripple_gidney_carry_out

uncontrolled_cases = [(2, 1, 1), (2, 2, 3), (3, 3, 2), (4, 5, 7)]

for n, a, b in uncontrolled_cases:
    n_gidney_ancilla = n - 1
    qubit_budget = 2 * n + 1 + n_gidney_ancilla

    result = run_subtractor_case(subtractor_ripple_gidney_carry_out, qubit_budget, n, a, b)

    full_diff = b - a
    expected_diff = full_diff % (2**n)
    expected_borrow = int(b < a)

    assert result["a_meas"] == int_to_bits(a, n)
    assert result["diff"] == int_to_bits(expected_diff, n)
    assert int(result["borrow_out"]) == expected_borrow

    measured_diff = bits_to_int(result["diff"])
    measured_borrow = int(result["borrow_out"])

    # The borrow and low n bits reconstruct the complete difference.
    reconstructed_diff = expected_diff - expected_borrow * (2**n)
    assert reconstructed_diff == full_diff

    print(
        f"n={n}, a={a}, b={b} -> "
        f"diff={measured_diff}, borrow={measured_borrow}, "
        f"full diff={reconstructed_diff} (expected {full_diff})"
    )


print("Uncontrolled subtractor checks passed.")

n=2, a=1, b=1 -> diff=0, borrow=0, full diff=0 (expected 0)
n=2, a=2, b=3 -> diff=1, borrow=0, full diff=1 (expected 1)
n=3, a=3, b=2 -> diff=7, borrow=1, full diff=-1 (expected -1)
n=4, a=5, b=7 -> diff=2, borrow=0, full diff=2 (expected 2)
Uncontrolled subtractor checks passed.

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.

Controlled addition and subtraction

A controlled adder applies the addition only when the control qubit is in the state \(|1\rangle\):

\[ |\mathrm{ctrl}\rangle|a\rangle|b\rangle \longmapsto |\mathrm{ctrl}\rangle|a\rangle \left|(b+\mathrm{ctrl} \cdot a)\bmod 2^n\right\rangle. \]

When \(c=0\), the input registers are unchanged; when \(c=1\), the circuit adds \(a\) to \(b\).

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].

Controlled subtraction is obtained by reversing the corresponding controlled addition circuit:

\[ |\mathrm{ctrl}\rangle|a\rangle|b\rangle \longmapsto |\mathrm{ctrl}\rangle|a\rangle \left|(b-\mathrm{ctrl} \cdot a)\bmod 2^n\right\rangle. \]

Controlled versions of the modular and carry-out Cuccaro and Gidney adders and subtractors are provided.

[1] Cuccaro et al., “A new quantum ripple-carry addition circuit”.

def run_controlled_adder_case(
    controlled_adder: GuppyFunctionDefinition,
    qubit_budget: int,
    n: int,
    a: int,
    b: int,
    ctrl_active: bool,
 ) -> dict:
    """Run one controlled modular-addition case and return measured bits."""
    a_bit_array = array(*int_to_bits(a, n))
    b_bit_array = array(*int_to_bits(b, n))

    @guppy
    @no_type_check
    def main() -> None:
        a_reg = qarray(n)
        b_reg = qarray(n)
        carry_out = qubit()

        apply_bitstring(a_reg, a_bit_array)
        apply_bitstring(b_reg, b_bit_array)

        ctrl = qubit()
        if ctrl_active:
            x(ctrl)

        controlled_adder(ctrl, a_reg, b_reg, carry_out)

        discard(ctrl)

        output("a_meas", collect_measurements(measure_array(a_reg)))
        output("sum", collect_measurements(measure_array(b_reg)))
        output("carry_out", measure(carry_out).read())


    res = main.emulator(n_qubits=qubit_budget).run()
    return res.results[0].as_dict()

from guppyalgos.primitives.arithmetic import cntrl_adder_ripple_gidney_carry_out
controlled_cases = [(2, 1, 1), (2, 2, 3), (3, 3, 2), (4, 5, 7)]

for n, a, b in controlled_cases:
    for ctrl_active in (False, True):
        n_gidney_ancilla = n
        qubit_budget = 2 * n + 2 + n_gidney_ancilla

        result = run_controlled_adder_case(
            cntrl_adder_ripple_gidney_carry_out, qubit_budget, n, a, b, ctrl_active
        )

        # The operation computes b + ctrl * a.
        expected_full_sum = b + int(ctrl_active) * a
        expected_sum = expected_full_sum % (2**n)
        expected_carry = expected_full_sum >> n

        assert result["a_meas"] == int_to_bits(a, n)
        assert result["sum"] == int_to_bits(expected_sum, n)
        assert int(result["carry_out"]) == expected_carry

        measured_sum = bits_to_int(result["sum"])
        measured_carry = int(result["carry_out"])

        # The carry and low n bits reconstruct the complete sum.
        reconstructed_sum = measured_sum + measured_carry * (2**n)
        assert reconstructed_sum == expected_full_sum

        print(
            f"ctrl={int(ctrl_active)}, n={n}, a={a}, b={b} -> "
            f"sum={measured_sum}, carry={measured_carry}, "
            f"full sum={reconstructed_sum} (expected {expected_full_sum})"
        )

print("Controlled adder checks passed.")

ctrl=0, n=2, a=1, b=1 -> sum=1, carry=0, full sum=1 (expected 1)
ctrl=1, n=2, a=1, b=1 -> sum=2, carry=0, full sum=2 (expected 2)
ctrl=0, n=2, a=2, b=3 -> sum=3, carry=0, full sum=3 (expected 3)
ctrl=1, n=2, a=2, b=3 -> sum=1, carry=1, full sum=5 (expected 5)
ctrl=0, n=3, a=3, b=2 -> sum=2, carry=0, full sum=2 (expected 2)
ctrl=1, n=3, a=3, b=2 -> sum=5, carry=0, full sum=5 (expected 5)
ctrl=0, n=4, a=5, b=7 -> sum=7, carry=0, full sum=7 (expected 7)
ctrl=1, n=4, a=5, b=7 -> sum=12, carry=0, full sum=12 (expected 12)
Controlled adder checks passed.

Comparison

For two unsigned \(n\)-bit integers, the comparator determines whether \(b<a\) and XORs the result into a target qubit \(z\):

\[ |a\rangle|b\rangle|z\rangle \longmapsto |a\rangle|b\rangle |z\oplus(b<a)\rangle, \]

where \((b<a)\) is \(1\) when the comparison is true and \(0\) otherwise. Both input registers are preserved.

Ripple-carry comparators

A ripple-carry comparator reuses the carry-propagation network from the corresponding non-modular subtractor. It propagates the carries or borrows from the least-significant bit to the most-significant bit without writing the difference. The final borrow bit indicates whether \(b-a\) underflows and therefore whether \(b<a\).

After XORing this result into \(z\), the carry-propagation network is applied in reverse to restore the input registers and return any ancilla qubits to their initial states.

comparator_ripple_cuccaro implements the Cuccaro-based ripple-carry comparator. It has \(\Theta(n)\) gate count and depth and requires one clean ancilla qubit.

comparator_ripple_cuccaro implements the Cuccaro-based comparator. Its resource requirements therefore depend on the selected ladder implementations, as with the Cuccaro adder. Using the naive ladders gives \(\Theta(n)\) gate count and depth with one clean ancilla qubit, while logarithmic-depth ladders reduce the overall depth to \(\mathcal{O}(\log n)\) at the cost of \(\mathcal{O}(n)\) ancilla qubits.

Ancilla-free logarithmic-depth comparator

comparator_vandaele implements the quantum–quantum comparator described in Section 4.1 of Vandaele, “Asymptotically Optimal Quantum Circuits for Comparators and Incrementers”. Rather than propagating carries sequentially, the construction recursively decomposes the underlying V-shaped ladder operator.

The comparator uses \(\Theta(n)\) gates, has \(\Theta(\log n)\) circuit depth, and requires no ancilla qubits. These bounds are asymptotically optimal in gate count, depth, and qubit count.

def run_comparator_case(
    comparator_impl: GuppyFunctionDefinition,
    qubit_budget: int,
    n: int,
    a: int,
    b: int,
    *,
    swap_inputs: bool = False,
) -> dict:
    """Run one uncontrolled comparator case and return measured bits."""
    a_bit_array = array(*int_to_bits(a, n))
    b_bit_array = array(*int_to_bits(b, n))

    @guppy
    @no_type_check
    def main() -> None:
        # Prepare |a>|b>|0>
        a_reg = qarray(n)
        b_reg = qarray(n)
        target = qubit()

        apply_bitstring(a_reg, a_bit_array)
        apply_bitstring(b_reg, b_bit_array)

        if swap_inputs:
            comparator_impl(b_reg, a_reg, target)
        else:
            comparator_impl(a_reg, b_reg, target)

        output("a_meas", collect_measurements(measure_array(a_reg)))
        output("b_meas", collect_measurements(measure_array(b_reg)))
        output("target", measure(target).read())


    res = main.emulator(n_qubits=qubit_budget).run()
    return res.results[0].as_dict()

from guppyalgos.primitives.arithmetic.comparator import comparator_vandaele

uncontrolled_cases = [(2, 1, 1), (2, 2, 3), (3, 3, 2), (4, 5, 7)]

for n, a, b in uncontrolled_cases:
    n_vandaele_ancilla = 0
    qubit_budget = 2 * n + 1 + n_vandaele_ancilla
    swap_inputs = True
    result = run_comparator_case(
        comparator_vandaele(n), qubit_budget, n, a, b, swap_inputs=swap_inputs
    )

    expected_sign = int(b < a)

    assert result["a_meas"] == int_to_bits(a, n)
    assert result["b_meas"] == int_to_bits(b, n)
    assert int(result["target"]) == expected_sign

    measured_sign = int(result["target"])

    print(
        f"n={n}, a={a}, b={b} -> "
        f"b < a: {measured_sign} "
        f"(expected {expected_sign})"
    )

print("Comparator checks passed.")

n=2, a=1, b=1 -> b < a: 0 (expected 0)
n=2, a=2, b=3 -> b < a: 0 (expected 0)
n=3, a=3, b=2 -> b < a: 1 (expected 1)
n=4, a=5, b=7 -> b < a: 0 (expected 0)
Comparator checks passed.

Incrementation

An \(n\)-bit incrementer adds one to a quantum register modulo \(2^n\):

\[ |x\rangle \longmapsto |(x+1)\bmod 2^n\rangle. \]

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\).

The following incrementer constructions are provided:

  • Linear-depth incrementer: Bit \(x_j\) is flipped exactly when all lower-order bits are \(1\). The carry into bit \(j\) is therefore

    \[ c_j=x_0x_1\cdots x_{j-1}=c_{j-1}x_{j-1}. \]

    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.

  • 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”. 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.

Controlled versions of both incrementers are also provided. They implement

\[ |\mathrm{ctrl}\rangle|x\rangle \longmapsto |\mathrm{ctrl}\rangle|(x+\mathrm{ctrl})\bmod 2^n\rangle. \]

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\).

def run_cca_incrementer_case(
    incrementer: GuppyFunctionDefinition,
    qubit_budget: int,
    n: int,
    value: int,
    ) -> dict:
    """Increment an n-bit register modulo 2**n and return its measurement."""
    value_bit_array = array(*int_to_bits(value, n))

    @guppy
    @no_type_check
    def main() -> None:
        register = qarray(n)
        apply_bitstring(register, value_bit_array)

        incrementer(register)

        output(
            "incremented",
            collect_measurements(measure_array(register)),
        )

    # The CCA construction uses O(log*(n)) clean ancillas.
    # Allocating up to n additional qubits is a conservative bound.
    result = main.emulator(n_qubits=qubit_budget).run()
    return result.results[0].as_dict()

from guppyalgos.primitives.arithmetic.incrementer.incrementer_cca import cca_incrementer

incrementer_cases = [(1, 0), (1, 1), (3, 3), (4, 7), (4, 15)]

for n, value in incrementer_cases:
    qubit_budget = 2 * n
    result = run_cca_incrementer_case(cca_incrementer, qubit_budget, n, value)

    expected = (value + 1) % (2**n)
    expected_bits = int_to_bits(expected, n)

    assert result["incremented"] == expected_bits

    measured = bits_to_int(result["incremented"])
    print(
        f"n={n}, value={value} -> "
        f"incremented={measured} (expected {expected})"
    )

print("Incrementer checks passed.")

n=1, value=0 -> incremented=1 (expected 1)
n=1, value=1 -> incremented=0 (expected 0)
n=3, value=3 -> incremented=4 (expected 4)
n=4, value=7 -> incremented=8 (expected 8)
n=4, value=15 -> incremented=0 (expected 0)
Incrementer checks passed.

Multiplication

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

\[ |a\rangle|b\rangle|p\rangle \longmapsto |a\rangle|b\rangle |(p+ab)\bmod 2^n\rangle. \]

When the accumulator \(p\) is initialized to zero, it contains \(ab\bmod 2^n\) after the operation.

Writing the multiplier as

\[ b=\sum_{i=0}^{n-1}b_i2^i \]

gives

\[ ab=\sum_{i=0}^{n-1}b_i(a\ll i). \]

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

\[ b_i a_{j-i} \]

when \(j\geq i\), and zero otherwise. Bits shifted beyond the \(n\)-bit accumulator are discarded by the modular arithmetic.

The following variants are provided:

  • Uncontrolled multiplication: multiplier_ripple_gidney_mod adds \((a\ll i)\) into \(p\) whenever \(b_i=1\).

  • Controlled multiplication: controlled_multiplier_ripple_gidney_mod performs the same multiplication only when an additional control qubit \(c\) is set:

    \[ |c\rangle|a\rangle|b\rangle|p\rangle \longmapsto |c\rangle|a\rangle|b\rangle |(p+cab)\bmod 2^n\rangle. \]

At any one step, the uncontrolled construction uses:

  • \(n\) qubits for \(a\);

  • \(n\) qubits for \(b\);

  • \(n\) qubits for the accumulator \(p\);

  • up to \(n\) temporary qubits for the current partial product; and

  • the ancilla qubits required by the Gidney adder.

The temporary partial-product and adder work qubits are uncomputed before they are discarded. The controlled variant additionally requires the global control qubit.

This construction follows the standard reversible shift-and-add decomposition described by Vedral, Barenco, and Ekert, “Quantum networks for elementary arithmetic operations”.

def run_multiplier_case(
    multiplier: GuppyFunctionDefinition,
    qubit_budget: int,
    n: int,
    a: int,
    b: int,
) -> dict:
    """Multiply two n-bit values modulo 2**n and return the measurements."""
    a_bit_array = array(*int_to_bits(a, n))
    b_bit_array = array(*int_to_bits(b, n))

    @guppy
    @no_type_check
    def main() -> None:
        a_reg = qarray(n)
        b_reg = qarray(n)
        product_reg = qarray(n)

        apply_bitstring(a_reg, a_bit_array)
        apply_bitstring(b_reg, b_bit_array)

        multiplier(a_reg, b_reg, product_reg)

        output("a_meas", collect_measurements(measure_array(a_reg)))
        output("b_meas", collect_measurements(measure_array(b_reg)))
        output("product", collect_measurements(measure_array(product_reg)))

    result = main.emulator(n_qubits=qubit_budget).run()
    return result.results[0].as_dict()

from guppyalgos.primitives.arithmetic import multiplier_ripple_gidney_mod

multiplier_cases = [(2, 1, 1), (2, 2, 3), (3, 3, 2), (4, 5, 7)]

for n, a, b in multiplier_cases:
    qubit_budget = 5 * n - 1
    result = run_multiplier_case(multiplier_ripple_gidney_mod, qubit_budget, n, a, b)

    expected_product = (a * b) % (2**n)
    expected_product_bits = int_to_bits(expected_product, n)

    # Both input registers are preserved.
    assert result["a_meas"] == int_to_bits(a, n)
    assert result["b_meas"] == int_to_bits(b, n)

    # The output register contains a * b modulo 2**n.
    assert result["product"] == expected_product_bits

    measured_product = bits_to_int(result["product"])
    print(
        f"n={n}, a={a}, b={b} -> "
        f"product={measured_product} "
        f"(expected {expected_product})"
    )

print("Multiplier checks passed.")

n=2, a=1, b=1 -> product=1 (expected 1)
n=2, a=2, b=3 -> product=2 (expected 2)
n=3, a=3, b=2 -> product=6 (expected 6)
n=4, a=5, b=7 -> product=3 (expected 3)
Multiplier checks passed.

Exponentiation

For a classical base \(b\), an \(m\)-bit quantum exponent \(x\), and an \(n\)-bit output register \(a\), exponentiator_ripple_gidney_mod performs

\[ |x\rangle|a\rangle \longmapsto |x\rangle |a\,b^x\bmod 2^n\rangle. \]

When the output register is initialized to \(|1\rangle\), it contains \(b^x\bmod 2^n\) after the operation.

Writing the little-endian exponent as

\[ x=\sum_{i=0}^{m-1}x_i2^i, \]

we have

\[ b^x\bmod 2^n = \prod_{i=0}^{m-1} \left(b^{2^i}\bmod 2^n\right)^{x_i}. \]

The constants

\[ b_i=b^{2^i}\bmod 2^n \]

are computed classically at compile time.

For each exponent bit \(x_i\), the circuit applies

controlled_multiplier_ripple_gidney_mod_in_place(
    exponent_reg[i], output_reg, b_i
)

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.

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.

def run_exponentiator_case(
    exponentiator: GuppyFunctionDefinition,
    qubit_budget: int,
    n: int,
    base: int,
    exponent: int,
) -> dict:
    """Compute base**exponent modulo 2**n and return the measurements."""
    exponent_reg_size = max(1, exponent.bit_length())

    exponent_bit_array = array(*int_to_bits(exponent, exponent_reg_size))
    initial_output_bit_array = array(*int_to_bits(1, n))

    exponentiator_impl = exponentiator

    @guppy
    @no_type_check
    def main() -> None:
        exponent_reg = qarray(exponent_reg_size)
        output_reg = qarray(n)

        apply_bitstring(exponent_reg, exponent_bit_array)
        apply_bitstring(output_reg, initial_output_bit_array)

        exponentiator_impl(exponent_reg, output_reg, base)

        output("exponent_meas", collect_measurements(measure_array(exponent_reg)))
        output("power", collect_measurements(measure_array(output_reg)))

    result = main.emulator(n_qubits=qubit_budget).run()

    return result.results[0].as_dict()

from guppyalgos.primitives.arithmetic import exponentiator_ripple_gidney_mod

exponentiator_cases = [(3, 3, 0), (3, 3, 1), (3, 3, 2), (4, 3, 3)]

for n, base, exponent in exponentiator_cases:
    exponent_reg_size = max(1, exponent.bit_length())
    expected_exponent_bits = int_to_bits(exponent, exponent_reg_size)

    expected_power = pow(base, exponent, 2**n)
    expected_power_bits = int_to_bits(expected_power, n)

    qubit_budget = exponent_reg_size + 5 * n
    result = run_exponentiator_case(exponentiator_ripple_gidney_mod, qubit_budget, n, base, exponent)

    # The exponent register is preserved.
    assert result["exponent_meas"] == expected_exponent_bits

    # The output contains base**exponent modulo 2**n.
    assert result["power"] == expected_power_bits

    measured_power = bits_to_int(result["power"])
    print(
        f"n={n}, base={base}, exponent={exponent} -> "
        f"power={measured_power} "
        f"(expected {expected_power})"
    )

print("Exponentiator checks passed.")

n=3, base=3, exponent=0 -> power=1 (expected 1)
n=3, base=3, exponent=1 -> power=3 (expected 3)
n=3, base=3, exponent=2 -> power=1 (expected 1)
n=4, base=3, exponent=3 -> power=11 (expected 11)
Exponentiator checks passed.