SOME problems are hard. So hard that they defeat the most powerful computers. If you want to work out why a long protein folds up into one particular shape, for example, you can wire together as many modern supercomputers as you like and you’ll still be waiting many times the age of the Universe for an answer.
Even quantum computers are unlikely to be much better. A quantum computer – if one can ever be built – will exploit the multiple existences of quantum states to solve certain kinds of problem with lightning speed. But there is still a huge class of problems for which a quantum computer would, in practice, be little better than a good old PC.
There is an answer, however. Earlier this year Todd Brun, who studies quantum information and computing at the Institute for Advanced Study in Princeton, New Jersey, was musing on how the underlying physics of a computer affects its power. If quantum is better than classical, what might be better than quantum?
Advertisement
“As long as one is speculating, one might as well speculate wildly,” says Brun. So he did, and came up with a computer that can travel in time. When he worked out what this hypothetical hardware might be able to do, he was rather surprised: it can do anything.
It’s not surprising that a computer connected to a time machine can give you a fast answer. You just need to write an ordinary program, and add a final instruction to send the answer back in time when it is found. That way you can have the answer as soon as you set the program going – or even earlier. What is even more impressive is that, thanks to Brun’s cunning programming skills, the computer never even has to do the computation.
His basic time-travelling program looks like this:
-
Before carrying out any computation, check if the answer has been sent back from the future. If it has, skip to the end.
-
If not, carry out the calculation by brute force.
-
When the answer is finally found, send it back in time to step 1.
As with all time-travel ideas, there is a paradox here. If the answer isn’t found at step 1, then the computer works it out and sends it back to step 1; therefore it must be found at step 1. A contradiction, surely?
But look at it another way. If the answer is found at step 1, there is no contradiction. “If one requires that the laws of physics be logically consistent, then the answer must be found,” says Brun.
That does have a bizarre consequence, though. The computer doesn’t have to lift a digit because step 2 is never executed. For the Universe not to be wrecked on a logical inconsistency, the answer must be there. Yet without step 2, the program would not work.
So where did it come from? This is an old problem in discussions of time travel. There is the story where an inventor receives from the future a set of the instructions on how to build a time machine. So they build it, and then send themselves the instructions. Where did the blueprints originate? The answer is nowhere. It’s an odd and somehow unsatisfying situation, but it is logically consistent.
This is one of the reasons why Brun is so impressed with the time-travelling computer. All other notions of time travel founder because of the paradoxes they throw up. If you went back in time and tried to kill your grandfather before you were born, for instance, something would have to intervene to stop you. Problems such as this make most kinds of time travel seem improbable. “I suspect that if you could send something as large and complex as a person, the conditions that make our usual existence possible would be disrupted,” Brun says.
But Brun’s computer works precisely because of logical consistency. Indeed, he thinks this peculiar characteristic might make it the only kind of time machine that can exist.
One restriction is unavoidable, though. As with any time machine, you need a “closed time-like curve”, effectively a loop in time. That means the computer can only visit a certain stretch of time – the amount contained within the loop – and so can only carry out calculations that can be done within that time.
This is a bit of a problem. If the computer would never have been capable of carrying out step 2 within the allotted time, the logic breaks down and you get no answer. And remember that some tasks would take a ridiculously long time. Even if you get hold of a time loop billions of years long, and build a computer that will not fall apart after six months and that will withstand asteroid impacts and being eaten by the Sun, and any number of other calamities, you might find that a few billion years is far too brief.
There is a way out, though. Almost any mathematical problem can be broken down into smaller pieces. Solve one, and you can use the answer as the input to the next stage, and so on until you get the final answer. So for the time-travelling computer, you can break a problem down so that each piece is small enough to be done within the time loop available. Then write the program so that the answer to the smallest piece would be output before it gets done. That answer forms the input for the next run-through, and so on. Once more, logic implies that you get the final answer at the beginning, without the program ever running.
That means the time machine can breeze through problems such as protein folding, finding the shortest routes between a set of cities, and making deductions from a set of logical propositions. These problems, which belong to a class called “NP hard”, are notoriously difficult for ordinary computers to solve, but would be a breeze if only your computer could travel through time.
Just one tiny snag remains: a loop in time isn’t exactly an off-the-shelf component. Many physicists doubt that such a thing can ever be created, and even if it is possible in principle it might in practice mean carrying out some exotic, outrageous – and, let’s face it, unimaginable – feat, such as travelling through wormholes in space-time.
Brun’s only other doubt about his machine is that it seems just too good to be true. “It’s just a gut feeling, but this computer is too efficient at solving problems with no effort,” he says. He has yet to find a fundamental flaw, though, and has submitted the paper to Foundations of Physics. Whether or not he has also submitted a request to Santa Claus, he won’t say.