Study Shows Time Traveling May Not Increase Computational Power

(PhysOrg.com) -- For more than 50 years, physicists have been intrigued by the concept of closed time-like curves (CTCs). Because a CTC returns to its starting point, it raises the possibility of traveling backward in time. More recently, physicists have theorized that CTC-assisted computers could enable ideal quantum state discrimination, and even make classical computers (with CTCs) equally as powerful as quantum computers. However, a new study argues that CTCs, if they exist, might actually provide much less computational benefit than previously thought.

A team of scientists consisting of Charles Bennett, Graeme Smith, and John Smolin from IBM, along with Debbie Leung from the University of Waterloo, argues that previous analyses of CTCs have fallen into the so-called “linearity trap,” and have been based on physically irrelevant definitions that have led to incorrect conclusions about CTCs. The new study will be published in an upcoming issue of Physical Review Letters.

As the physicists explain, CTCs are difficult to think about because they make quantum evolution nonlinear, whereas standard quantum mechanics systems evolve linearly. (In linear systems, the evolution of a mixture of states is equal to the mixture of the evolutions of individual states; this is not the case in nonlinear systems.) It seems that much of the apparent power of CTCs has come from analyzing the evolution of pure quantum states, and extending these results linearly to find the evolution of mixed states. The physicists call this situation the “linearity trap,” which occurs when nonlinear theories are extended linearly. In the case of CTC computations, Bennett and coauthors found that this problem was causing the output to be uncorrelated with the input, which isn't a very useful computation.

“The trouble with the earlier work is that it didn't take into account the physical processes by which the inputs to a computation are selected,” Smith told PhysOrg.com. “In a nonlinear theory, the output of a computation depends not only on the input, but also on how it was selected. This is the strange thing about nonlinear theories, and easy to miss.”

To overcome these problems, the scientists proposed that the inputs to the system should be selected by an independent referee at the start of the computation, rather than being built deterministically into the structure of the computer. In order to ensure that the proper input is selected, the physicists proposed the “Principle of Universal Inclusion.” The principle states that the evolution of a nonlinearly evolving system may depend on parts of the universe with which it does not interact, ensuring that scientists do not ignore the parts of the universe that need to be used to select the inputs. The physicists hope that these criteria will lead to choosing the correct input, and then to generating the correct corresponding output, rather than simply evolving the system linearly based on incorrect inputs.

As the scientists note, one of the motivating factors for their investigation is the previous finding that CTCs can distinguish between two nonorthogonal pure states, which is impossible in standard quantum mechanics. Further, the previous results seemed to imply that CTCs could be used to distinguish between two identical states, which should be impossible no matter how you look at it. To investigate this problem, the scientists considered what would happen if they prepared and evolved quantum states according to a specific physical process. They found that two output states can be distinguished even without using a CTC, eliminating any advantage the CTC may have offered.

In addition to quantum state discrimination, the physicists also investigated the alleged computational power of CTCs, where they found that the output is often not correlated with the input. The scientists argue that the root of the problem seems to lie in the definition of the CTC-assisted computational class, which is not physically or computationally meaningful, and does not produce correctly correlated mixtures of input-output pairs. The scientists proposed an alternate CTC-assisted computational class that allows them to correctly evaluate the system’s abilities, but it also shows that CTC-assisted systems do not seem to increase computational power.

Not all scientists agree with the new results. Scott Aaronson of MIT, who has also investigated the possible computation benefits of CTCs, said that he has been aware of the issues of nonlinearity, but does not consider it as important as the scientists do in the current study. Further, he explains that, even in the new model, CTCs would still increase the power of quantum computers.

“The underlying reason for the disagreement is this: in the actual universe, CTCs almost certainly don't exist,” Aaronson said. “So, in asking what the right model of computation ‘would be’ if they did exist, one is inherently asking a strange and somewhat ill-defined question.”

Aaronson agreed with the new study that requiring the input to be a pure state (as he and coauthor John Watrous do in a previous study) is a problem. But, he said, the new model requires the input to be nothing, which is an even bigger problem.

“As it turns out, every answer to the question that people have come up with has had conceptual problems,” he said. “But in (essentially) prohibiting any input whatsoever to the CTC register, it seems to me that Bennett et al. make the conceptual problems worse, not better, than they are in my and Watrous's model. This is a matter of honest disagreement.”

In spite of the new study’s conclusions, Smith also thinks that CTCs are still worth investigating, as they may be useful in ways that are currently unknown.

“I think it's still interesting,” he said. “Our work just highlights some of the subtleties involved that can lead you to inaccurate conclusions. I should point out that we haven't proven CTCs are no good for computation, we've only shown that the existing algorithms that have been proposed don't work. So, there might be something more out there (though I wouldn't bet on it).”

More information: Charles H. Bennett, Debbie Leung, Graeme Smith, and John A. Smolin. “Can closed timelike curves or nonlinear quantum mechanics improve quantum state discrimination or help solve hard problems?” Physical Review Letters. To be published. arXiv:0908.3023v1

Copyright 2009 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.