What does the $\sqrt{NOT}$ gate have to do with irreversibility?

Question

In his essay "Why now is the right time to study quantum computing" Aram Harrow writes, after describing the action of the $\sqrt{NOT}$ gate, that:

However, if we apply $\sqrt{NOT}$ a second time before measuring, then we always obtain the outcome 1. This demonstrates a key difference between quantum superpositions and random mixtures; placing a state into a superposition can be done without any irreversible loss of information.

I'm confused by what he meant here. How does the existence of a $\sqrt{NOT}$ gate in quantum computation demonstrate a difference in irreversibility as opposed to classical computation?

Answer 1

I wouldn't say it's the existence of the $\sqrt{NOT}$ gate that demonstrates reversibility per se. It's the specific example that Harrow is using.

When you measure the output of applying a $\sqrt{NOT}$ gate to a $|0\rangle$, it looks just like a coin flip. It could be either $|0\rangle$ or $|1\rangle$ with a 50% chance. So far, nothing has been demonstrated that a random mixture can't do. A random mixture is perfectly capable of replacing a single bit with the results of a coin flip.

When you apply $\sqrt{NOT}$ a second time, the $\sqrt{NOT}$ gate recovers the initial information. But recovering information would be impossible if there was simply a random mixture. That's the demonstration of the key difference between superposition and random mixture. Information used in the creation of a superposition can be recovered; information lost in a random mixture cannot be.

Answer 2

He's saying that there is a unitary matrix $U$ (quantum operation) with the property that $U^2$ is a bit flip, but there is no stochastic matrix (random operation) $S$ such that $S^2$ is a bit flip.

In terms of reversibility, the key thing is that the state $U|0\rangle$ is perpendicular to the state $U|1\rangle$ for any $U$. For classical operations that is not always true. For example, for the "coin flip" operation $S$ it is the case that $S|0\rangle = S|1\rangle$. This implies that there can be no inverse operation $S^\dagger$ such that $\forall k: S^\dagger S|k\rangle = |k\rangle$.

Answer 3

The point is just that the gate $U := \sqrt{\rm{NOT}}$ naively appears to to scramble all the information about an initial classical state, because it takes both the initial states $|0\rangle$ and $|1\rangle$ to states that have 50/50 probabilities of being measured to 0 or 1. So classically, one would expect that these superposition states $U|0\rangle$ and $U|1\rangle$ would be identical, and that the procedure that prepared them - applying the gate $U$ to a computational basis state - would have irreversably erased all the information about the initial state. But the secret sauce of quantum coherence - i.e. the different relative complex phases in the amplitudes - means that the apparently-scrambled states $U|0\rangle$ and $U|1\rangle$ are actually physically distinct, and applying the gate $U$ again makes the apparently-erased information "reappear" by transforming the apparently-identical states into manifestly distinct states. The point is that unitary operations like $U$ never actually destroy any information about the initial state, even if they might naively appear to.