Reversibility

Kettle provides unified reversibility for quantum and classical code. This enables automatic uncomputation, the compute block pattern, and bidirectional programming.

Why Reversibility?

The problem with regular assignment:

x = 5      -- What was x before? Lost forever.
x = x + 1  -- Same problem - old value destroyed.

Regular assignment destroys information. Once you overwrite a value, you can't recover what was there before. This matters for:

• Quantum computing: Qubits must be "uncomputed" (returned to |0⟩) before being discarded, or information leaks into the environment
• Reversible algorithms: Some algorithms need to run backwards (cryptography, optimization, debugging)
• Resource efficiency: Landauer's principle - erasing information costs energy

The solution - reversible operations:

x += 1     -- Inverse: x -= 1
x ^= mask  -- Inverse: x ^= mask (XOR is self-inverse)
x <-> y    -- Inverse: x <-> y (swap is self-inverse)

These operations preserve information. Given the output, you can always reconstruct the input.

Reversible Operations

Classical Operations

Operation	Meaning	Inverse
x += e	Add e to x	x -= e
x -= e	Subtract e from x	x += e
x ^= e	XOR x with e	x ^= e (self-inverse)
x *= c	Multiply x by constant c (Float only)	x /= c
x /= c	Divide x by constant c (Float only)	x *= c
x <-> y	Swap x and y	x <-> y (self-inverse)

Quantum Operations

All quantum gates are reversible (except measurement):

• Single-qubit: hadamard, pauli_x, pauli_y, pauli_z, s_gate, t_gate
• Rotations: rx(θ), ry(θ), rz(θ)
• Multi-qubit: cnot, cz, swap, ccnot (Toffoli)

Not reversible: measure - collapses quantum state, destroying superposition information.

Quantum Gate Inverses

Many quantum gates have explicit adjoint (inverse) versions:

Gate	Inverse
hadamard	hadamard (self-inverse)
pauli_x, pauli_y, pauli_z	self-inverse
s_gate	s_gate_dag
t_gate	t_gate_dag
rx(θ)	rx(-θ)
ry(θ)	ry(-θ)
rz(θ)	rz(-θ)

fn apply_and_undo(q: Qubit) -> Qubit with Quantum
  q <- hadamard     -- Apply H
  q <- hadamard     -- Undo H (H is self-inverse)

  q <- t_gate       -- Apply T
  q <- t_gate_dag   -- Undo T

  q <- rx(1.57)     -- Rotate by θ
  q <- rx(-1.57)    -- Rotate by -θ (undo)
  q
end fn

The Compute Block

The compute block provides automatic uncomputation. Operations on the compute variable are tracked and automatically reversed when the block exits.

result = compute with temp = initial_value
  -- operations on temp are tracked
  temp += something
  temp *= 2
  temp  -- last expression is returned
end compute  -- temp operations automatically reversed

How It Works

1. Initialize: Create the compute variable with initial value
2. Execute: Run the body, logging reversible operations on the compute variable
3. Capture: The last expression becomes the return value
4. Uncompute: Replay logged operations in reverse order
5. Cleanup: The compute variable goes out of scope

fn example() -> Int
  result = compute with temp = 0
    temp += 10       -- logged
    temp += 20       -- logged (temp = 30)
    temp             -- return value: 30
  end compute        -- uncompute: temp -= 20, temp -= 10

  result  -- 30
end fn

Extracting Results

Operations on the compute variable are undone. Operations on other variables persist:

fn extract_result() -> Int
  output = 0

  compute with x = 5
    x += 10          -- logged (x = 15)
    output += x      -- NOT logged (output is not the compute variable)
    x *= 2           -- logged (x = 30)
    x                -- return value
  end compute        -- uncompute: x /= 2, x -= 10 (x back to 5)

  output  -- 15 (persisted)
end fn

This is the "compute-copy-uncompute" pattern from quantum computing: compute a value, copy out what you need, then uncompute to clean up.

Scope Isolation

The compute variable exists only inside the block:

fn scoped() -> Int
  compute with temp = 42
    temp + 1
  end compute

  -- temp is not accessible here
  -- temp  -- Error: undefined variable
  0
end fn

Control Flow

Conditionals and loops work inside compute blocks. The operation log captures whatever actually executes:

fn conditional(flag: Bool) -> Int
  compute with x = 0
    match flag
      True -> x += 100   -- logged only if flag is True
      False -> x += 50   -- logged only if flag is False
    end match
    x
  end compute
end fn

fn with_loop() -> Int
  compute with counter = 0
    for i in [1, 2, 3]
      counter += i       -- logged 3 times
    end for
    counter              -- 6
  end compute            -- uncompute: counter -= 3, -= 2, -= 1
end fn

Classical Example: Temporary Computation

fn distance_squared(x1: Int, y1: Int, x2: Int, y2: Int) -> Int
  compute with dx = 0, dy = 0
    dx += x2
    dx -= x1
    dy += y2
    dy -= y1
    dx * dx + dy * dy
  end compute
end fn

Multiple variables can be tracked in a single compute block using comma-separated syntax, avoiding the need for nesting.

Quantum Example: Ancilla Pattern

fn controlled_phase(control: Qubit, target: Qubit) -> Tuple[Qubit, Qubit] with Quantum
  compute with ancilla = qubit()
    ancilla <- pauli_x
    (ancilla, target) <- cnot
    (control, ancilla) <- cz
  end compute  -- ancilla uncomputed and implicitly discarded

  (control, target)
end fn

The Reversible Capability

Mark a function is Reversible to enforce that only reversible operations are used:

fn transform(x: Int, y: Int) -> Tuple[Int, Int] is Reversible
  x += y      -- inverse: x -= y
  x -= 3      -- inverse: x += 3
  x ^= y      -- self-inverse
  (x, y)
end fn

The compiler rejects non-reversible operations:

fn bad(x: Int) -> Int is Reversible
  x = 5  -- Error: assignment destroys information, use compound assignment
  x
end fn

Summary

Feature	Purpose
Compound assignments (+=, -=, ^=)	Reversible alternatives to assignment (Int or Float)
*=, /=	Reversible multiply/divide (Float only - Int division loses info)
x <-> y	Reversible swap
_dag gates (s_gate_dag, t_gate_dag)	Explicit gate inverses
compute with x = a, y = b ... end compute	Auto-uncompute temporary values
is Reversible	Enforce reversibility at compile time