How Time-Traveling Could Affect Quantum Computing

(PhysOrg.com) -- If space-time were constructed in such a way that you could travel back in time, it would create some pretty strange effects. One of these oddities, as many people know, is the “grandfather paradox.” Here, a person travels back in time to kill their grandfather before the person’s father is born, thus preventing their own birth.

The type of space-time that enables time traveling involves “closed time-like curves” (CTCs), and, besides personal fates, CTCs can also provide insights into quantum information and computing. In a recent study, computer scientists Scott Aaronson of MIT and John Watrous of the University of Waterloo have discovered that, if closed time-like curves exist, then quantum computers would be no more powerful than classical computers.

But researchers shouldn’t stop working on quantum computing technology just yet, as no one has any evidence that closed time-like curves actually exist. Closed time-like curves are strange: sometimes physicists describe them as a piece of paper folded over on itself, so that opposite ends touch and create a shortcut. A person standing at the front end could then easily step onto the back end, thereby easily stepping into the past.

CTCs provide interesting but complex insights into computation. At first it may seem that, if CTCs existed, researchers could perform computations of unlimited length in an instant, by simply computing the answer, and then sending it back in time to before they started. However, this proposal, like the grandfather paradox, breaks the rules of causality, since the input could be changed, affecting the future output. Further, the computation may have actually taken 100 years, so Aaronson and Watrous don’t consider this an honest computation method.

Instead, the scientists attempt to overcome causality breaking and its paradoxical consequences. One way to do this is to simply argue that nature must somehow enforce causality. For example, in 1991, physicist David Deutsch proposed a resolution to the grandfather paradox that relies on the parallel universes theory in quantum mechanics: everyone is born into a universe with a certain probability, so if you go back in time to kill your grandfather, there’s a probability that you won’t be born in that universe, but another. Not all physicists agree with such interpretations, but Aaronson and Watrous adopt Deutsch’s ideas for their demonstration.

The scientists envision a scenario in which classical and quantum computers contain CTCs, and these CTCs contain bits or qubits. Computations start at a fixed point, which nature somehow decides on, and which ensures causal consistency (avoiding the grandfather paradox).

Aaronson and Watrous show that classical and quantum computers with polynomial-size CTCs both have the same amount of computing power. They can both solve the set of problems in an abstract space called 'PSPACE,' which is all the problems that a classical computer can solve using a polynomial amount of memory. This computing power is extremely large, and both types of computers are very efficient when using CTCs.

“The way you use CTCs to compute, in one sentence, is by forcing nature to solve an exponentially hard computational problem just in order to make the universe causally consistent,” Aaronson told PhysOrg.com. “You can set up the computation inside the CTC to take as input a proposed solution to the problem, and then do the following:

“IF the input solution is correct, THEN output that same solution.
IF the input solution is incorrect, THEN output the next solution in some standard ordering (looping around to the first solution after you've reached the last one).
Go back in time, and feed in the output of the computer as its input.”

The key, Aaronson explained, is determining what the input to this computation needs to be, in order for everything to be causally consistent.

“Assuming there are any correct solutions at all, the input must itself be a correct solution!” he said. “For otherwise we'd have an inconsistency: the output of the computation would not match the input.”

He added that, if there are no correct solutions, then the output and input both have to be completely random; that's the only way to ensure causal consistency in that case.

“Admittedly, how nature manages to actually do the work of finding the fixed point (and thereby making the universe causally consistent) remains a great mystery,” he said. “But the point is, this is the sort of thing nature would presumably need to do if CTCs existed.”

In their study, Aaronson and Watrous described CTC computing using a rough analogy of Shakespeare’s plays being written by someone from the present going back in time and dictating the plays to him. As long as the person from the present dictates the plays correctly, there is no paradox, and causal consistency is maintained.

“In the Shakespeare example, there's no actual logical inconsistency,” Aaronson explained. “You go back in time and dictate the plays to him, therefore he writes the plays, therefore the plays come down to you, therefore you're able to go back in time and dictate the plays to him, etc. Everything is consistent – there's no paradox! Or rather, the only ‘paradox’ is one of computational complexity: a difficult task seems to have been performed (namely, Shakespeare's plays being written), but without anyone ever doing the actual creative work of writing those plays.”

By pinning down the exact computational power of CTCs, the computer scientists hope that their findings may lead to applications in quantum information.

“In order to solve this problem, Watrous and I had to give an algorithm for computing fixed points of quantum operations using a polynomial amount of memory,” Aaronson said. “And that's something that one could easily imagine finding other uses for in quantum computing theory. In fact, I'm working on a paper right now about using bounded-memory quantum computers to extract the bias of a classical coin. And in order to solve the problem in that paper, I'm using many of the same techniques as in the closed time-like curves paper.

“I don't want to oversell this,” he added. “It's not going to revolutionize quantum information; it's just (even at the purely technical level, and ignoring the closed time-like curve part) a useful trick.”

More information: Aaronson, Scott and John Watrous. “Closed timelike curves make quantum and classical computing equivalent.” Proc. R. Soc. A. doi:10.1098/rspa.2008.0350.

Copyright 2008 PhysOrg.com.
All rights reserved. This material may not be published, broadcast, rewritten or redistributed in whole or part without the express written permission of PhysOrg.com.