guppyalgos.primitives.arithmetic

Quantum arithmetic algorithms.

Functions

adder_ripple_cuccaro_carry_out(a_reg, b_reg, ...)

Apply an optimized Cuccaro ripple-carry adder.

adder_ripple_cuccaro_carry_out_dagger(a_reg, ...)

Apply the inverse of the Cuccaro ripple-carry adder.

adder_ripple_cuccaro_mod(a_reg, b_reg)

Apply an optimized modular Cuccaro ripple-carry adder.

adder_ripple_cuccaro_mod_dagger(a_reg, b_reg)

Apply the inverse of the Cuccaro ripple-carry modular adder circuit.

adder_ripple_gidney_carry_out(a_reg, b_reg, ...)

Apply a Gidney non-modular ripple-carry adder.

adder_ripple_gidney_carry_out_dagger(a_reg, ...)

Apply the dagger of the non-modular Gidney ripple-carry adder.

adder_ripple_gidney_mod(a_reg, b_reg)

Apply a modular Gidney ripple-carry adder.

adder_ripple_gidney_mod_dagger(a_reg, b_reg)

Apply the inverse of the modular Gidney ripple-carry adder.

cntrl_adder_ripple_cuccaro_carry_out(ctrl, ...)

Apply a controlled optimized Cuccaro ripple-carry adder.

cntrl_adder_ripple_cuccaro_carry_out_dagger(...)

Apply the inverse of the controlled Cuccaro ripple-carry adder.

cntrl_adder_ripple_cuccaro_mod(ctrl, a_reg, ...)

Apply a controlled optimized modular Cuccaro ripple-carry adder.

cntrl_adder_ripple_cuccaro_mod_dagger(ctrl, ...)

Apply the inverse of the controlled optimized modular Cuccaro ripple-carry adder.

cntrl_adder_ripple_gidney_carry_out(ctrl, ...)

Apply a controlled Gidney ripple-carry adder.

cntrl_adder_ripple_gidney_carry_out_dagger(...)

Apply the dagger of the controlled Gidney ripple-carry adder.

cntrl_adder_ripple_gidney_mod(ctrl, a_reg, b_reg)

Apply a controlled modular Gidney ripple-carry adder.

cntrl_adder_ripple_gidney_mod_dagger(ctrl, ...)

Apply the dagger of the controlled modular Gidney ripple-carry adder.

cntrl_multiplier_ripple_gidney_mod(ctrl, ...)

Conditionally multiply a_reg by b_reg into product modulo 2**n.

cntrl_multiplier_ripple_gidney_mod_in_place(...)

Conditionally multiply a_reg by the odd classical constant b in-place.

cntrl_subtractor_ripple_cuccaro_carry_out(...)

Apply a controlled Cuccaro ripple-carry subtraction circuit.

cntrl_subtractor_ripple_cuccaro_mod(ctrl, ...)

Apply a controlled Cuccaro ripple-carry modular subtraction circuit.

cntrl_subtractor_ripple_gidney_carry_out(...)

Apply a controlled Gidney ripple-carry subtraction circuit.

cntrl_subtractor_ripple_gidney_mod(ctrl, ...)

Apply a controlled Gidney ripple-carry modular subtraction circuit.

compute_and(q0, q1, t_qubit)

Temporary AND computation acting on 0 state target.

exponentiator_ripple_gidney_mod(...)

Multiply the output register by base^exponent modulo 2**n_output.

multiplier_ripple_gidney_mod(a_reg, b_reg, ...)

Add the product of a_reg and b_reg into product modulo 2**n.

multiplier_ripple_gidney_mod_in_place(a_reg, b)

Multiply a_reg by the odd classical constant b in-place.

subtractor_ripple_cuccaro_carry_out(a_reg, ...)

Apply a Cuccaro ripple-carry subtraction circuit.

subtractor_ripple_cuccaro_mod(a_reg, b_reg)

Apply a Cuccaro ripple-carry modular subtraction circuit.

subtractor_ripple_gidney_carry_out(a_reg, ...)

Apply a Gidney ripple-carry subtraction circuit.

subtractor_ripple_gidney_mod(a_reg, b_reg)

Apply a Gidney ripple-carry modular subtraction circuit.

uncompute_and(q_0, q_1, target_q)

Uncompute the logical AND operation.
guppyalgos.primitives.arithmetic.adder_ripple_cuccaro_carry_out(a_reg, b_reg, carry_out)

Apply an optimized Cuccaro ripple-carry adder.

