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-2 Toffolis (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 and 2*n-2 Toffoli 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) & 1 for 0 <= 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 uses 2*n-2 Toffolis.

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 same 2*n-2 Toffoli 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-1 Toffolis.

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-1 Toffoli cost as cmp_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 and k_is_zero=1 always toggle out; K=2**n and k_is_zero=0 never toggle it. Applying the kernel twice uncomputes its flag. Cost: 2*n-1 Toffolis 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 by phase_add_constant() and undone by iqft(). 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**n to 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**n and 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 -K to invert the operation, provided the negated constant is representable. For binary inputs use add_constant_qft() instead.

cudaq_algorithms.primitives.add_constant_qft(reg: cudaq.qview, constant: int)

Replace binary reg by (reg+K) mod 2**n using QFT, phase_add_constant(), and inverse QFT.

Parameters:
  • reg – n-qubit binary target, with 1 <= n <= 62.

  • constant – Integer K, interpreted modulo 2**n and representable by the kernel’s signed 64-bit integer.

No workspace is required. The inverse is subtract_constant_qft(). The implementation uses n*(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 -K between 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 selects x < 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=0 and always false for invert=1. At K=2**n the 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 with add_constant_qft() using K. Use cmp_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.