How Time-Traveling Could Affect Quantum Computing

( -- 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 “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
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

Study Shows Time Traveling May Not Increase Computational Power

Citation: How Time-Traveling Could Affect Quantum Computing (2008, November 20) retrieved 16 October 2019 from
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.

Feedback to editors

User comments

Nov 20, 2008
I believe it was Fred Pohl who wrote a book about future computers, that would travel back in time, compute the answer, travel back to the time if left, and effectively instantenously gave you the answer.

Nov 20, 2008

Shadowram, time travel is crazy to think about and such, makes for good sci-fi, but its important to realize that our perception of reality necessarily involves mental ordering, and so its not always easy to pick out the reality from the mental constructs. For example they said,...

"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,"

Well, there is no analytic link between cause and effect. Causality is a constant conjunction of individual events, its not a thing 'nature manages' of itself,... it's a means of mental synthesis of sense impressions given our mental design, and therefore is not a self consistent aspect of reality itself, such that talk of 'CTCs' are relevant, apart from intellectual masturbation.

We are 'compelled' in believing that there is a necessary connection between cause and effect, when we observe a regularity in our perceptions, ...this is due to a means of mental ordering of reality, not to the reality itself. A rational order of reality can not be accounted for merely by the chance accumulation of sense perceptions, ...the synthesis occurs in our functioning bio-mechanical mind, and so the conceptual form in which our understanding of reality takes is a product of a-prior mental paradigms, ...causality being one.

Nov 20, 2008
The lede misunderstands the information presented. They provide an argument that both quantum and classical computers *which use* closed time curves are equally powerful, not that quantum computers *will prove* no more powerful than classical computers *if* closed time curves exist.

Nov 20, 2008
The problem with classical thinking about time-traveling is that there's a past I. and you go from a future I. to change certain portion of a past into a past II. Consider this. A blank painting canvas is placed in an experiment from the future to be painted with a certain color. A canvas observer will see a traveler from the future to paint it red. But then he stand up and go for a time-machine and we realize that he's that traveler. He saw the color of choice was red so he decides to paint it blue this time. But wait a moment if he'll go to the past then himself will see a blue color and when he'll be about to decide to paint a different color then before he'll choose yet another one. For example the red again because he's not aware that the canvas was already painted by him with such color before. The point is that he'll create a loop in which he's undecided on what color he saw on the canvas and also what color he painted a minute later on it. He'll go nuts or something. But there's ofcourse a simple solution to all the time paradoxes. No time traveling is possible. The reality will happen only one way, the way we cannot tell but the way it always has to be. It's an elegant solution to have an illusion of free will and at the same time be still sure that everything is set in stone.

Nov 20, 2008
Smellyhat gets a 5/5 for using the word "lede" instead of the word "lead". Good work:). And incidentally, I agree with your criticism of the lede.

Nov 20, 2008
Its refreshing to see time travel discussed seriously for a change. I don't run into many pages like this.

Kudos to Physorg

Nov 20, 2008
Time is strictly a classical concept. It is an average rate of interaction (particle exchange) among many otherwise closed systems. On the quantum level there are only those interactions, they do occur in some order, but there is no "global flow of time" that regulates them.

We presume there is a global thing called "time" when we watch two non-interacting clocks ticking at apparently the same rate. But if we look closely at the quantum level, we see that those two clocks are exchanging many virtual photons. They are parts of the same system. When we construct extremely tiny clocks, remove them from each other, and cool them down to the point that they are exchanging far fewer particles, their time rates are far less synchronized and are more independent.

Our presumption that classical time is an intrinsic part of quantum interactions, has served only to muddle our understanding of quantum mechanics.


Nov 21, 2008
Im no physisist but causality has always struck me as immutable law, yet to be understood scientifically but instinctively self-evident
(almost like gravity). Some folks like to make what I believe is a ludricrous leap from quantum behavior to something tangible traveling back in time. I would wager everything I own that its no more possible to transmit even just useful information back in time than its possible to make something from nothing (in the rigorous sense). To me it would be literally that, causing something to be that wasnt 'before'. This is how it also violates conservation of matter. And infinite parallel realms being a workaround is just as absurd. I think its all popular mythical hooey, no matter what solutions are included in the math. I know open thinking is a vital part of discovery, but I think ones energy could be more productively applied not quite so far out in the fringes of speculation. Time travel in the 'controversial' sense is strictly about going backwards, not speeding up, slowing down, or other aspects. Those are more practical topics. I for one would love it if human hibernation were possible, as myself and others could use the benefits future medicine will provide, not to mention the compound interest :).

Nov 21, 2008
i'm a bit confused.if you off your granpa then at what point do you cease to exist?let say the the instant(sic)the lead leaves the gun?the instant you start to squeeze the trigger?the instant you make the consious decision to fire.whatever consious means you may be able to think yourself out of here.what did i just write?

Nov 21, 2008
If conventional time travel were possible we would be cooked by radiation from the past and future...right?

Nov 21, 2008
Sigh.... Time is just a figment of man's imagination, well, the type of time discussed here. 'Time' exists in so much as an inch or an ounce exists. Can we see and measure them? Yes we can, only because we know within our minds what constitutes an inch or an ounce. They are just created measurements of physical objects. They do not exist outside of the human mind.

Time is the same thing. Time is just a measurement of regular occurrences within our universe. Also, if could not remember the past, then there would be no possibility of 'Time Travel'. If you truly think about it, the 'Past' is nothing more than memory's stored within our individual minds.

Another problem you have with %u2018Time Travel%u2019 is the failure to recognize %u2018Location Travel%u2019 as well. Let%u2019s say you wanted to start at location X and wanted to %u2018Travel%u2019 back one minute. Location X must therefore move back to its original position as of one minute ago. Where does that leave you? You must not only calculate the rotation of the Earth, but the rotation of the Earth around the Sun, the Sun around our Galaxy, Our Galaxy through Space, etc.
So, to %u2018Travel back in Time%u2019, unless you continue to be part of that space-time, you may have a bit of a problem. If you stay part of that space-time, then %u2018Time Travel%u2019 into the past would be just as fast as time travel into the future; i.e. one minute equals one minute.

You have a better chance of cross dimensional travel than you do of %u2018Time Travel%u2019.

Nov 21, 2008
I am not a physicist, but isn't there a problem with the law of conservation of energy? If we would put the whole universe in a large closed sphere, then the total amount of energy / mass should always remain the same. Now when time traveling; wouldn't this increase the mass / energy level on time of arrival and lower it in the time of departure.

Nov 21, 2008
The paradoxs are the result of confusing the form under which reality must be understood given our nature,.. with the reality itself. Time, space, and causality are not discoverable in themselves apart from an observer. They are forms under which reality is ordered by our minds. Space-time is the manifold of relative observations,.. not the reality apart from an observer,... that is the mistake being made by realists.

Nov 21, 2008
... and Kant understood this before relativity and QM!

Nov 21, 2008
to travel back in time would require the ability to also travel forward in time as without this feature anyone returning to the point of departure would immeadiately be returned back in time. The requirement would be to return at least a fraction of a second in the future of the departure time to prevent this looping effect. If therefore we assume that forward travel would be impossible due to the non existance of the universe or people in it at a future point this would make return impossible.
However, time would presumably not stand still while one was in the past there would be departure to "now" time where the traveler would not exist in the "now" therefore he/she could not return to that period as it was without him in the "now". In fact he would have to return to the exact micro second which we all know as "now" but the problem is the future becomes the past without any perception of the "now" instance this leads one to assume that he could not return to hid departure point in time or the "now" or into the future. which ultimately means that we would not know if anyone has travelled in time as they could not have returned to our "present".

Nov 21, 2008
@ Ant: Groundhog day!!!

Nov 21, 2008
I am sick and tired of this sort of pseudoscience being passed around as science. Every physicist worth his or her Phd should know that nothing can move in spacetime. This is the reason that Sir Karl Popper called spacetime "Einstein's block universe in which nothing happens." It is also the reason that Dr. Robert Geroch (U. of Chicago) wrote in his text book on relativity that "There is no dynamics within space-time itself: nothing ever moves therein; nothing happens; nothing changes. [...] In particular, one does not think of particles as "moving through" space-time, or as "following along" their world-lines. Rather, particles are just "in" space-time, once and for all, and the world-line represents, all at once the complete life history of the particle."

Isn't it about time that physicists stop talking about time travel? There is no time travel at all, forward or backward. There is only the changing NOW, the present. And no, we are certainly not moving toward the future at 1 second per second. Please PhysOrg, give this crackpottery a rest. It's annoying. And it does not matter if Stephen Hawking or some other famous scientist like Carl Sagan believes in the possibility of time travel. It is still crackpottery.

Nothing Can Move in Spacetime:

Nov 21, 2008
Bad link. Here it is again.

Nothing Can Move in Spacetime:

Nov 22, 2008
well said Traveler!
They confuse science with science fiction, Too much TV which they confuse with reality. when someone can define the time legnth of "NOW"/the present then I will beleive there is some merit to research on the subject.

