Modular Multiplication#

from qualtran import Bloq, CompositeBloq, BloqBuilder, Signature, Register
from qualtran import QBit, QInt, QUInt, QAny
from qualtran.drawing import show_bloq, show_call_graph, show_counts_sigma
from typing import *
import numpy as np
import sympy
import cirq

ModDbl#

An n-bit modular doubling gate.

Implements \(\ket{x} \rightarrow \ket{2x \mod p}\) using \(2n\) Toffoli gates.

Parameters#

  • dtype: Dtype of the number to double.

  • p: The modulus for the doubling.

Registers#

  • x: The register containing the number to double.

References#

from qualtran.bloqs.mod_arithmetic import ModDbl

Example Instances#

moddbl_small = ModDbl(QUInt(4), 13)

prime = 10**9 + 7
moddbl_large = ModDbl(QUInt(32), prime)

Graphical Signature#

from qualtran.drawing import show_bloqs
show_bloqs([moddbl_small, moddbl_large],
           ['`moddbl_small`', '`moddbl_large`'])

Call Graph#

from qualtran.resource_counting.generalizers import ignore_split_join
moddbl_small_g, moddbl_small_sigma = moddbl_small.call_graph(max_depth=1, generalizer=ignore_split_join)
show_call_graph(moddbl_small_g)
show_counts_sigma(moddbl_small_sigma)
../../_images/4944b2007179a6d2b8ac54f9f018d513de92c1108fbeff87eeb35066fa903d6b.svg

Counts totals:

  • AddK: 1

  • AddK: 1

  • CNOT: 1

  • XGate: 2

CModMulK#

Perform controlled modular multiplication by a constant.

Applies \(\ket{c}\ket{c} \rightarrow \ket{c} \ket{x*k^c \mod p}\).

Parameters#

  • dtype: Dtype of the register.

  • k: The integer multiplicative constant.

  • mod: The integer modulus.

Registers#

  • ctrl: The control bit

  • x: The integer being multiplied

from qualtran.bloqs.mod_arithmetic import CModMulK

Example Instances#

import sympy

k, N, n_x = sympy.symbols('k N n_x')
modmul_symb = CModMulK(QUInt(n_x), k=k, mod=N)

modmul = CModMulK(QUInt(8), k=123, mod=13 * 17)

Graphical Signature#

from qualtran.drawing import show_bloqs
show_bloqs([modmul_symb, modmul],
           ['`modmul_symb`', '`modmul`'])

Call Graph#

from qualtran.resource_counting.generalizers import ignore_split_join
modmul_symb_g, modmul_symb_sigma = modmul_symb.call_graph(max_depth=1, generalizer=ignore_split_join)
show_call_graph(modmul_symb_g)
show_counts_sigma(modmul_symb_sigma)
../../_images/8176524178be11b380ffa566de047411e062ed53a0ae79d3667d027d7e3fea54.svg

Counts totals:

  • CSwap: 1

  • CtrlScaleModAdd: 2

DirtyOutOfPlaceMontgomeryModMul#

Perform windowed montgomery modular multiplication.

Applies the trasformation

\[ \ket{x}\ket{y}\ket{0}\ket{0}\ket{0} \rightarrow \ket{x}\ket{y}\ket{xy2^{-n}}\ket{h}\ket{c} \]

Where:

  • \(n\) is the bitsize.

  • \(x, y\) are in montgomery form

  • \(h\) is an ancilla register that represents intermidate values.

  • \(c\) is whether a final modular reduction was applied or not.

Parameters#

  • bitsize: size of the numbers.

  • window_size: size of the window.

  • mod: The integer modulus.

  • uncompute: whether to compute or uncompute.

Registers#

  • x: The first integer

  • y: The second integer

  • target: product in montgomery form \(xy 2^{-n}\)

  • qrom_indices: concatination of the indicies used to query QROM.

  • reduced: whether a final modular reduction was applied.

References#

from qualtran.bloqs.mod_arithmetic import DirtyOutOfPlaceMontgomeryModMul

Example Instances#

dirtyoutofplacemontgomerymodmul_small = DirtyOutOfPlaceMontgomeryModMul(6, 2, 7)

dirtyoutofplacemontgomerymodmul_medium = DirtyOutOfPlaceMontgomeryModMul(
    bitsize=16, window_size=4, mod=2**15 - 1
)

Graphical Signature#

from qualtran.drawing import show_bloqs
show_bloqs([dirtyoutofplacemontgomerymodmul_small, dirtyoutofplacemontgomerymodmul_medium],
           ['`dirtyoutofplacemontgomerymodmul_small`', '`dirtyoutofplacemontgomerymodmul_medium`'])

Call Graph#

from qualtran.resource_counting.generalizers import ignore_split_join
dirtyoutofplacemontgomerymodmul_small_g, dirtyoutofplacemontgomerymodmul_small_sigma = dirtyoutofplacemontgomerymodmul_small.call_graph(max_depth=1, generalizer=ignore_split_join)
show_call_graph(dirtyoutofplacemontgomerymodmul_small_g)
show_counts_sigma(dirtyoutofplacemontgomerymodmul_small_sigma)
../../_images/561c89c638004782609cdf716190102ef30867e430870477cd432094f71dd5d8.svg

Counts totals:

  • AddK: 1

  • LessThanConstant: 1

  • SingleWindowModMul: 3

  • XGate: 1