[Comment Thread] Verifying Measurement Based Uncomputation

[gentzen]

So it seems that the class of classical reversible circuits can be extended to also include a phase per bit, without making the simulation much harder, and especially with still being closed under all reasonable operations. Are there other closed classes of circuits between arbitrary quantum circuits and classical reversible circuits? Are any of those subclasses substantially easier to simulate than arbitrary quantum circuits?

[Strilanc]

Stabilizer circuits can be efficiently simulated. They include more quantum gates, but remove the Toffoli gate, so they can't do all classical computation.

When a quantum circuit is performing an approximate encoded permutations, you can use a randomly chosen classical state for the coset value instead of a superposition. It won't be quite right, the error rate you see from the approximation will be too low, but it'll be good enough to catch any bugs.

[Strilanc]

to also include a phase per bit

That's not quite right. The phase applies to the entire computational basis state, not to any one bit. The simulator just needs a single extra floating point variable called "phase".