Nov 22, 2008
IAMNAP but is there such a thing as a Planck-time? And if there is, is it the shortest interval of time measureable?

Nov 22, 2008
time travel is the most complete and utter bullshit there could ever be.

Nov 23, 2008

The space-time block universe does not exclude time-travel. Time travel would simply be the case in which space-time has singular points. If we imagine space as a 2-D sheet and the third (to us) dimension as time (for the flat-worlders on the sheet), then a time machine would act like a black hole in the origin time slice, and like a white hole in the destination time slice. One sheet would be connected to another by the time machine (which, by the way, would only work in one direction in order for an object's position to be a (possibly discontinuous) function of its proper time.) So, in the block version, a universe in which time travel to the past has occurred would have singularities at the points of origin and destination of the time machine.

Not that I can think of any ways to build a time machine.

Nov 23, 2008
Iomed, you got to be kidding me. What part of "nothing can change in a block universe" do you not understand?

What makes spacetime a block universe is the time dimension. Contrary to intuition and common wisdom, a time dimension makes change or motion impossible. If you don't get it, don't fret. Most people don't.

Nov 23, 2008
sometimes, I consider the ramifications of a density-gradient/scalar-vector based "layered" construction of "energy" into particles/matter in conjunction with the lack of a "time-dimension"(as traveler mentioned). The thoughts that come to mind are quite interesting.

If one so chooses, for the moment, ponder the "perpetual now", no past/future, then leave behind any taking-for-granted that matter is "physical matter" as we understand, then much can come in the way of creative insights.... or at least some entertaining thoughts.

Nov 24, 2008
I am always very excited when I read articles about quantum computing. In this article their hypotheses are well explained and seem reasonable. But, I really wonder if any concrete work is done so far about the topic. Do we apply same methods? [Basic gate logics, VLSI etc.]

Nov 24, 2008
Traveler: Even if our universe is a block universe (and that is debatable), that wouldn't preclude the possibility of time travel. All that would mean was that in the static universe the world-line of a particle (or macro object) wrapped around itself instead of being linear in the forth spacial dimension.

Nothing would change, and the world-line of the particle wouldn't move, but from the particle's point of view it would make a loop through time, since it's effective direction would have changed.

Nov 29, 2008
Call me old-fashioned if you want, but time travel ain't happenin'.

Nov 30, 2008
Iomed, you got to be kidding me. What part of "nothing can change in a block universe" do you not understand?

What makes spacetime a block universe is the time dimension. Contrary to intuition and common wisdom, a time dimension makes change or motion impossible. If you don't get it, don't fret. Most people don't.

The main point of my post was:
So, in the block version, a universe in which time travel to the past has occurred would have singularities at the points of origin and destination of the time machine.

Which I don't think implies change or motion. Granted, the wording of the sentence isn't all that great, but the idea is that the block universe would have singularities in the space-time regions corresponding to the space and time in which the time machine operates. If the time machine were based on wormhole manipulation (through time-dialation one mouth to form a two-way time machine) one would likely need to include at least one more spatial dimension, with the benefit of not having singularities (at least intrinsically, or so I think.)

Dec 03, 2008
I don't understand how the block universe prevents time travel more than it prevents space travel. We're all "particles" on our own world lines. We're just bigger. We're in no way
different than particles that accelerate in the presence of some force. We just don't realise what the forces are (nothing spiritual implied, mind you!) and probably our movements are more complicated. That's why, if we manage to build a time machine, then closed time loops exist and we found a use for them. Just as we found a use of electricity. If we don't find a way to do it, CTC either doesn't exist or more likely, we're not smart enough to find a way to use it.

I'm not saying we should, or that they exist. But the whole idea of causality is ill-defined. After all, causal relations are defined only as part of the light-cone of a particle. How this defines causality? What happens with your world line is very dependent of the space-time you're in. If you manage to meet a CTC then your world line will probably go crazy. But this isn't a property of YOU, it's a property of the metric so to say. Your psychic is not a problem of Nature! If you consider space-time freak-outs in the presence of a black hole for real, for example, where's the problem to consider CTC for real?
Nature doesn't have any obligation to protect your worldline and keep is out of troubles. I personally think that if you manage to run on a paradox, the Nature will flatten it out with the least possible tension. Like killing you off in some nasty way and radiate your perturbation back to infinity. Not such a big deal! Some people simply tend to think Universe for more fragile than it is.

Also,I would like to discuss the article. Did I understand correctly that if you feed the right answer into the quantum time pc, it will either give you the right answer or a random one? This sounds soooooooo useful :)

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