This circuit performs in-place modular addition of a_reg into b_reg and computes the final carry-out:

|a>|b>|0> -> |a>|a + b mod 2^n>|carry_out>

The circuit requires one ancilla qubit. The circuit’s depth depends on the supplied ladder implementations.

When both the CNOT and Toffoli ladders are linear, gates from the two ladders can be interleaved and executed in parallel, as shown in Fig. 6 of the Reference. The pseudocode in Fig. 5 makes this scheduling explicit: each line corresponds to a single time-slice.

In our implementation, the ladders are represented separately rather than being manually interleaved. This provides greater flexibility: when linear ladders are supplied, the compiler can identify independent operations and schedule them in parallel, recovering the linear-depth construction described by Cuccaro et al. If alternative ladder implementations are supplied—for example, logarithmic-depth ladders—the surrounding adder construction does not impose the linear scheduling of Fig. 5 and can instead take advantage of the lower-depth ladder structure.

Reference: Cuccaro, Steven A., et al. “A new quantum ripple-carry addition circuit.” arXiv preprint quant-ph/0410184 (2004).

Parameters:

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg += a_reg mod 2^n.

  • carry_out (qubit) – Qubit that is flipped if the addition produces a final carry out.

guppyalgos.primitives.arithmetic.adder_ripple_cuccaro_carry_out_dagger(a_reg, b_reg, carry_out)

Apply the inverse of the Cuccaro ripple-carry adder.

Computes b - a in place on b_reg while restoring a_reg. The supplied borrow_out qubit is treated as the carry-out qubit from the forward adder and is uncomputed by the inverse operation.

Transformation:

|a>|a + b mod 2^n>|carry_out> -> |a>|b>|0>

The circuit has linear depth and requires one ancilla qubit.

TODO: Rewrite using CNOT ladders and Toffoli ladders. This adder does not necessarily have linear depth, it depends on the choice of ladders.

Reference: Cuccaro, Steven A., et al. “A new quantum ripple-carry addition circuit.” arXiv preprint quant-ph/0410184 (2004).

Parameters:

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg -= a_reg mod 2^n.

  • carry_out (qubit) – Carry/borrow qubit to uncompute.

guppyalgos.primitives.arithmetic.adder_ripple_cuccaro_mod(a_reg, b_reg)

Apply an optimized modular Cuccaro ripple-carry adder.

This circuit performs in-place modular addition of a_reg into b_reg:

|a>|b> -> |a>|a + b mod 2^n>

The circuit has linear depth and requires one ancilla qubit.

This is the modular case of adder_ripple_cuccaro_carry_out.

Reference: Cuccaro, Steven A., et al. “A new quantum ripple-carry addition circuit.” arXiv preprint quant-ph/0410184 (2004).

Parameters:

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg += a_reg mod 2^n.

guppyalgos.primitives.arithmetic.adder_ripple_cuccaro_mod_dagger(a_reg, b_reg)

Apply the inverse of the Cuccaro ripple-carry modular adder circuit.

This circuit is the inverse of the Cuccaro ripple-carry adder. It computes b - a in place on b_reg:

|a>|b + a mod 2^n> -> |a>|b>

The circuit has linear depth and requires one ancilla qubit.

TODO: Rewrite using CNOT ladders and Toffoli ladders. This adder does not necessarily have linear depth, it depends on the choice of ladders.

Reference: Cuccaro, Steven A., et al. “A new quantum ripple-carry addition circuit.” arXiv preprint quant-ph/0410184 (2004).

Parameters:

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg -= a_reg mod 2^n.

guppyalgos.primitives.arithmetic.adder_ripple_gidney_carry_out(a_reg, b_reg, carry_out)

Apply a Gidney non-modular ripple-carry adder.

The circuit implements the transformation:

|a>|b>|0> -> |a>|b + a mod 2^n>|carry_out>

Parameters:

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg += a_reg mod 2^n.

  • carry_out (qubit) – Qubit that is flipped if the addition produces a final carry out.

guppyalgos.primitives.arithmetic.adder_ripple_gidney_carry_out_dagger(a_reg, b_reg, carry_out)

Apply the dagger of the non-modular Gidney ripple-carry adder.

The circuit implements the transformation:

|a>|b + a mod 2^n>|carry_out> -> |a>|b>|0>

Parameters:

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg += a_reg mod 2^n.

  • carry_out (qubit) – Qubit that is flipped iff the subtraction produces a final borrow (i.e. iff b < a).

guppyalgos.primitives.arithmetic.adder_ripple_gidney_mod(a_reg, b_reg)

