qat.lang.AQASM.arithmetic.modular_exp

qat.lang.AQASM.arithmetic.modular_exp(reg_control_size: int, acc_size: int, base: int, modulus: int)

Generates a QRoutine performing the following operation:

\[|a\rangle |0 \rangle \mapsto |a\rangle | \textrm{base}^a \mod \textrm{modulus} \rangle\]

acc_size is expected to be of size bitlength(modulus).

This routine is the basis of Shor’s algorithm for number factoring:

from qat.lang.AQASM import *
from qat.lang.AQASM.arithmetic import modular_exp
from qat.lang.AQASM.qftarith import QFT
import qat.lang.AQASM.qftarith as qftarith

modulus = 15
base = 2
bitlength = 4 # We need 4 bits to write 15

shor = Program()
phase_reg = shor.qalloc(2 * bitlength)
acc = shor.qalloc(bitlength)

modular_exp(2 * bitlength, bitlength, base, modulus)(phase_reg, acc)


QFT(2 * bitlength)(phase_reg)

circuit = shor.to_circ(link=[qftarith])

from qat.core.util import statistics

print(statistics(circuit))

{'nbqbits': 19, 'size': 2, 'gates': {'custom gate': 0, 'X': 1, 'H': 3720, 'C-PH': 8988, 'C-C-PH': 1472, 'C-C-CNOT': 128, 'C-C-C-PH': 384, 'C-C-X': 128, 'C-SWAP': 32}, 'measurements': 0, 'resets': 0, 'logic': 0, 'breaks': 0, 'remaps': 0, 'gate_size': 14853}
Parameters

  • reg_control_size – the exponent registers size

  • acc_size – the accumulator size

  • base – the root of the exponentiation

  • modulus – the modulus value

Warning

This routine makes use of Euclide’s algorithms to invert base modulo modulus. In order for this to work, base and modulus need to be coprime.

Warning

This routine has public arity reg_control_size + acc_size but uses acc_size + 1 additional qubits (these will be automatically allocated at circuit generation time, in the to_circ() method).

This number does not include the optional qubits allocated by sub-routines used inside this routine

This routine calls: