org.soulspace.qclojure.application.algorithm.quantum-arithmetic — org.soulspace/qclojure 0.4.0

Production-ready quantum arithmetic circuits with minimal resource usage.

This namespace provides a complete suite of quantum arithmetic operations needed for algorithms like Shor's factoring, quantum period finding, and other cryptographic quantum algorithms.

This implementation focuses on:

• Minimal qubit usage (qubits are sparse resources)
• Correct quantum arithmetic from the start
• Proper testing at each level
• Production-ready code that will work on real quantum hardware

All circuits are designed to be:

• Reversible (essential for quantum computation)
• Resource-efficient (minimizing ancilla qubits)
• Fault-tolerant ready (structured for error correction)
• Modular and composable

controlled-modular-exponentiation clj

(controlled-modular-exponentiation circuit
                                   exponent-qubits
                                   base
                                   modulus
                                   result-qubits
                                   ancilla-qubits)

Controlled modular exponentiation for quantum period finding.

Computes result := base^exponent mod N with quantum controls using binary exponentiation. This implementation uses precomputed powers to minimize quantum operations.

Algorithm (Binary Exponentiation):

1. Precompute all powers base^(2^k) mod N classically
2. For each exponent bit k:
   • If bit k is |1⟩, multiply result by base^(2^k) mod N
   • Use controlled modular multiplication

This is much more efficient than repeated squaring in quantum domain.

Parameters:

• circuit: quantum circuit
• exponent-qubits: qubits representing exponent (control qubits)
• base: classical base value
• modulus: classical modulus value
• result-qubits: qubits to store result (initially |1⟩)
• ancilla-qubits: ancilla qubits for computation

Returns: Modified quantum circuit with controlled modular exponentiation applied

controlled-modular-exponentiation-circuit clj

(controlled-modular-exponentiation-circuit n-exp-qubits
                                           n-result-qubits
                                           base
                                           modulus
                                           &
                                           [circuit-name])

Create a complete controlled modular exponentiation circuit for QPF.

Factory function with conservative resource allocation for production use. Uses the optimized binary exponentiation algorithm for better performance.

Parameters:

• n-exp-qubits: number of qubits for exponent register
• n-result-qubits: number of qubits for result register
• base: classical base value
• modulus: classical modulus value
• circuit-name: optional name for the circuit

Returns: A quantum circuit ready for use in period finding algorithms

controlled-modular-multiplication clj

(controlled-modular-multiplication circuit
                                   control
                                   multiplier
                                   operand-qubits
                                   result-qubits
                                   modulus
                                   ancilla-qubits)

Controlled modular multiplication using repeated modular addition.

Performs result := (result × multiplier) mod N when control is |1⟩. Uses proper quantum modular arithmetic with classical multiplier decomposition.

Algorithm:

1. For each bit i of multiplier (from LSB to MSB):
   • If bit i is set, conditionally add (operand × 2^i) mod N to result
   • Use controlled modular addition for each power of 2

This implementation uses classical preprocessing to reduce quantum resources.

Parameters:

• circuit: quantum circuit
• control: control qubit
• multiplier: classical multiplier value
• operand-qubits: qubits representing operand to multiply
• result-qubits: qubits representing the result (modified in place)
• modulus: classical modulus value
• ancilla-qubits: ancilla qubits for computation (need at least 4n)

Returns: Modified quantum circuit with controlled modular multiplication applied

controlled-quantum-subtractor clj

(controlled-quantum-subtractor circuit control a-qubits b-qubits ancilla-qubits)

Production-ready controlled quantum subtractor: if control=|1⟩, compute a := a - b.

Performs controlled subtraction using two's complement arithmetic when control qubit is |1⟩. If control=|0⟩, leaves a unchanged. Uses proper quantum controlled operations.

Algorithm:

1. If control=|1⟩, flip all bits of b (controlled bit flip)
2. If control=|1⟩, add 1 to b (controlled increment)
3. Perform quantum addition a + b (now b is ~b+1 if control=|1⟩)

This implements controlled subtraction: a - b = a + (~b + 1) when control=|1⟩

Parameters:

• circuit: quantum circuit
• control: control qubit (subtraction happens only if |1⟩)
• a-qubits: minuend qubits (result stored here)
• b-qubits: subtrahend qubits (temporarily modified, then restored)
• ancilla-qubits: ancilla qubits (need at least 2n+2 qubits)

Returns: Modified quantum circuit with controlled subtraction applied

create-quantum-arithmetic-circuit clj

(create-quantum-arithmetic-circuit operation-type n-bits & [options])

Factory function to create optimized quantum arithmetic circuits.

Provides a high-level interface for creating production-ready arithmetic circuits with proper resource allocation and optimization hints.

