QuantumModulus

class QuantumModulus(modulus, inpl_adder=None, qs=None)

This class is a subtype of QuantumFloat, which can be used to model and process modular arithmetic. Modular arithmetic plays an important role in many cryptographical applications, especially in Shor’s algorithm.

The QuantumModulus allows users convenient access to modular arithmetic, which for many gate based frameworks is rather complicated due to the intricacies of the reduction process.

For a first example we simply add two instances:

>>> from qrisp import QuantumModulus
>>> N = 13
>>> a = QuantumModulus(N)
>>> b = QuantumModulus(N)
>>> a[:] = 5
>>> b[:] = 10
>>> c = a + b
>>> print(c)
{2: 1.0}

We get the output 2 because

>>> (5 + 10)%13
2

Similar to QuantumFloat, subtraction and addition are also supported:

>>> d = a*b
>>> print(d)
{11: 1.0}

Check the result:

>>> (5*10)%13
11

Especially relevant for Shor’s algorithm are the in-place operations:

>>> a = QuantumModulus(N)
>>> a[:] = 5
>>> a *= 10
>>> print(a)
{11: 1.0}

Specifying a custom adder

It is possible to specify a custom adder that is used when processing the Modular-Arithmetic. For this, you can use the inpl_adder keyword.

By default, the Fourier-adder is used, but we can for instance also try the Cuccaro-adder.

>>> from qrisp import cuccaro_adder
>>> a = QuantumModulus(N, inpl_adder = cuccaro_adder)
>>> a[:] = 5
>>> a *= 10
>>> print(a)
{11: 1.0}

Or the Gidney-adder.

>>> from qrisp import gidney_adder
>>> a = QuantumModulus(N, inpl_adder = gidney_adder)
>>> a[:] = 5
>>> a *= 10
>>> print(a)
{11: 1.0}    

To learn how to create your own adder for this feature, please visit this page.

Warning

Currently the adder is only used in in-place multiplication, since this is the relevant operation for Shor’s algorithm. The other operations (such as addition etc.) will follow in a future release of Qrisp.

Advanced usage

The modular multiplication uses a technique called Montgomery reduction. The quantum version of this algorithm can be found in this paper. The idea behind Montgomery reduction is to choose a differing representation of numbers to enhance the reduction step of modular arithmetic. This representation works as follows: For an integer \(m\) called Montgomery shift, the modular number \(a \in \mathbb{Z}/N\mathbb{Z}\) is represented as

\[\hat{k} = (2^{-m} k) \text{mod} N\]

If you’re interested in why this representation is advantageous, we recommend checking out the linked resources above.

For Qrisp, the Montgomery shift can be modified via the attribute m.

>>> a = QuantumModulus(N)
>>> a.m = 3
>>> a[:] = 1
>>> print(a)
{1: 1.0}

We shift back to 0:

>>> a.m -= 3
>>> print(a)
{8: 1.0}

Note that this shift is only a compiler shift - ie. no quantum gates are applied. Instead the decoder function is modified.