Graduate Shor's algorithm - need to uncompute auxiliary qubits?

[jarekduda]

Due to required reversibility, classical function (f(a)=y^a \mod N) in Shor's algorithm needs a lot of auxiliary qubits. I was afraid that their later treatment might influence the computation - and just got confirmation from Peter Shor himself: that we need to "uncompute" these auxiliary qubits.

Let's look at quantum subroutine of Shor's algorithm:

1. Hadamard gates create superposition of all (exponential number) values for input qubits.
2. Then we perform a classical function on them, which is here: f(a)=y^a \mod N, where N is the number we would like to factorize, y is some chosen (usually random) number smaller than N
3. Then we perform measurement of value of this function f(a)=m (random). This measurement restricts the original ensemble to only input values a, such that f(a)=m.
4. Mathematics says that this restricted ensemble has to be periodic, this period can be concluded from value of (quantum) Fourier transform, and allows to conclude the factors.

However, calculation of classical function requires huge number of auxiliary qubits (~square of number of other qubits) - they are usually ignored in considerations, but there is a crucial question what finally happens with them?
As measurement of value qubits has restricted the ensemble, measuring/collapse of auxiliary qubits should also affect the ensemble - this time in unwanted way.

I thought maybe we could "erase them" by measuring in orthogonal basis, but Peter Shor has replied:
"In order to make the factoring algorithm work properly, you need to reset all the auxiliary qubits, which started as |0⟩ at the beginning of the computation, to |0⟩ at the end of the computation. This is called "uncomputing" these qubits. (Actually, you can set them to anything you please as long as it is a constant independent of the workings of the algorithm.) Theorems about reversible classical computation ensure that it is possible to do this."

Asking for literature, he replied: "Measuring the qubits in the "orthogonal basis" isn't going to work. You need to "uncompute" them. This is discussed briefly on page 9 of my paper, and in much more detail in C. H. Bennett (1973), Logical reversibility of computation."

However, reversible computation of bits is just a permutation - I don't see how to "uncompute" most of them (auxiliary) to a fixed value such that the total process is still a permutation?
Can it be done? How? Have you seen addressed/solved this problem in a literature?

 

[Strilanc]

Here is a simple recipe for creating a quantum circuit to compute a function:

1) Create a normal irreversible classical circuit that computes the function.
2) Convert all of the gates in that circuit into reversible gates.
2a) Introduce an ancilla bit for every wire (value) in the classical circuit.
2b) Initialize the output wire of gates using the input wires and a reversible gate, e.g. an AND gate becomes a Toffoli gate from the bits corresponding to the input wires to the bit corresponding to the output wire.
3) After the output has been prepared, add operations that clear each bit corresponding to an intermediate wire (go in reverse order, since later intermediates need earlier intermediates).
4) You now have a circuit that produces no extraneous garbage, so you can run it on a quantum computer without causing unexpected decoherence.

This recipe always works, assuming you aren't trying to modify a register in place and you're okay with the large amounts of overhead.

As an example, let's do a full adder. Here is a diagram of the classical circuit that I got from google image search:

This circuit has 8 distinct values, one for each input and one for each gate output. We'll call them A, B, Cin, xor1, S, and1, and2, Cout. We then prepare an equivalent reversible circuit:

AND gates got turned into Toffoli gates, XOR gates got turned into a pair of CNOTs, and OR gates got turned into a Toffoli with inverted controls and an inverted output (because A or B is equivalent to not [not A and not B]).

This circuit gives the right values of S and Cout for each possible value of A, B, and Cin. But it also generates quite a lot of other junk, namely the xor1, and1, and and2 values. We need to get rid of those if we want to avoid problems when doing quantum computation. Fortunately, there's a very easy way to do that: just run every operation in reverse order (except the ones that initialized the output). Looks like this:

And that's how you compute the sum of three bits without generating any other garbage. You can use this circuit on a quantum computer.

Computing the modular exponentiation of an n-bit register can be done in exactly the same way. The circuit will be larger, but the same ideas apply.

If you want more details on explicit circuit constructions that can be used by Shor's algorithm, with a focus on minimizing the number of bits, see my paper Factoring with n+2 clean qubits and n-1 dirty qubits.

 

[jarekduda]

Thank you, this is a very clear example - indeed we can and should "uncompute" all the auxiliary qubits back to |0>.