Arithmetic Circuits and Modular Thinking

Many quantum algorithms involve arithmetic operations. This chapter teaches you to think about quantum arithmetic as reversible basis-state transformations.

The Reversibility Constraint

Classical arithmetic often loses information:

AND: 2 inputs → 1 output
Addition can overflow

Quantum arithmetic must be reversible:

Use ancilla qubits for results
Preserve inputs (or uncompute them)

Basis State Mapping

Design arithmetic circuits by thinking about basis states:

Operation	Mapping
SWAP	\(
Increment	\(
Add constant	\(

SWAP: The Simplest Arithmetic Circuit

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector

# SWAP |xy⟩ → |yx⟩
qc = QuantumCircuit(2)
qc.swap(0, 1)

# Test on all inputs
for bits in ['00', '01', '10', '11']:
    qc_test = QuantumCircuit(2)
    for i, b in enumerate(reversed(bits)):
        if b == '1':
            qc_test.x(i)
    qc_test.compose(qc, inplace=True)
    print(f"{bits} → {Statevector(qc_test)}")

Increment

Adding 1 modulo \(2^n\):

def increment(n):
    """Create a circuit that adds 1 modulo 2^n."""
    qc = QuantumCircuit(n)
    for i in range(n-1, 0, -1):
        qc.mcx(list(range(i)), i)
    qc.x(0)
    return qc

# Test on 2 qubits
inc = increment(2)
for bits in ['00', '01', '10', '11']:
    qc_test = QuantumCircuit(2)
    for i, b in enumerate(reversed(bits)):
        if b == '1':
            qc_test.x(i)
    qc_test.compose(inc, inplace=True)
    print(f"{bits}+1 = {Statevector(qc_test)}")

Addition in the Fourier Basis

Addition becomes phase rotation in the Fourier basis:

# Add k in Fourier basis
def add_fourier(k, n):
    qc = QuantumCircuit(n)
    for i in range(n):
        qc.p(2*pi*k/(2**(i+1)), i)
    return qc

This is more efficient than computational basis addition.

Modular Arithmetic

Many quantum algorithms require modular arithmetic (operations modulo \(N\)):

\[x + y \pmod{N}\]

Key property: all operations wrap around at \(N\).

# Modular addition: (x + k) mod 4
def add_mod_4(k):
    qc = QuantumCircuit(2)
    inc = increment(2)
    for _ in range(k % 4):
        qc.compose(inc, inplace=True)
    return qc

Design Patterns

Pattern 1: Start with Basis States

Before writing gates, write the intended mapping:

|w⟩ → |w⟩    (identity)
|w⟩ → |f(w)⟩ (transformation)

Pattern 2: Test Exhausively

For small circuits, test all possible inputs:

def test_circuit(circuit, n_qubits, expected_mapping):
    for i in range(2**n_qubits):
        qc = QuantumCircuit(n_qubits)
        # Prepare basis state |i⟩
        for j in range(n_qubits):
            if (i >> j) & 1:
                qc.x(j)
        qc.compose(circuit, inplace=True)
        state = Statevector(qc)
        # Check result