Given a target arithmetic primitive (e.g., modular inverse, point addition) whose naive quantum implementation stores every intermediate variable in its own register, apply this reduction pattern:

1. Find an algebraic invariant linking the variables (e.g., Rt + rT = p in the extended Euclidean algorithm, or Hua's identity linking multiplication to inversion). Use it to store only the minimum spanning subset of variables and reconstruct the rest on demand via arithmetic queries.
2. Implement those on-demand queries as arithmetic oracles using digit/windowed evaluation plus measurement-based uncomputation (spooky pebbling), so temporary work is recycled in o(n) ancillas instead of O(n).
3. Replace expensive operations (variable-variable multiplication, squaring) with sequences of the cheap primitive you've already minimized (e.g., express multiplication via 5 calls to inversion using Hua's identity), trading gate count for qubit count only when the cheap primitive is asymptotically cheap in gates too.
4. Compute exact qubit/gate bounds by summing: (persistent state) + (temporary oracle workspace, sublinear) + (O(1) control/flag qubits).

Progress:

• Step 1: Identify all state variables and any algebraic identity relating them (look for invariants like Bézout's identity, Hua's identity, or determinant relations)
• Step 2: Determine which variables must persist between operations vs. which can be recomputed from an identity
• Step 3: Design the register layout — pack persisted variables into a small number of registers, using length/layout metadata registers (O(log n) bits) to track which representation is active
• Step 4: Partition the algorithm into intervals/scales (e.g., "small" vs "large" quotient steps) so each interval has an input-independent (oblivious) schedule
• Step 5: Build a classical windowed evaluator for constant-depth arithmetic expressions (digit-by-digit scan, Newton iteration for division/inversion) with sublinear working memory
• Step 6: Convert each evaluator into a quantum arithmetic oracle via measurement-based uncomputation (segment the computation, use Hadamard-basis measurement + phase correction)
• Step 7: Prove exactness — every temporary value used in an update must be recoverable from the post-update state, so it can be uncomputed and erased
• Step 8: Compose all pieces per Definition-of-exactness (Kraus operator factors into α_μ · U) and sum resource costs
• Step 9: Verify disjointness of "target regions" (cells being overwritten) from all preserved subregisters, across every intermediate state, not just endpoints

Example 1: Input: A quantum circuit stores all four EEA quantities (R, r, T, t) explicitly, using ~4n qubits, and needs to be shrunk. Output: Use the invariant Rt + rT = p to store only three of the four (e.g., pick layout (r,T;t) early and (R,t;r) late, switching once when t crosses 2^(n/2)), reconstructing the fourth via a division query R = (p - rT)/t. This drops the persistent state to 3n/2 + o(n) qubits. Temporary quotients/matrices generated during updates are recomputed from the updated state and erased, never stored persistently.

Example 2: Input: Need to multiply two variable field elements X, Y while only having a cheap in-place inverter available, without allocating a full second n-qubit multiplier register. Output: Apply Hua's identity a - (a^-1 + (b^-1 - a)^-1)^-1 = aba to express the map (X,Y) -> (X, X²Y) as five sequential calls to the inverter plus O(1) additions, reusing the same inverter workspace each time. Handle the constant-size exceptional set (where an inverse is undefined) with a final small permutation correction (≤8 basis strings) computed classically and patched in via controlled XOR.

Example 3: Input: An oracle needs to XOR a bit-window of a large implicitly-represented product/quotient into a target, but only o(n) ancilla qubits are budgeted. Output: Build a classical oblivious evaluator (digit scan for products, Newton–Raphson halving recursion for division/inverse mod 2^m) that computes the window using O(w) working bits at a time (w = window scale), then wrap it in a spooky-pebbling schedule: split into T/S segments, run forward while measuring out and XORing checkpoints into a classical phase record, then recompute-and-correct backward with classically-controlled Z gates. Net cost: O(S) ancillas, O(T²/S + T) Toffolis.