Study Shows Time Traveling May Not Increase Computational Power

October 22, 2009 By Lisa Zyga feature

( -- 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 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 “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 . 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 discrimination or help solve hard problems?” . To be published. arXiv:0908.3023v1

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

Explore further: How Time-Traveling Could Affect Quantum Computing

Related Stories

How Time-Traveling Could Affect Quantum Computing

November 20, 2008

( -- 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.” ...

Quantum ghosts are helpful

April 27, 2009

( -- The idea that far distant particles can somehow 'talk' to each other worried Einstein so much that he called it 'spooky action at a distance'.

Recommended for you

Mapping the edge of reality

April 28, 2017

Australian and German researchers have collaborated to develop a genetic algorithm to confirm the rejection of classical notions of causality.


Adjust slider to filter visible comments by rank

Display comments: newest first

1 / 5 (1) Oct 22, 2009
I theorized on this a number of years back and came to the same conclusion.
Oct 23, 2009
This comment has been removed by a moderator.
1 / 5 (1) Oct 23, 2009
Semi-dirac DIRC cherenkov radiation loops in plasma torroidal arrays should offer something of each quantum and CTC archs towards faster computation systems.
1 / 5 (1) Oct 23, 2009
"CTCs can distinguish between two nonorthogonal pure states, which is impossible in standard quantum mechanics."

(translation of above: CTCs find a difference between two parallel vectors of equal magnitude)
Yeah, that is pretty dumb... Why did nobody notice this? It's sort of an obvious clue that something is seriously wrong...

"“The underlying reason for the disagreement is this: in the actual universe, CTCs almost certainly don't exist,” Aaronson said."

Just to speculate, but from my perspective it's not that CTCs don't exist, it's that they would be treated incorrectly under quantum mechanics as it is conceptualized in the Copenhagen interpretation.

Copenhagen Interpretation: Every time a "flop" occurs, where an outcome is random, one universe with each outcome can be said to exist.

My Interpretation: Every time a flop occurs, where an outcome is random, the outcome is determined by the position in reference to a "reality matrix". Only 1 universe, one outcome.
1 / 5 (2) Oct 26, 2009
For me classical computers with such loop allows for example to immediately solve NP-problems:
Imagine we take some real random number generator - for example measuring spin of photon 45 degrees from its polarization.
Now the procedure is:
(1) make a choice according to this generator,
(2) if from future there is a message that it was a wrong choice - take a different one
(3) wait for results of this choice
(4) finally if it was wrong choice - send this information back in time to (2)
Now if there is a satisfying choice, physics should choose it to stabilize this time-loop.
If there isn't, it has to lie, such channels cannot be perfect, it would allow for paradoxes.
The question is if they are allowed - it's similar question if physics is deterministic. It's not popular believe nowadays because of Bell's inequalities, but it's a meter of proper understanding
1 / 5 (1) Oct 29, 2009
What is time? What is a closed time-like curve???
How is one created? Can it ever be created (other than in your imagination)????????

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.