Last time I talked about information causality. Today I want to call attention to two other interesting talks at the New Directions in the Foundations of Physics conference in Washington DC.
The first talk was Dan Browne's "Computational Character of Quantum Mechanics." What Dan did was to present the solution to the problem he originally presented at the second FQXi conference. For his problem, he considered linear classical devices in a black box and asked what kind of computational tasks can the black box achieve? Then he switched the classical linear devices with quantum mechanical linear devices and observed that the black box became a universal Turing machine. Whaw! Why?
The key to the answer lies in representing the GHZ equality in binary format, and noticing that it converts sums into products. And with products, via Taylor series, one can approximate any nonlinear output. In fact what happens under the hood is a transition from Presburger arithmetic to the much more powerful Peano arithmetic.
The second talk I want to present to you was Scott Aaronson's about playing with computers and time machines. Scott was claiming that hard computational problems become simple problems if time travel is possible because time suddenly becomes a reusable resource.
Now time machines do fire the imagination under any circumstances, and the talk did not disappoint on that. But time travel is ripe with problems and it was impossible for Scott not to create controversy. The first (obvious) problem for Scott was the grandfather paradox. The solution was easy: in quantum mechanics the cat can be both dead and alive by quantum superposition, and Scott was following David Deutsch's suggestion that a time machine naturally finds fixed points in a stochastic evolution equation.
Unfortunately there are serious objections to his claim, because time travel has also other problems. In fact, one can take known time travel no-go results, and translate them in this computational approach. I could think of two right away.
First, there is an old objection by Jacobson who pointed out that the quantum mechanics expectation values in the presence of time machines are ambiguous because a Lorentz transformation can tilt the "now" plane to intersect the acronal region. Several papers attempted to modify quantum mechanics by renormalizing appropriately the answer, but all suffered from one problem or another. So how would Jacobson objection translate into Scott's result? Easy. Have two spatially separated operators enter a superposition state of quantum mechanics, add the inputs and let the time machine compute an answer. However, a fast moving observer would see something completely different: the first operator enters a part of the wave function and gets instantaneously an answer back, while a moment later the other operator gets his answer. But here is the catch. Adding the two answers do not equal the answer as seen by a stationary observer, because the answer is in general non-linear (http://arxiv.org/abs/0908.3023).
Another objection would be from a result originally obtained by Hawking. The time traveler returning back would lose all his quantum coherence and would not bring any information back from the future. All lottery number information from the future would be wiped out. So what would be the equivalent problem in computation? The limiting cycle of the stationary point. If the quantum system evolves from state A to B, to C, to Z, and all the way back to A, what you get in fact is completely white noise, a state of maximum entropy which would take the same long computational amount of time to isolate the answer as it would take without the time machine. And since Scott asserts that all computational hard problems can be solved in no time, this counter-example shows that this hope is not realized.
So while the idea of time as a reusable resource is valid and under this assumption Scott's results were valid, in reality do not try to build a time machine to speed up computations. Who knows, maybe all the answers coming back would be 42.