Apply a modular Gidney ripple-carry adder.

This circuit performs in-place modular addition of a_reg into b_reg:

|a>|b> -> |a>|a + b mod 2^n>

The circuit has linear depth and requires n - 1 ancilla qubits.

Reference: Gidney, C. (2018). Halving the cost of quantum addition. Quantum, 2, 74.

Parameters:

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg += a_reg mod 2^n.

guppyalgos.primitives.arithmetic.adder_ripple_gidney_mod_dagger(a_reg, b_reg)

Apply the inverse of the modular Gidney ripple-carry adder.

This circuit performs subtraction of a_reg from b_reg and computes the final borrow bit:

|a>|b + a mod 2^n> -> |a>|b>

The circuit has linear depth and requires n - 1 ancilla qubits.

Reference: Gidney, C. (2018). Halving the cost of quantum addition. Quantum, 2, 74.

Parameters:

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg -= a_reg mod 2^n.

guppyalgos.primitives.arithmetic.cntrl_adder_ripple_cuccaro_carry_out(ctrl, a_reg, b_reg, carry_out)

Apply a controlled optimized Cuccaro ripple-carry adder.

The circuit implements the transformation:

|ctrl>|a>|b>|0> -> |ctrl>|a>|b + ctrl * a mod 2^n>|ctrl * carry_out>

The circuit requires one ancilla qubit. The circuit’s depth depends on the supplied ladder implementations.

Reference: Cuccaro, Steven A., et al. “A new quantum ripple-carry addition circuit.” arXiv preprint quant-ph/0410184 (2004).

Parameters:

  • ctrl (qubit) – The control qubit.

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg += a_reg mod 2^n.

  • carry_out (qubit) – Qubit that is flipped if the addition produces a final carry out.

guppyalgos.primitives.arithmetic.cntrl_adder_ripple_cuccaro_carry_out_dagger(ctrl, a_reg, b_reg, carry_out)

Apply the inverse of the controlled Cuccaro ripple-carry adder.

Computes b - a in place on b_reg conditioned on the control qubit while restoring a_reg. The supplied borrow_out qubit is treated as the carry-out qubit from the forward adder and is uncomputed by the inverse operation.

Transformation:

|ctrl>|a>|b + ctrl * a mod 2^n>|ctrl * carry_out> -> |ctrl>|a>|b>|0>

The circuit has linear depth and requires one ancilla qubit.

TODO: Rewrite using CNOT ladders and Toffoli ladders. This adder does not necessarily have linear depth, it depends on the choice of ladders.

Reference: Cuccaro, Steven A., et al. “A new quantum ripple-carry addition circuit.” arXiv preprint quant-ph/0410184 (2004).

Parameters:

  • ctrl (qubit) – The control qubit.

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg -= a_reg mod 2^n.

  • carry_out (qubit) – Carry/borrow qubit to uncompute.

guppyalgos.primitives.arithmetic.cntrl_adder_ripple_cuccaro_mod(ctrl, a_reg, b_reg)

Apply a controlled optimized modular Cuccaro ripple-carry adder.

The circuit implements the transformation:

|ctrl>|a>|b> -> |ctrl>|a>|b + ctrl * a mod 2^n>

The circuit requires one ancilla qubit. The circuit’s depth depends on the supplied ladder implementations.

This is the modular variant of cntrl_adder_ripple_cuccaro_carry_out.

Reference: Cuccaro, Steven A., et al. “A new quantum ripple-carry addition circuit.” arXiv preprint quant-ph/0410184 (2004).

Parameters:

  • ctrl (qubit) – The control qubit.

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg += a_reg mod 2^n.

guppyalgos.primitives.arithmetic.cntrl_adder_ripple_cuccaro_mod_dagger(ctrl, a_reg, b_reg)

Apply the inverse of the controlled optimized modular Cuccaro ripple-carry adder.

The circuit implements the transformation:

|ctrl>|a>|b + ctrl * a mod 2^n> -> |ctrl>|a>|b>

The circuit requires one ancilla qubit. The circuit’s depth depends on the supplied ladder implementations.

This is the modular variant of cntrl_adder_ripple_cuccaro_carry_out.

Reference: Cuccaro, Steven A., et al. “A new quantum ripple-carry addition circuit.” arXiv preprint quant-ph/0410184 (2004).

Parameters:

  • ctrl (qubit) – The control qubit.

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg += a_reg mod 2^n.

