[Cryptography] Quantum computers and the Government

[Jerry Leichter]

> As for reversible computations, anything you do with quantum computers must in some sense be reversible, apparently because of quantum physics....
QM is linear.  All evolution of quantum state is multiplication by invertible matrices (gross oversimplification) - which is inherently invertible, so loses no information.  That's why you can't build a quantum AND or OR gate - such gates would lose information.  Instead you get gates with two inputs and two outputs, one of which gives you the result you care about, and the other of which ensures reversibility.  One that often gets mentioned is the CNOT, or Controlled Not, gate:  It take x and y as input, and returns x XOR y *and x* as outputs.  (So it replaces y by NOT Y if and only if x is true - hence the name.)  Of course the point of this is not to do it with classical bits, but with qbits. If you throw away the x output, which you think of as just irrelevant fluff in classical terms ... your x XOR y result promptly turns from a qbit into just a normal bit, either exactly 0 or exactly 1.  The wonders of quantum mechanics.

"No information loss" was the basis of an apparent paradox - and a bet - about what happens in a black hole.  General relativity tells us "Black holes have no hair":  A black hole is completely defined by only three parameters (mass, charge, spin).  So if you throw in an encyclopedia, versus throwing in blank sheets of paper with the same total mass ... the effect on the black hole is the same.  So what happened to the information in the encyclopedia?  

As long as black holes were thought to be permanent features of the universe once formed, one could imagine that the information was in there, just locked up out of reach.  But then Stephen Hawking showed that once you consider quantum mechanics, black holes must gradually (and eventually exponentially quickly) lose their energy by emitting what's now called Hawking radiation - and that that radiation is thermal, i.e., completely random, carrying no information about the black hole.  If the black hole vanishes ... where did the information go?  In a celebrated 1997 bet, Hawking and Kip Thorne bet John Preskill that the information was indeed lost (which would require some kind of change to QM to explain how); Preskill claimed the information leaks out somehow (which would require some kind of change to general relativity to explain how).  The winning side of the bet would receive an encyclopedia of their choice, "from which information can be retrieved at will."

Hawking conceded in 2004, though Thorne didn't.  The details remain obscure and debated.  There's some very recent work that actually shows how the information might leak out (through correlations between emitted particles and something in the black hole).  Wild stuff - originally shown in the context of string theory, but then the techniques were translated into more traditional terms.  I don't know if this stuff is universally accepted.  There's still so much we don't understand!

                                                        -- Jerry