2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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? $\endgroup$
    – gen
    Mar 5 '20 at 22:09
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.