Simple circuit simulations of classical and quantum Turing machines

Abstract

We construct reversible Boolean circuits efficiently simulating reversible Turing machines. Both the circuits and the simulation proof are rather simple. Then we give a fairly straightforward generalization of the circuits and the simulation proof to the quantum case.