guppyalgos.primitives.arithmetic.cntrl_adder_ripple_gidney_carry_out(ctrl, a_reg, b_reg, carry_out)

Apply a controlled Gidney ripple-carry adder.

The circuit implements the transformation:

|ctrl>|a>|b>|0> -> |ctrl>|a>|b + ctrl * a mod 2^n>|ctrl * carry_out>

Parameters:

  • ctrl (qubit) – The control qubit.

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg += a_reg mod 2^n.

  • carry_out (qubit) – Qubit that is flipped if the addition produces a final carry out.

guppyalgos.primitives.arithmetic.cntrl_adder_ripple_gidney_carry_out_dagger(ctrl, a_reg, b_reg, carry_out)

Apply the dagger of the controlled Gidney ripple-carry adder.

The circuit implements the transformation:

|ctrl>|a>|b + ctrl * a mod 2^n>|ctrl * carry_out> -> |ctrl>|a>|b>|0>

Parameters:

  • ctrl (qubit) – The control qubit.

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg += a_reg mod 2^n.

  • carry_out (qubit) – Qubit that is flipped iff the subtraction produces a final borrow (i.e. iff b < a).

guppyalgos.primitives.arithmetic.cntrl_adder_ripple_gidney_mod(ctrl, a_reg, b_reg)

Apply a controlled modular Gidney ripple-carry adder.

The circuit implements the transformation:

|ctrl>|a>|b> -> |ctrl>|a>|b + ctrl * a mod 2^n>

Implements the controlled modular addition circuit from Figure 4 of https://quantum-journal.org/papers/q-2018-06-18-74/pdf/.

Each intermediate bit gadget costs 8T gates: one temp_and_compute for the carry and one temporary logical-AND pair in the backward pass for the controlled addend contribution.

Parameters:

  • ctrl (qubit) – The control qubit.

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg += a_reg mod 2^n.

guppyalgos.primitives.arithmetic.cntrl_adder_ripple_gidney_mod_dagger(ctrl, a_reg, b_reg)

Apply the dagger of the controlled modular Gidney ripple-carry adder.

The circuit implements the transformation:

|ctrl>|a>|b + ctrl * a mod 2^n> -> |ctrl>|a>|b>

Implements the inverse of the controlled modular addition circuit from Figure 4 of https://quantum-journal.org/papers/q-2018-06-18-74/pdf/.

Parameters:

  • ctrl (qubit) – The control qubit.

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg += a_reg mod 2^n.

guppyalgos.primitives.arithmetic.cntrl_multiplier_ripple_gidney_mod(ctrl, a_reg, b_reg, product)

Conditionally multiply a_reg by b_reg into product modulo 2**n.

Performs the transformation: |ctrl⟩|a⟩|b⟩|p⟩ → |ctrl⟩|a⟩|b⟩|p + ctrl * a * b mod 2**n⟩

This implements the standard shift-and-add decomposition:

product += ctrl * b_reg[i] * (a_reg << i) mod 2**n

for each bit position i of the multiplier register. The global control ctrl gates the entire multiplication: if ctrl is 0, the product is left unchanged.

Parameters:

  • ctrl – Global control qubit.

  • a_reg – Multiplicand register.

  • b_reg – Multiplier register. Each bit controls the corresponding shifted addend.

  • product – Accumulator register, updated modulo 2**n.

guppyalgos.primitives.arithmetic.cntrl_multiplier_ripple_gidney_mod_in_place(ctrl, a_reg, b)

Conditionally multiply a_reg by the odd classical constant b in-place.

Performs |ctrl>|a> -> |ctrl>|b * a mod 2**n> when ctrl is set and acts as the identity otherwise. Since multiplication modulo 2**n is invertible only for odd multipliers, b must be odd.

Parameters:

  • ctrl – Control qubit.

  • a_reg – Register modified in-place when ctrl is set.

  • b – Odd classical multiplier.

Raises:

ValueError – If b is even.

guppyalgos.primitives.arithmetic.cntrl_subtractor_ripple_cuccaro_carry_out(ctrl, a_reg, b_reg, borrow_out)

Apply a controlled Cuccaro ripple-carry subtraction circuit.

This circuit is the inverse of the Cuccaro ripple-carry adder. It computes b - a in place on b_reg, conditioned on the control qubit:

|ctrl>|a>|b>|0> -> |ctrl>|a>|b - ctrl * a mod 2^n>|ctrl * borrow_out>

For unsigned integers, borrow_out is flipped iff b < a.

The circuit has linear depth and requires one ancilla qubit.

