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

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?

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.

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$$.

• Thanks for your answer. I have no problems understanding what the sqrt not gate does, however I find it difficult to frame its existence in the context ir/reversibility. Could you explain how the sqrt not demonstrates the difference between classical and quantum computation in terms of information loss / reversibility?
– gen
Mar 5, 2020 at 22:09

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.