Modular Multiplier Example¶

Download Notebook - multiplier.ipynb

This notebook demonstrates the Gidney ripple-based multiplier circuits in guppyalgos.primitives.arithmetic:

multiplier_ripple_gidney_mod
cntrl_multiplier_ripple_gidney_mod

Both implement multiplication modulo \(2^n\) on little-endian bit registers.

from typing import no_type_check

from guppylang import guppy
from guppylang.std.builtins import array, output
from guppylang.std.quantum import (
    collect_measurements,
    discard,
    measure_array,
    qubit,
    x,
 )

from guppyalgos.primitives.arithmetic import (
    cntrl_multiplier_ripple_gidney_mod,
    multiplier_ripple_gidney_mod,
 )
from guppyalgos.utils import apply_bitstring, bits_to_int, int_to_bits, qarray

Math and Circuit Structure¶

For \(n\)-bit little-endian registers \(a\) and \(b\), the target operation is

\[ |a\rangle|b\rangle|p\rangle \mapsto |a\rangle|b\rangle|p + a\cdot b \; (\mathrm{mod}\; 2^n)\rangle. \]

Write \(b = \sum_{i=0}^{n-1} b_i 2^i\). Then

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

So the circuit performs a sequence of modular additions of shifted addends.

Uncontrolled multiplier: add \((a\ll i)\) into product only when multiplier bit \(b_i=1\).
Controlled multiplier: same, but each addition is additionally gated by a global control ctrl.

Internally, temporary work qubits are created and uncomputed each step, then discarded. The total qubit count for the multiplier breaks down into:

\(n\) qubits for the input \(a\)
\(n\) qubits for the input \(b\)
\(n\) qubits for the (temporary) partial product \(b_i\,(a\ll i)\)
\(n\) qubits for the output \(a \cdot b\)
Any ancilla qubits used by the adder

def run_multiplier_case(n: int, a: int, b: int) -> dict:
    """Run one uncontrolled modular multiplication case and return measured bits."""
    a_bits = int_to_bits(a, n)
    b_bits = int_to_bits(b, n)
    a_bit_array = array(*a_bits)
    b_bit_array = array(*b_bits)

    @guppy
    @no_type_check
    def main() -> None:
        a_reg = qarray(n)
        apply_bitstring(a_reg, a_bit_array)
        multiplier = qarray(n)
        apply_bitstring(multiplier, b_bit_array)
        product = qarray(n)

        multiplier_ripple_gidney_mod(a_reg, multiplier, product)

        output("a_meas", collect_measurements(measure_array(a_reg)))
        output("mult_meas", collect_measurements(measure_array(multiplier)))
        output("prod_meas", collect_measurements(measure_array(product)))

    res = main.emulator(n_qubits=5 * n - 1).run()
    return res.results[0].as_dict()


def run_cntrl_multiplier_case(
    n: int, a: int, b: int, ctrl_active: bool
 ) -> dict:
    """Run one controlled modular multiplication case and return measured bits."""
    a_bits = int_to_bits(a, n)
    b_bits = int_to_bits(b, n)
    a_bit_array = array(*a_bits)
    b_bit_array = array(*b_bits)

    @guppy
    @no_type_check
    def main() -> None:
        a_reg = qarray(n)
        apply_bitstring(a_reg, a_bit_array)
        multiplier = qarray(n)
        apply_bitstring(multiplier, b_bit_array)
        product = qarray(n)

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

        cntrl_multiplier_ripple_gidney_mod(ctrl, a_reg, multiplier, product)

        output("a_meas", collect_measurements(measure_array(a_reg)))
        output("mult_meas", collect_measurements(measure_array(multiplier)))
        output("prod_meas", collect_measurements(measure_array(product)))

        discard(ctrl)

    res = main.emulator(n_qubits=5 * n + 1).run()
    return res.results[0].as_dict()

Uncontrolled Multiplier Demo¶

The following cell checks that

\[ \mathrm{product}_{\mathrm{out}} = (a\cdot b) \bmod 2^n \]

and that the input registers are preserved.

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

for n, a, b in uncontrolled_cases:
    result = run_multiplier_case(n, a, b)
    expected_bits = int_to_bits((a * b) % (2**n), n)

    assert result["a_meas"] == int_to_bits(a, n)
    assert result["mult_meas"] == int_to_bits(b, n)
    assert result["prod_meas"] == expected_bits

    print(
        f"n={n}, a={a}, b={b} -> prod={bits_to_int(result['prod_meas'])} (expected {bits_to_int(expected_bits)})"
    )

print("Uncontrolled multiplier checks passed.")

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

Controlled Multiplier Demo¶

For the controlled circuit, we check two behaviors:

ctrl = 0: product register is unchanged.
ctrl = 1: product register becomes \((a\cdot b) \bmod 2^n\).

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):
        result = run_cntrl_multiplier_case(n, a, b, ctrl_active)
        expected_value = 0 if not ctrl_active else (a * b) % (2**n)
        expected_bits = int_to_bits(expected_value, n)

        assert result["a_meas"] == int_to_bits(a, n)
        assert result["mult_meas"] == int_to_bits(b, n)
        assert result["prod_meas"] == expected_bits

        print(
            f"ctrl={int(ctrl_active)}, n={n}, a={a}, b={b} -> ",
            f"prod={bits_to_int(result['prod_meas'])} (expected {bits_to_int(expected_bits)})",
        )

print("Controlled multiplier checks passed.")

ctrl=0, n=2, a=1, b=1 ->  prod=0 (expected 0)
ctrl=1, n=2, a=1, b=1 ->  prod=1 (expected 1)
ctrl=0, n=2, a=2, b=3 ->  prod=0 (expected 0)
ctrl=1, n=2, a=2, b=3 ->  prod=2 (expected 2)
ctrl=0, n=3, a=3, b=2 ->  prod=0 (expected 0)
ctrl=1, n=3, a=3, b=2 ->  prod=6 (expected 6)
ctrl=0, n=4, a=5, b=7 ->  prod=0 (expected 0)
ctrl=1, n=4, a=5, b=7 ->  prod=3 (expected 3)
Controlled multiplier checks passed.