Reversible arithmetic
These device kernels are imported from cudaq_algorithms.primitives
and called inside a @cudaq.kernel. They mutate the supplied registers
and return no classical result. The signatures below are registered
explicitly with Sphinx because autodoc does not render decorated CUDA-Q
kernels.
Register conventions
Integer registers are nonempty, unsigned, and little-endian: qubit zero
has weight one. An n-qubit binary register represents integers modulo
2**n. Every quantum view passed to an operation must be pairwise
disjoint from the others and have the stated width. Carry/work views
start in zero and are restored to zero unless stated otherwise.
These are caller preconditions, not runtime validation. Pass matching operand widths, an n-qubit work view, and exactly n constant bits. Mismatched widths are undefined: depending on the kernel and the constant, a call raises an index error, ignores the extra qubits, or acts on fewer bits than the target has. A constant-bit list shorter than n is read past its end without an error, so the constant that is applied is unpredictable.
Flags are XOR outputs: a comparison toggles out[0] by its predicate.
The one-qubit flag can start in zero, one, or a coherent state. It is
distinct from clean workspace. All maps extend coherently to superposed
inputs, preserving the phases needed by compute/use/uncompute.
Use the supplied inverse kernels. The CDKM family requires its explicit
inverses; cudaq.adjoint is not supported for those kernels. The QFT
family also supplies explicit inverses.
See Modular arithmetic and comparison flags for the CDKM/QFT comparison and the executable arithmetic tutorial.
CDKM addition and subtraction
- cudaq_algorithms.primitives.add_register(a: cudaq.qview, b: cudaq.qview, carry: cudaq.qview)
Add a into b modulo
2**n, preserving a:|a,b,0> -> |a,(b+a) mod 2**n,0>.- Parameters:
a – n-qubit addend, restored after use.
b – n-qubit target.
carry – One clean qubit, restored to zero.
The inverse is
subtract_register(). Cost:2*n-2Toffolis (zero for n=1). Overflow is discarded; there is no carry-out result.
- cudaq_algorithms.primitives.subtract_register(a: cudaq.qview, b: cudaq.qview, carry: cudaq.qview)
Subtract a from b modulo
2**n, preserving a:|a,b,0> -> |a,(b-a) mod 2**n,0>.- Parameters:
a – n-qubit subtrahend, restored after use.
b – n-qubit target.
carry – One clean qubit, restored to zero.
This is the hand-written inverse of
add_register(), with the same workspace contract and2*n-2Toffoli cost.
- cudaq_algorithms.primitives.add_constant(target: cudaq.qview, constant_bits: list[int], work: cudaq.qview, carry: cudaq.qview)
Replace target by
(target+K) mod 2**n.- Parameters:
target – n-qubit binary target.
constant_bits – Exactly n bits, with bit k equal to
(K >> k) & 1for0 <= K < 2**n.work – n clean qubits, restored to zero.
carry – One clean qubit, restored to zero.
The constant is loaded into work, added, and unloaded. The inverse is
subtract_constant(); each direction uses2*n-2Toffolis.
- cudaq_algorithms.primitives.subtract_constant(target: cudaq.qview, constant_bits: list[int], work: cudaq.qview, carry: cudaq.qview)
Replace target by
(target-K) mod 2**n.- Parameters:
target – n-qubit binary target.
constant_bits – Exactly n little-endian bits of K, with
0 <= K < 2**n.work – n clean qubits, restored to zero.
carry – One clean qubit, restored to zero.
This is the hand-written inverse of
add_constant(), with the same2*n-2Toffoli cost.
CDKM comparisons
- cudaq_algorithms.primitives.cmp_ge_register(a: cudaq.qview, b: cudaq.qview, carry: cudaq.qview, out: cudaq.qview)
Apply
out[0] ^= (a >= b)using unsigned comparison.- Parameters:
a – n-qubit operand, preserved.
b – n-qubit operand, preserved.
carry – One clean qubit, restored to zero.
out – One-qubit XOR flag; any input state is allowed.
No n-qubit work register is needed. Applying this kernel twice with the same operands uncomputes the flag. Cost:
2*n-1Toffolis.
- cudaq_algorithms.primitives.cmp_gt_register(a: cudaq.qview, b: cudaq.qview, carry: cudaq.qview, out: cudaq.qview)
Apply the strict unsigned comparison
out[0] ^= (a > b).- Parameters:
a – n-qubit operand, preserved.
b – n-qubit operand, preserved.
carry – One clean qubit, restored to zero.
out – One-qubit XOR flag; any input state is allowed.
This kernel is self-inverse under its workspace preconditions and has the same
2*n-1Toffoli cost ascmp_ge_register().
- cudaq_algorithms.primitives.cmp_ge_constant(x_reg: cudaq.qview, complement_bits: list[int], k_is_zero: int, work: cudaq.qview, carry: cudaq.qview, out: cudaq.qview)
Apply
out[0] ^= (x >= K), preserving x.- Parameters:
x_reg – n-qubit binary operand, preserved.
complement_bits – Exactly n little-endian bits of
(2**n-K) mod 2**n.k_is_zero – 1 exactly when K=0; otherwise 0.
work – n clean qubits, restored to zero.
carry – One clean qubit, restored to zero.
out – One-qubit XOR flag; any input state is allowed.
The threshold satisfies
0 <= K <= 2**n. Both endpoints use all-zero complement bits: K=0 andk_is_zero=1always toggle out;K=2**nandk_is_zero=0never toggle it. Applying the kernel twice uncomputes its flag. Cost:2*n-1Toffolis for positive K, and no Toffolis for K=0.
Fourier transforms and phase addition
- cudaq_algorithms.primitives.qft(reg: cudaq.qview)
Apply the QFT without final bit-reversal swaps.
- Parameters:
reg – n-qubit register, initially in the binary basis.
On a basis input x, qubit t has the factor
(|0> + exp(2*pi*i*x/2**(t+1))*|1>)/sqrt(2). This ordering is the convention consumed byphase_add_constant()and undone byiqft(). No additional workspace is required.
- cudaq_algorithms.primitives.iqft(reg: cudaq.qview)
Apply the hand-written inverse of the swap-free
qft().- Parameters:
reg – n-qubit register in that Fourier convention.
The output is back in the binary basis, with no additional workspace. Do not insert bit-reversal swaps between these transforms and
phase_add_constant().
- cudaq_algorithms.primitives.phase_add_constant(reg: cudaq.qview, constant: int)
Add K modulo
2**nto a register already in the swap-free Fourier basis. No forward or inverse QFT is included.- Parameters:
reg – n-qubit Fourier-basis register, with
1 <= n <= 62.constant – Integer K, interpreted modulo
2**nand representable by the kernel’s signed 64-bit integer.
Qubit t receives phase
2*pi*(K mod 2**(t+1))/2**(t+1). The register stays in the Fourier basis. Use-Kto invert the operation, provided the negated constant is representable. For binary inputs useadd_constant_qft()instead.
- cudaq_algorithms.primitives.add_constant_qft(reg: cudaq.qview, constant: int)
Replace binary reg by
(reg+K) mod 2**nusing QFT,phase_add_constant(), and inverse QFT.- Parameters:
reg – n-qubit binary target, with
1 <= n <= 62.constant – Integer K, interpreted modulo
2**nand representable by the kernel’s signed 64-bit integer.
No workspace is required. The inverse is
subtract_constant_qft(). The implementation usesn*(n-1)controlled phase rotations and n single-qubit phase rotations, with no Toffolis. Rotation synthesis costs are not included in these logical counts.
- cudaq_algorithms.primitives.subtract_constant_qft(reg: cudaq.qview, constant: int)
Replace binary reg by
(reg-K) mod 2**n.- Parameters:
reg – n-qubit binary target, with
1 <= n <= 62.constant – Integer K; both K and its negation must fit the kernel’s signed 64-bit integer.
This is the inverse of
add_constant_qft(), implemented using phase addition by-Kbetween QFT and inverse QFT. It needs no workspace and has the same logical rotation count.
QFT comparisons with a shifted operand
- cudaq_algorithms.primitives.cmp_ge_constant_qft_shift(x_reg: cudaq.qview, constant: int, invert: int, out: cudaq.qview)
Toggle a comparison flag and leave the operand shifted:
|x,f> -> |(x-K) mod 2**n, f XOR predicate(x)>.- Parameters:
x_reg – n-qubit binary operand, with
1 <= n <= 61.constant – Threshold K, with
0 <= K <= 2**n.invert – 0 selects
x >= K; 1 selectsx < K.out – One-qubit XOR flag; any input state is allowed.
The predicate uses the original x. At K=0 the operand is unshifted; the predicate is always true for
invert=0and always false forinvert=1. AtK=2**nthe modular shift is also zero, and these constant predicates are reversed.No additional workspace is required. Between this kernel and
cmp_ge_constant_qft_shift_adj(), use the flag while leaving x_reg untouched. To restore x while retaining the computed flag, follow the compute half withadd_constant_qft()using K. Usecmp_ge_constant()for an operand-preserving comparator.
- cudaq_algorithms.primitives.cmp_ge_constant_qft_shift_adj(x_reg: cudaq.qview, constant: int, invert: int, out: cudaq.qview)
Apply the hand-written inverse of
cmp_ge_constant_qft_shift()with the same K and invert value.- Parameters:
x_reg – n-qubit shifted operand, with
1 <= n <= 61.constant – The compute half’s threshold,
0 <= K <= 2**n.invert – The compute half’s predicate selector, 0 or 1.
out – The one-qubit XOR flag from the compute half.
On the compute half’s output, this restores the original operand and flag without extra workspace. In a compute/Z/uncompute phase oracle, the flag returns to its input state and the selected phase remains on the operand.