TODO: Rewrite using CNOT ladders and Toffoli ladders. This adder does not necessarily have linear depth, it depends on the choice of ladders.

Reference: Cuccaro, Steven A., et al. “A new quantum ripple-carry addition circuit.” arXiv preprint quant-ph/0410184 (2004).

Parameters:

  • ctrl (qubit) – The control qubit.

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg -= a_reg mod 2^n.

  • borrow_out (qubit) – Clean output qubit receiving the final borrow bit. This is flipped iff b < a.

guppyalgos.primitives.arithmetic.cntrl_subtractor_ripple_cuccaro_mod(ctrl, a_reg, b_reg)

Apply a controlled Cuccaro ripple-carry modular subtraction circuit.

This circuit is the inverse of the controlled Cuccaro ripple-carry modular adder. It computes b - a in place on b_reg, conditioned on the control qubit:

|ctrl>|a>|b> -> |ctrl>|a>|b - ctrl * a mod 2^n>

The circuit has linear depth and requires one ancilla qubit.

TODO: Rewrite using CNOT ladders and Toffoli ladders. This adder does not necessarily have linear depth, it depends on the choice of ladders.

Reference: Cuccaro, Steven A., et al. “A new quantum ripple-carry addition circuit.” arXiv preprint quant-ph/0410184 (2004).

Parameters:

  • ctrl (qubit) – The control qubit.

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg -= a_reg mod 2^n.

guppyalgos.primitives.arithmetic.cntrl_subtractor_ripple_gidney_carry_out(ctrl, a_reg, b_reg, borrow_out)

Apply a controlled Gidney ripple-carry subtraction circuit.

This circuit is the inverse of the Gidney ripple-carry adder. It computes b - a in place on b_reg, conditioned on the control qubit:

|ctrl>|a>|b>|0> -> |ctrl>|a>|b - ctrl * a mod 2^n>|ctrl * borrow_out>

For unsigned integers, borrow_out is flipped iff b < a.

Reference: Gidney, C. (2018). Halving the cost of quantum addition. Quantum, 2, 74.

Parameters:

  • ctrl (qubit) – The control qubit.

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg -= a_reg mod 2^n.

  • borrow_out (qubit) – Clean output qubit receiving the final borrow bit. This is flipped iff b < a.

guppyalgos.primitives.arithmetic.cntrl_subtractor_ripple_gidney_mod(ctrl, a_reg, b_reg)

Apply a controlled Gidney ripple-carry modular subtraction circuit.

This circuit is the inverse of the controlled Gidney ripple-carry modular adder. It computes b - a in place on b_reg, conditioned on the control qubit:

|ctrl>|a>|b> -> |ctrl>|a>|b - ctrl * a mod 2^n>

Reference: Gidney, C. (2018). Halving the cost of quantum addition. Quantum, 2, 74.

Parameters:

  • ctrl (qubit) – The control qubit.

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg -= a_reg mod 2^n.

guppyalgos.primitives.arithmetic.compute_and(q0, q1, t_qubit)

Temporary AND computation acting on 0 state target.

Following the construction in https://arxiv.org/abs/1805.03662 which uses 4 T-gates.

Parameters:

  • q0 (qubit) – The first input qubit.

  • q1 (qubit) – The second input qubit.

  • t_qubit (qubit) – The target qubit to store the result. Begins in \(\ket{0}\)

guppyalgos.primitives.arithmetic.exponentiator_ripple_gidney_mod(exponent_reg, output_reg, base)

Multiply the output register by base^exponent modulo 2**n_output.

Base must be odd since the multiplication is performed in-place, and multiplication modulo 2**n_output requires an odd multiplicand for reversibility.

Explicitly, performs the transformation |x⟩|a⟩ → |x⟩|a * base^x mod 2**n_output⟩.

Parameters:

  • exponent_reg – Quantum register holding the exponent.

  • output_reg – Quantum register to store the result. Typically initialized to |1⟩.

  • base – Classical base to be exponentiated.

Raises:

ValueError – If the base is negative or even.

guppyalgos.primitives.arithmetic.multiplier_ripple_gidney_mod(a_reg, b_reg, product)

Add the product of a_reg and b_reg into product modulo 2**n.

Performs the transformation: |a⟩|b⟩|p⟩ -> |a⟩|b⟩|p + a * b mod 2**n⟩

This implements the standard shift-and-add decomposition:

product += b_reg[i] * (a_reg << i) mod 2**n

for each bit position i of the multiplier register.

