Quantum circuit oracles for Abstract Machine computations

This paper considers a very general model of computation via conditional iteration, the abstract machines of Hines (2008) [23], and studies the conditions under which these describe reversible computations. Using this, we demonstrate how to construct quantum circuits that act as oracles for these Abstract Machines.For a classical computation with worst-case performance T, the resulting quantum circuit requires an ancilla of 1+log(T) qubits, and takes O(T) steps. The ancilla starts and finishes in the constant state |0〉, so garbage collection is performed automatically.