Parameters:

• operation-type: type of arithmetic operation (:add, :multiply, :mod-exp, etc.)
• n-bits: number of bits for operands
• options: optional parameters map

Returns: A complete quantum circuit ready for execution

estimate-auxiliary-qubits clj

(estimate-auxiliary-qubits n-bits operation)

Estimate auxiliary qubits needed for quantum arithmetic operations.

Conservative estimates to ensure operations work on real hardware.

Parameters:

• n-bits: number of bits in operands
• operation: type of operation (:addition, :multiplication, :exponentiation, :comparison, :modular-addition)

Returns: Number of auxiliary qubits needed

estimate-gate-count clj

(estimate-gate-count operation n-bits)

Estimate gate count for quantum arithmetic operations.

Used for quantum resource estimation and optimization.

Parameters:

• operation: type of operation
• n-bits: number of bits

Returns: Estimated gate count

optimize-circuit-depth clj

(optimize-circuit-depth circuit)

Optimize circuit depth by parallelizing independent operations.

This function would implement circuit optimization strategies for real hardware. For now, it returns the original circuit with metadata about optimization potential.

Parameters:

• circuit: quantum circuit to optimize

Returns: Optimized circuit with metadata

partition-ancilla-qubits clj

(partition-ancilla-qubits ancilla-qubits partitions)

Partition ancilla qubits for different uses with proper resource allocation.

Parameters:

• ancilla-qubits: vector of available ancilla qubit indices
• partitions: vector of [name count] pairs specifying how to partition

Returns: Map of partition-name -> qubit-vector

precompute-modular-powers clj

(precompute-modular-powers base modulus max-bits)

Precompute base^(2^k) mod N for all k from 0 to max-bits-1.

This classical preprocessing reduces quantum resource requirements.

Parameters:

• base: base value
• modulus: modulus N
• max-bits: maximum number of bits in exponent

Returns: Vector of precomputed values [base^1 mod N, base^2 mod N, base^4 mod N, ...]

quantum-adder-ripple-carry clj

(quantum-adder-ripple-carry circuit a-qubits b-qubits carry-qubits c-out)

Quantum ripple-carry adder with minimal resource usage.

Adds two n-bit numbers: |a⟩|b⟩|0⟩ → |a⟩|a+b mod 2^n⟩|c_out⟩

Resource usage:

• Input: 2n qubits (a, b registers)
• Ancilla: n+1 qubits (n carry qubits + 1 final carry)
• Total: 3n+1 qubits

Parameters:

• circuit: quantum circuit
• a-qubits: vector of qubits for first number (preserved)
• b-qubits: vector of qubits for second number (becomes sum)
• carry-qubits: vector of n ancilla qubits for carry propagation
• c-out: final carry output qubit

Returns: Modified quantum circuit with addition applied

quantum-carry clj

(quantum-carry circuit a b c_in c_out)

Quantum carry operation for ripple-carry addition.

Implements the reversible carry operation: |a⟩|b⟩|c_in⟩|c_out⟩ → |a⟩|b ⊕ a⟩|c_in ⊕ a⟩|c_out ⊕ (a∧b) ⊕ (a∧c_in) ⊕ (b∧c_in)⟩

This is the most fundamental building block for quantum addition. Uses exactly 3 gates: CNOT + Toffoli + CNOT

Parameters:

• circuit: quantum circuit
• a: first input qubit
• b: second input qubit
• c_in: carry input qubit
• c_out: carry output qubit

Returns: Modified quantum circuit with carry operation applied

quantum-carry-inverse clj

(quantum-carry-inverse circuit a b c_in c_out)

Inverse of quantum carry operation.

Undoes the carry operation for uncomputation. Uses exactly 3 gates in reverse order.

Parameters:

• circuit: quantum circuit
• a: first input qubit
• b: second input qubit
• c_in: carry input qubit
• c_out: carry output qubit

Returns: Modified quantum circuit with carry operation undone

quantum-comparator-less-than clj

(quantum-comparator-less-than circuit a-qubits n-qubits result ancilla-qubits)

Production-ready quantum comparator to check if a < N using quantum subtraction.

Sets result qubit to |1⟩ if a < N, |0⟩ otherwise. Uses quantum subtraction with borrow detection for correct comparison.

Algorithm:

1. Compute temp := a - N using quantum subtraction
2. Check borrow-out bit: if |1⟩ then a < N
3. Uncompute temp to restore original state
4. Copy borrow-out to result

Parameters:

• circuit: quantum circuit
• a-qubits: qubits representing number a
• n-qubits: qubits representing modulus N
• result: result qubit (set to |1⟩ if a < N)
• ancilla-qubits: ancilla qubits (need exactly 2*n + 1 qubits)

