Modular Addition

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

ModAdd

An n-bit modular addition gate.

Implements |x>|y> => |x>|y + x % p> using \(4n\) Toffoli gates.

This gate can also operate on integers in the Montgomery form.

Parameters

• bitsize: Number of bits used to represent each integer.

• mod: The modulus for the addition.

Registers

• x: A bitsize-sized input register (register x above).

• y: A bitsize-sized input/output register (register y above).

References

• How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates. Construction from Figure 6a and cost summary in Figure 8.

from qualtran.bloqs.mod_arithmetic import ModAdd

Example Instances

n, p = sympy.symbols('n p')
mod_add = ModAdd(n, mod=p)

Graphical Signature

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

Call Graph

from qualtran.resource_counting.generalizers import ignore_split_join
mod_add_g, mod_add_sigma = mod_add.call_graph(max_depth=1, generalizer=ignore_split_join)
show_call_graph(mod_add_g)
show_counts_sigma(mod_add_sigma)

Counts totals:

• AddK: 1

• AddK: 1

• Add: 1

• LinearDepthGreaterThan: 1

• XGate: 1

ModAddK

Applies U(add, M)|x> = |(x + add) % M> if x < M else |x>.

Applies modular addition to input register |x> given parameters mod and add_val s.t.

1. If integer x < mod: output is |(x + add) % M>

2. If integer x >= mod: output is |x>.

This condition is needed to ensure that the mapping of all input basis states (i.e. input states |0>, |1>, …, |2 ** bitsize - 1) to corresponding output states is bijective and thus the gate is reversible.

Also supports controlled version of the gate by specifying a per qubit control value as a tuple of integers passed as cvs.

from qualtran.bloqs.mod_arithmetic import ModAddK

Example Instances

n, m, k = sympy.symbols('n m k')
mod_add_k = ModAddK(bitsize=n, mod=m, add_val=k)

mod_add_k_small = ModAddK(bitsize=4, mod=7, add_val=1)

mod_add_k_large = ModAddK(bitsize=64, mod=500, add_val=23)

Graphical Signature

from qualtran.drawing import show_bloqs
show_bloqs([mod_add_k, mod_add_k_small, mod_add_k_large],
           ['`mod_add_k`', '`mod_add_k_small`', '`mod_add_k_large`'])

Call Graph

from qualtran.resource_counting.generalizers import ignore_split_join
mod_add_k_g, mod_add_k_sigma = mod_add_k.call_graph(max_depth=1, generalizer=ignore_split_join)
show_call_graph(mod_add_k_g)
show_counts_sigma(mod_add_k_sigma)

Counts totals:

• Add: 5

CModAdd

Controlled Modular Addition.

Implements \(\ket{c}\ket{x}\ket{y} \rightarrow \ket{c}\ket{x}\ket{(cx+y)\%p}\) using \(5n+1\) Toffoli gates.

Note: The reference reports \(5n\) toffolis. Our construction has an extra toffoli gate due to the current implementaiton of OutOfPlaceAdder.

Parameters

• dtype: Type of the input registers.

• mod: The modulus for the addition.

• cv: Control value for which the gate is active.

Registers

• ctrl: The control qubit.

• x: A dtype register.

• y: A dtype register.

References

• How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates. Construction from Figure 6a and cost summary in Figure 8.

from qualtran.bloqs.mod_arithmetic import CModAdd

Example Instances

cmodadd_example = CModAdd(QUInt(32), 10**9 + 7)

n, p = sympy.symbols('n p')
cmodadd_symbolic = CModAdd(QUInt(n), p)

Graphical Signature

from qualtran.drawing import show_bloqs
show_bloqs([cmodadd_example, cmodadd_symbolic],
           ['`cmodadd_example`', '`cmodadd_symbolic`'])

Call Graph

from qualtran.resource_counting.generalizers import ignore_split_join
cmodadd_example_g, cmodadd_example_sigma = cmodadd_example.call_graph(max_depth=1, generalizer=ignore_split_join)
show_call_graph(cmodadd_example_g)
show_counts_sigma(cmodadd_example_sigma)

Counts totals:

• AddK: 1

• AddK: 1

• CAdd: 1

• CLinearDepthGreaterThan: 1

• XGate: 1

CModAddK

Perform x += k mod m for constant k, m and quantum x.

Parameters

• k: The integer to add to x.

• mod: The modulus for the addition.

• bitsize: The bitsize of the x register.

Registers

• ctrl: The control bit

• x: The register to perform the in-place modular addition.

References

• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Gidney and Ekerå 2019. The reference implementation in section 2.2 uses CModAddK, but the circuit that it points to is just ModAdd (not ModAddK). This ModAdd is less efficient than the circuit later introduced in the Litinski paper so we choose to use that since it is more efficient and already implemented in Qualtran.

• How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates. Litinski et al. 2023. This CModAdd circuit uses 2 fewer additions than the implementation referenced in the paper above. Because of this we choose to use this CModAdd bloq instead.

from qualtran.bloqs.mod_arithmetic import CModAddK

Example Instances

n, m, k = sympy.symbols('n m k')
cmod_add_k = CModAddK(bitsize=n, mod=m, k=k)

cmod_add_k_small = CModAddK(bitsize=4, mod=7, k=1)

Graphical Signature

from qualtran.drawing import show_bloqs
show_bloqs([cmod_add_k, cmod_add_k_small],
           ['`cmod_add_k`', '`cmod_add_k_small`'])

Call Graph

from qualtran.resource_counting.generalizers import ignore_split_join
cmod_add_k_g, cmod_add_k_sigma = cmod_add_k.call_graph(max_depth=1, generalizer=ignore_split_join)
show_call_graph(cmod_add_k_g)
show_counts_sigma(cmod_add_k_sigma)

Counts totals:

• CModAdd: 1

CtrlScaleModAdd

Perform y += x*k mod m for constant k, m and quantum x, y.

Parameters

• k: The constant integer to scale x before adding into y.

• mod: The modulus of the addition

• bitsize: The size of the two registers.

Registers

• ctrl: The control bit

• x: The ‘source’ quantum register containing the integer to be scaled and added to y.

• y: The ‘destination’ quantum register to which the addition will apply.

References

• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Construction based on description in section 2.2 paragraph 4. We add n And/And† bloqs because the bloq is controlled, but the construction also involves modular addition controlled on the qubits comprising register x.

from qualtran.bloqs.mod_arithmetic import CtrlScaleModAdd

Example Instances

n, m, k = sympy.symbols('n m k')
ctrl_scale_mod_add = CtrlScaleModAdd(bitsize=n, mod=m, k=k)

ctrl_scale_mod_add_small = CtrlScaleModAdd(bitsize=4, mod=7, k=1)

Graphical Signature

from qualtran.drawing import show_bloqs
show_bloqs([ctrl_scale_mod_add, ctrl_scale_mod_add_small],
           ['`ctrl_scale_mod_add`', '`ctrl_scale_mod_add_small`'])

Call Graph

from qualtran.resource_counting.generalizers import ignore_split_join
ctrl_scale_mod_add_g, ctrl_scale_mod_add_sigma = ctrl_scale_mod_add.call_graph(max_depth=1, generalizer=ignore_split_join)
show_call_graph(ctrl_scale_mod_add_g)
show_counts_sigma(ctrl_scale_mod_add_sigma)

Counts totals:

• And: $\displaystyle n$

• And†: $\displaystyle n$

• CModAddK: $\displaystyle n$