12

In implementing a quantum subroutine it is important to uncompute temporary registers after use, to ensure the output state of the subroutine is not entangled with them (which would affect its behaviour).

Why is it necessary to perform this through uncomputation rather than simply setting temporary registers to zero afterwards?

Sideshow Bob
  • 427
  • 2
  • 10

3 Answers3

9

While it is definitely possible to reset registers after using them (namely, by simply measuring them) the issue is that doing so can potentially destroy interference that one might want to achieve by subsequent computations with the quantum data. Unfortunately, this is the most common case encountered in quantum algorithms, such as e.g. the computation of arithmetic in Shor's factoring and dlog algorithms or the computation of a Boolean predicate in case of Grover's search algorithm.

Concretely, assume that we have two registers, a data register $A$, an output register $B$, and an ancilla register $C$ and that half-way through the computation we arrived at an entangled state $\sum_{x} \alpha_{x} |x\rangle |f(x)\rangle |g(x)\rangle$, where the inputs are held in $A$, the function values $f(x)$ are computed into $B$, and the values $g(x)$ are results of some intermediate computations that is stored in the scratch register $C$.

If we now, instead of uncomputing the register $C$ so that it holds $|0\rangle$ (or some other state that is unentangled with registers $A$ and $B$), we decide to reset the register $C$, this will have the following detrimental effect: we will measure (at random) some value $c_0$ and the state will collapse to the superposition of all $x$ that are consistent with this measured value, so that the state will become (up to normalization):

$$ \sum_{x: g(x) = c_0} \alpha_x |x\rangle |f(x)\rangle. $$

Note that this can be vastly different from the state $\sum_x \alpha_x |x\rangle |f(x)\rangle$ that we really wanted (and actually only for constant functions $g$ yields the correct result). Indeed, if $g$ is a permutation, only a single $x$ will survive from the initial superposition! Hence, temporary/scratch registers have to be uncomputed if we want to do subsequent computations with the data in the other registers.

MartinQuantum
  • 765
  • 5
  • 9
6

Uncomputing temporary registers seem to me to be the most efficient way to set temporary registers back to zero.

You can't measure these and classically flip them

  1. because a measurement of $1$ doesn't necessarily mean the state of the temporary register is $|1\rangle$

  2. because measuring would cause entangled qubits to collapse into a corresponding state so that would defeat the purpose of uncomputing temporary registers that you mentioned in your question.

And somehow implementing a circuit that detected a temporary register's state moved it back to 0 would be much more difficult than simply uncomputing the temporary register.

Sanchayan Dutta
  • 17,945
  • 8
  • 50
  • 112
Malcolm Regan
  • 773
  • 5
  • 11
3

Because all operations you carry out (besides measurement) need to be unitary and this one would not.

cnada
  • 4,802
  • 1
  • 9
  • 22