Originally posted on PHYS, however, obviously it has more to do with CS
I am currently trying to implement a circuit for computing the greatest common divisor in the Quantum Computing Language. In my work, I partially proceed from the paper Quantum Circuits for GCD Computation with O(nlogn) Depth and O(n) Ancillae published by I. Markov and M. Saeedi in 2013, which may be found at arXiv http://arxiv.org/abs/1304.7516.
The paper introduces a binary GCD algorithm analogue and works out a design of the quantum circuit which is clarified in least details, however, in the same time it is somewhat confusing due to several statements that actually do not correspond with the rest of the work. First of all, let me enclose an image denoting design of the circuit. (Credit goes to the paper)
As you may see, the circuit entirely corresponds to the classical binary GCD algorithm. It takes advantage of quantum circuits for comparison, bit shift, addition and multiplication. Nevertheless, in our case those functions are controlled by state of ancillary qubits and thus, they may not regarded reversible on their own. It means, we have to account for a separate register of auxiliary qubits which cannot be erased till the end of our computation as it would simply violate desired reversibility otherwise.
But in contrast to that, in the paper we may find at least three statements which do actually deny those simple facts. Let me cite: (About preceding works) The authors did not clear all zero-initialized ancillae which limits the applicability of their techniques. (About the circuit) The zero-initialized ancillae may be modified in-side a given circuit, but should be returned to zero at the end of computation to be reused. (About implementation) To count ancillae, note that all computational ancillae are cleared inside each block. After the final multiplication block for R·B, one can copy (in log depth) the final GCD result to another n-qubit zero-initialized register and apply the whole circuit (except for copying the result) in reverse order to recover A,B, and zero-initialized ancillae. Given that all components use O(n) ancillae, the total number of ancillae remains linear.
I ask myself: How can be all ancillaes cleared at the end of each computational block while the binary GCD seems to be reversible only with regard to an auxiliary register of control qubits? It is apparent this question reduces to the problem of binary GCD reversibility which is actually something I am doubtful about. Maybe I lack of insight and the usage of other control bits is so obvious so as to omit it, however, in every case I would like to ask you about your view on the problem.