Exponentiator

Download Notebook - exponentiator.ipynb

This notebook demonstrates the modulo-\(2^n\) exponentiator implemented in guppyalgos.primitives.arithmetic.

from typing import no_type_check

from guppylang import guppy

from guppyalgos.primitives.arithmetic import exponentiator_ripple_gidney_mod

from guppylang.std.builtins import output
from guppylang.std.quantum import collect_measurements, measure_array

from guppyalgos.utils import apply_bitstring, bits_to_int, int_to_bits, qarray

Math and Circuit Structure

For a given \(n\)-bit classical constant \(b\), the target operation for the exponentiator is $\( |x\rangle |1\rangle \mapsto |x\rangle |b^x \mod 2^n \rangle. \)\( Since this operation is generally not reversible for even bases, \)b$ must be odd for this implementation.

The exponentiation is decomposed into the standard sequence of controlled modular multiplications as follows. For a little-endian exponent \(x = x_0 x_1 \dots x_{m-1}\), we can write the exponential as $\( b^x \mod 2^n = \prod_{i=0}^{m-1} \left( b^{2^i} \mod 2^n \right)^{x_i}. \)\( The multiplicand \)b^{2^i} \mod 2^n\( can be efficiently classically precomputed via repeated squaring, so in total the exponentiator requires \)m$ controlled multipliers.

n = 2
exponent = 5
base = 3

expected = base ** exponent % (2 ** n)
print(f"Expected output: {expected}")

Expected output: 3

exponent_reg_size = exponent.bit_length()
exponent_bits = int_to_bits(exponent, exponent_reg_size)
initial_state_bits = int_to_bits(1, n)

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

    exponentiator_ripple_gidney_mod(exponent_reg, output_reg, base)

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

required_qubits = exponent_reg_size + 5 * n
result = main.emulator(n_qubits=required_qubits).run().results[0].as_dict()
exponent_reg_measurement_result = bits_to_int(result["exponent_meas"])
output_reg_measurement_result = bits_to_int(result["output_meas"])

print(f"Exponent register measurement result: {exponent_reg_measurement_result}")
print(f"Output register measurement result: {output_reg_measurement_result}")

Exponent register measurement result: 5
Output register measurement result: 3