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

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

However, calculation of classical function requires huge number of

- Hadamard gates create superposition of all (exponential number) values for input qubits.
- Then we perform a classical function on them, which is here: [itex]f(a)=y^a \mod N[/itex], where [itex]N[/itex] is the number we would like to factorize, [itex]y[/itex] is some chosen (usually random) number smaller than [itex]N[/itex]
- Then we perform measurement of value of this function [itex]f(a)=m[/itex] (random).
This measurement restricts the original ensembleto only input values [itex]a[/itex], such that [itex]f(a)=m[/itex].- 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.
auxiliary qubits(~square of number of other qubits) - they are usually ignored in considerations, but there is a crucial questionwhat 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, butPeter 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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# A Shor's algorithm - need to uncompute auxiliary qubits?

Have something to add?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**