Parameters:

  • a_reg – Multiplicand register.

  • b_reg – Multiplier register. Each bit controls the corresponding shifted addend.

  • product – Accumulator register, updated modulo 2**n.

guppyalgos.primitives.arithmetic.multiplier_ripple_gidney_mod_in_place(a_reg, b)

Multiply a_reg by the odd classical constant b in-place.

Performs |a> -> |b * a mod 2**n>. Since multiplication modulo 2**n is invertible only for odd multipliers, b must be odd.

Let M = 2**n. The compute-swap-uncompute construction acts as (a, 0) -> (a, ba) -> (ba, a) -> (ba, a - b^{-1}(ba)) = (ba, 0) (mod M).

Parameters:

  • a_reg – Register modified in-place.

  • b – Odd classical multiplier.

Raises:

ValueError – If b is even.

guppyalgos.primitives.arithmetic.subtractor_ripple_cuccaro_carry_out(a_reg, b_reg, borrow_out)

Apply a Cuccaro ripple-carry subtraction circuit.

This circuit is the inverse of the Cuccaro ripple-carry adder. It computes b - a in place on b_reg:

|a>|b>|0> -> |a>|b - a mod 2^n>|borrow_out>

For unsigned integers, borrow_out is flipped iff b < a.

The circuit has linear depth and requires one ancilla qubit.

TODO: Rewrite using CNOT ladders and Toffoli ladders. This adder does not necessarily have linear depth, it depends on the choice of ladders.

Reference: Cuccaro, Steven A., et al. “A new quantum ripple-carry addition circuit.” arXiv preprint quant-ph/0410184 (2004).

Parameters:

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg -= a_reg mod 2^n.

  • borrow_out (qubit) – Clean output qubit receiving the final borrow bit. This is flipped iff b < a.

guppyalgos.primitives.arithmetic.subtractor_ripple_cuccaro_mod(a_reg, b_reg)

Apply a Cuccaro ripple-carry modular subtraction circuit.

This circuit is the inverse of the Cuccaro ripple-carry adder. It computes b - a in place on b_reg:

|a>|b> -> |a>|b - a mod 2^n>

The circuit has linear depth and requires one ancilla qubit.

TODO: Rewrite using CNOT ladders and Toffoli ladders. This adder does not necessarily have linear depth, it depends on the choice of ladders.

Reference: Cuccaro, Steven A., et al. “A new quantum ripple-carry addition circuit.” arXiv preprint quant-ph/0410184 (2004).

Parameters:

  • ctrl (qubit) – The control qubit.

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg -= a_reg mod 2^n.

guppyalgos.primitives.arithmetic.subtractor_ripple_gidney_carry_out(a_reg, b_reg, borrow_out)

Apply a Gidney ripple-carry subtraction circuit.

This circuit is the inverse of the Gidney ripple-carry adder. It computes b - a in place on b_reg:

|a>|b>|0> -> |a>|b - a mod 2^n>|borrow_out>

For unsigned integers, borrow_out is flipped iff b < a.

The circuit has linear depth and requires one ancilla qubit.

Reference: Gidney, C. (2018). Halving the cost of quantum addition. Quantum, 2, 74.

Parameters:

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg -= a_reg mod 2^n.

  • borrow_out (qubit) – Clean output qubit receiving the final borrow bit. This is flipped iff b < a.

guppyalgos.primitives.arithmetic.subtractor_ripple_gidney_mod(a_reg, b_reg)

Apply a Gidney ripple-carry modular subtraction circuit.

This circuit is the inverse of the Gidney ripple-carry adder. It computes b - a in place on b_reg:

|a>|b> -> |a>|b - a mod 2^n>

The circuit has linear depth and requires one ancilla qubit.

Reference: Gidney, C. (2018). Halving the cost of quantum addition. Quantum, 2, 74.

Parameters:

  • a_reg (array[qubit, n]) – The addend register.

  • b_reg (array[qubit, n]) – The target register. Modified in-place: b_reg -= a_reg mod 2^n.

guppyalgos.primitives.arithmetic.uncompute_and(q_0, q_1, target_q)

Uncompute the logical AND operation.

This function reverses the effects of the logical AND operation applied to the input qubits and the target qubit. It is equivalent to measurement based uncomputation as described in Fig 4. https://arxiv.org/pdf/1805.03662. The qubit must be discarded after use.

Parameters:

  • q_0 (qubit) – The first input qubit.

  • q_1 (qubit) – The second input qubit.

  • target_q (qubit) – The auxiliary qubit used in computation.