QMontgomeryUInt#

qualtran.QMontgomeryUInt

Montgomery form of an unsigned integer of a given width bitsize which wraps around upon overflow.

Inherits From: QDType, QCDType

qualtran.QMontgomeryUInt(
    bitsize, modulus=attr_dict['modulus'].default
)

Similar to unsigned integer types in C. Any intended wrap around effect is expected to be handled by the developer. Any QMontgomeryUInt can be treated as a QUInt, but not every QUInt can be treated as a QMontgomeryUInt. Montgomery form is used in order to compute fast modular multiplication.

In order to convert an unsigned integer from a finite field x % p into Montgomery form you first must choose a value r > p where gcd(r, p) = 1. Typically, this value is a power of 2.

Conversion to Montgomery form: [x] = (x * r) % p

Conversion from Montgomery form to normal form: x = REDC([x])

Pseudocode for REDC(u) can be found in the resource below.

References

Attributes

bitsize

The number of qubits used to represent the integer.

modulus

 

num_bits

 

num_cbits

Number of classical bits required to represent a single instance of this data type.

num_qubits

Number of qubits required to represent a single instance of this data type.

Methods#

is_symbolic

View source

is_symbolic() -> bool

Returns True if this dtype is parameterized with symbolic objects.

get_classical_domain

View source

get_classical_domain() -> Iterable[Any]

Yields all possible classical (computational basis state) values representable by this type.

to_bits

View source

to_bits(
    x: int
) -> List[int]

Yields individual bits corresponding to binary representation of x

from_bits

View source

from_bits(
    bits: Sequence[int]
) -> int

Combine individual bits to form x

assert_valid_classical_val

View source

assert_valid_classical_val(
    val: int, debug_str: str = 'val'
)

Raises an exception if val is not a valid classical value for this type.

Args

val

A classical value that should be in the domain of this QDType.

debug_str

Optional debugging information to use in exception messages.

assert_valid_classical_val_array

View source

assert_valid_classical_val_array(
    val_array: NDArray[np.integer], debug_str: str = 'val'
)

Raises an exception if val_array is not a valid array of classical values for this type.

Often, validation on an array can be performed faster than validating each element individually.

Args

val_array

A numpy array of classical values. Each value should be in the domain of this QDType.

debug_str

Optional debugging information to use in exception messages.

montgomery_inverse

View source

montgomery_inverse(
    xm: int
) -> int

Returns the modular inverse of an integer in montgomery form.

Args

xm

An integer in montgomery form.

montgomery_product

View source

montgomery_product(
    xm: int, ym: int
) -> int

Returns the modular product of two integers in montgomery form.

Args

xm

The first montgomery form integer for the product.

ym

The second montgomery form integer for the product.

montgomery_to_uint

View source

montgomery_to_uint(
    xm: int
) -> int

Converts an integer in montgomery form to a normal form integer.

Args

xm

An integer in montgomery form.

uint_to_montgomery

View source

uint_to_montgomery(
    x: int
) -> int

Converts an integer into montgomery form.

Args

x

An integer.

__ne__

__ne__(
    other
)

Check equality and either forward a NotImplemented or return the result negated.

__eq__

__eq__(
    other
)

Method generated by attrs for class QMontgomeryUInt.

On this page

This Page