In his book Quantum Computer Science, Mermin says that, although we'll need lots of "workspace" qubits in addition to those in the input and output registers, we can essentially ignore these in our analysis so long as we start and end with them in some fixed state, since they'll then be unentangled with the registers which contain any information we actually care about. He then goes into some detail to show that this is possible, i.e. that we can use the workspace bits, yet leave them in a fixed state. In fact, his method is intended to leave them in the initial state.

Here's his diagram of the approach:

Mermin, p. 49

The top bits are the workspace, the middle ones the input and the bottom ones the output. We apply some unitary (hence invertible) operator V to do the actual job of calculating the function using only the input and workspace bits. Then we copy the result to the output (using a series of cNOT gates). And finally we undo the effect of V by applying its inverse, which, Mermin says, leaves both the input and workspace in their original states.

I'm a complete novice in all this, but it looks wrong. After the copy, all three sets of bits are entangled and, it seems to me, we'd have to undo the copy as well as V to be sure that the input and workspace are restored to their original states.

Just to give the simplest example, suppose workspace, input and output all consist of just one bit. And suppose that V actually just applies a Hadamard to the input, so that the inverse is another Hadamard. Applying a Hadamard to the input, a cNOT with input as control and output as target and then another Hadamard to the input does not return the input to its original state.

So, in general, applying $V^\dagger$ does not look like any guarantee that the workspace will end up in its original state.

If I'm wrong--as I assume given my inexperience--what's my error? Or, in the unlikely event that I'm right, what can be done to make sure that the workspace state is restored and hence that we can, in fact, ignore it.

[Added later]

Here's a specific case in which, as far as I can tell, things don't work out. As above, input, output and workspace are each just one bit.

Simple example of a problem case

  • $\begingroup$ Does Mermin assume anything about the initial state of the output bits? It seems to me that for the computation shown in the diagram to be at all useful, you would at least have to know what the initial state of the output bits was. If one further assumes a particular initial state for the output bits, one may be able to say even more. $\endgroup$ Jul 23, 2015 at 22:37
  • $\begingroup$ Mermin assumes that the output bits are initially all zero. He also assumes that the workspace starts in some fixed state not dependent on the input $x$. Normally, the fixed initial state of the workspace would be also be all-zeroes, but that's not an assumption. $\endgroup$ Jul 24, 2015 at 1:43

1 Answer 1


Mermin was kind enough to look at this himself and provide me (the original poster) with an answer. The key is that his $V$ operator is not only reversible but, since it calculates a function $f(x)$ from binary numbers to binary numbers, one that takes basis states to basis states. With this second condition, it is, in fact, true that applying the inverse $V^\dagger$ after the copy leaves workspace bits in their original state.

My hand-drawn counter-example uses a $V$ that does not take basis states to basis states, since it applies a Hadamard to the input.

I convinced myself that the second condition resolves the problem by looking at a couple of examples. Even if the input is a superposition $\alpha_0 |w_0x_0y_0\rangle+\alpha_1|w_1x_1y_1\rangle+...$, we're okay. The operator $V$ applies a 1-1 relabeling of the $wx$ sections of the components of the superposition. The copy changes $y$'s, doing nothing to the $wx$ sections. And then $V^\dagger$ inverts the relabeling, leaving the $wx$ sections as they were initially. Since all of the $w$ parts were initially identical, they must also end up identical--which was the goal, since it implies they're not entangled with the rest.

Note that my question contains an error. Mermin does not claim that the input ends up in its initial state, just that the workspace does.

  • $\begingroup$ If you have correspondence from him you could post, that would be instructive. $\endgroup$
    – Simon S
    Jul 24, 2015 at 17:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .