Shor's algorithm - need to uncompute auxiliary qubits?

In summary, Shor's algorithm for factoring large numbers requires a large number of auxiliary qubits in order to perform the required classical function in a reversible manner. These auxiliary qubits are often ignored, but Peter Shor has confirmed that they must be "uncomputed" at the end of the computation in order for the algorithm to work properly. This can be done by converting the classical circuit into a reversible one and then clearing the intermediate qubits, resulting in a circuit that produces no extraneous garbage. This concept can also be applied to modular exponentiation, and for more details on this approach, refer to the paper "Factoring with n+2 clean qubits and n-1 dirty qubits."
  • #1
jarekduda
82
5
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 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:
EW7qP.png

  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: [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]
  3. Then we perform measurement of value of this function [itex]f(a)=m[/itex] (random). This measurement restricts the original ensemble to only input values [itex]a[/itex], such that [itex]f(a)=m[/itex].
  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?
 

Attachments

  • EW7qP.png
    EW7qP.png
    30 KB · Views: 1,573
Physics news on Phys.org
  • #2
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:

full-adder.png


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:

semi-reversible-full-adder.png


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:

reversible-full-adder.png


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.
 

Attachments

  • full-adder.png
    full-adder.png
    5.6 KB · Views: 579
  • semi-reversible-full-adder.png
    semi-reversible-full-adder.png
    2.3 KB · Views: 657
  • reversible-full-adder.png
    reversible-full-adder.png
    3.1 KB · Views: 617
Last edited:
  • Like
Likes jarekduda
  • #3
Thank you, this is a very clear example - indeed we can and should "uncompute" all the auxiliary qubits back to |0>.
 

1. What is Shor's algorithm?

Shor's algorithm is a quantum algorithm developed by mathematician Peter Shor in 1994. It is used to efficiently factor large numbers, which is a task that is considered difficult for classical computers.

2. How does Shor's algorithm work?

Shor's algorithm uses quantum Fourier transform and modular exponentiation to find the period of a function. This period is used to factor a large number into its prime factors. The algorithm also makes use of quantum parallelism to perform many calculations simultaneously, making it more efficient than classical algorithms.

3. What are auxiliary qubits in Shor's algorithm?

Auxiliary qubits are additional qubits used in Shor's algorithm to store intermediate results and perform calculations. These qubits are not part of the input or output of the algorithm, but they are necessary for its success.

4. Why is it important to uncompute auxiliary qubits in Shor's algorithm?

Uncomputing auxiliary qubits is important because it allows the algorithm to run more efficiently. When the algorithm is finished, these qubits are no longer needed and can be "erased" to make room for new calculations. Uncomputing also helps to reduce the chances of errors in the quantum computation.

5. Can Shor's algorithm be used for other problems besides factoring?

Yes, Shor's algorithm can be adapted for other problems that involve finding the period of a function, such as discrete logarithms and solving certain types of equations. However, it is most commonly used for factoring large numbers, as this has important implications for cryptography and computer security.

Similar threads

  • Quantum Physics
Replies
22
Views
358
Replies
2
Views
1K
  • Quantum Physics
Replies
13
Views
817
  • Quantum Physics
Replies
1
Views
644
  • Quantum Physics
Replies
2
Views
1K
  • Quantum Physics
Replies
11
Views
2K
Replies
3
Views
754
  • Quantum Physics
Replies
5
Views
2K
  • Quantum Physics
Replies
8
Views
1K
  • Quantum Physics
Replies
1
Views
2K
Back
Top