Returns: Modified quantum circuit with comparison result

quantum-incrementer clj

(quantum-incrementer circuit x-qubits ancilla-qubits)

Production-ready quantum incrementer: |x⟩ → |x+1 mod 2^n⟩.

Implements proper ripple-carry increment using quantum addition with constant 1. This is essential for two's complement arithmetic and proper quantum subtraction.

Algorithm:

1. Create a constant register |1⟩ in ancilla
2. Perform quantum addition: x + 1
3. Uncompute the constant register

Parameters:

• circuit: quantum circuit
• x-qubits: qubits to increment (modified in place)
• ancilla-qubits: ancilla qubits for carry propagation (need n+1 qubits)

Returns: Modified quantum circuit with increment applied

quantum-modular-adder clj

(quantum-modular-adder circuit a-qubits b-qubits n-qubits ancilla-qubits)

Quantum modular addition: (a + b) mod N.

Computes modular addition with minimal resource overhead. Resource usage: proper ancilla allocation for production use.

Parameters:

• circuit: quantum circuit
• a-qubits: first operand qubits
• b-qubits: second operand qubits (becomes result)
• n-qubits: modulus N qubits
• ancilla-qubits: ancilla qubits for computation (need at least 4n + 3)

Returns: Modified quantum circuit with modular addition applied

quantum-modular-multiplier clj

(quantum-modular-multiplier circuit
                            a-qubits
                            b-qubits
                            n-qubits
                            result-qubits
                            ancilla-qubits)

Quantum modular multiplication: (a × b) mod N.

Computes modular multiplication using quantum multiplication followed by modular reduction. This is a key building block for modular exponentiation.

Algorithm:

1. Compute temp := a × b using quantum multiplication
2. Reduce temp modulo N using repeated modular subtraction
3. Store result back to result-qubits

Parameters:

• circuit: quantum circuit
• a-qubits: first operand qubits (preserved)
• b-qubits: second operand qubits (preserved)
• n-qubits: modulus N qubits
• result-qubits: result qubits (n bits, becomes (a×b) mod N)
• ancilla-qubits: ancilla qubits (need at least 4n qubits)

Returns: Modified quantum circuit with modular multiplication result

quantum-multiplier-shift-add clj

(quantum-multiplier-shift-add circuit
                              a-qubits
                              b-qubits
                              product-qubits
                              ancilla-qubits)

Quantum multiplication using shift-and-add algorithm.

Computes product := a × b using repeated quantum addition.

Algorithm:

1. Initialize product to 0
2. For each bit i of multiplier b:
   • If bit i is set, add (a << i) to product
   • Use quantum controlled addition

This is the foundation for modular multiplication.

Parameters:

• circuit: quantum circuit
• a-qubits: multiplicand qubits (preserved)
• b-qubits: multiplier qubits (preserved)
• product-qubits: product result qubits (2n bits, initially |0⟩)
• ancilla-qubits: ancilla qubits for addition operations

Returns: Modified quantum circuit with multiplication result in product-qubits

quantum-subtractor clj

(quantum-subtractor circuit a-qubits b-qubits borrow-qubits borrow-out)

Production-ready quantum subtractor circuit.

Subtracts two n-bit numbers: |a⟩|b⟩ → |a⟩|a-b mod 2^n⟩ Uses proper two's complement arithmetic: a - b = a + (~b + 1)

This is a complete, production-ready quantum subtractor that:

1. Computes proper two's complement of b by flipping all bits
2. Uses production quantum incrementer to add 1
3. Performs quantum addition a + (~b + 1)
4. The borrow output indicates if a < b (important for comparisons)

Resource usage:

• Input: 2n qubits (a, b registers)
• Ancilla: 3n+2 qubits (n borrow qubits + n+1 for incrementer + 1 final borrow)
• Total: 5n+3 qubits

Parameters:

• circuit: quantum circuit
• a-qubits: qubits representing minuend (preserved)
• b-qubits: qubits representing subtrahend (becomes difference a-b)
• borrow-qubits: ancilla qubits for borrow propagation
• borrow-out: final borrow output qubit (|1⟩ if a < b)

Returns: Modified quantum circuit with subtraction applied

quantum-sum clj

(quantum-sum circuit a b c_in sum)

Quantum sum operation for addition circuits.

Computes sum bit: sum = a ⊕ b ⊕ c_in Uses exactly 3 CNOT gates.

Parameters:

• circuit: quantum circuit
• a: first input qubit
• b: second input qubit
• c_in: carry input qubit
• sum: sum output qubit

Returns: Modified quantum circuit with sum operation applied