Lemma: Record-retaining simulation

Suppose a hybrid procedure has polynomial worst-case time, polynomial workspace, computational-basis measurements, and a polynomial-time classical controller. Its quantum instructions come from the frozen alphabet. Then its classical-output distribution has a polynomial-size unitary implementation which retains polynomially many history and work qubits. The inverse is obtained by reversing the gate list and inverting the gates.

Proof. Replace a computational-basis measurement by CNOT copies into fresh history wires. A branch with history $h$ has the form

Distinct recorded histories are orthogonal. Controlled subsequent operations preserve the same branch squared norms and classical output distributions as the measured procedure. A reset is implemented by retaining the old factor and using a fresh zero wire.

Simulate the classical controller reversibly: compute intermediate Boolean values into fresh wires, retain the necessary configuration history, and use a halted flag after termination. AND is implemented by Toffoli, and XOR and copying by CNOT. No exponentially large decision tree needs to be printed. This is the compute–retain–reverse discipline of reversible computation Bennett,Toffoli.

Addressed quantum instructions can be compiled by enumerating ordered distinct tuples of physical wire addresses. There are at most $w^4$ tuples when the workspace has width $w$. For each tuple, reversibly compute the selection predicate, apply the selected controlled gate, and uncompute the predicate.

If the selected instruction already has an extra control, combine that control with the selection bit into a temporary conjunction before applying the singly controlled primitive. This avoids adding an unauthorized higher-arity gate to the alphabet.

The number of time steps, tuples, controller operations, measurement bits, and retained configurations is polynomial. Their gate-list generation is polynomial as well. Reversing that list gives the inverse.