Is There Anything Beyond Quantum Computing?
Credit: Marcin Wichary/Flickr, under a Creative Commons license.
Now, I’m emphatically not asking a philosophical question about whether a computer could be conscious, or “truly know why” it gave the answer it gave, or anything like that. I’m restricting my attention to math problems with definite right answers: e.g., what are the prime factors of a given number? And the question I care about is this: Is there any such problem that couldn’t be solved efficiently by a quantum computer, but could be solved efficiently by some other computer allowed by the laws of physics?
Here I’d better explain that, when computer scientists say “efficiently,” they mean something very specific: that is, that the amount of time and memory required for the computation grows like the size of the task raised to some fixed power, rather than exponentially. For example, if you want to use a classical computer to find out whether an n-digit number is prime or composite—though not what its prime factors are!—the difficulty of the task grows only like n cubed; this is a problem classical computers can handle efficiently. If that’s too technical, feel free to substitute the everyday meaning of the word “efficiently”! Basically, we want to know which problems computers can solve not only in principle, but in practice, in an amount of time that won’t quickly blow up in our faces and become longer than the age of the universe. We don’t care about the exact speed, e.g., whether a computer can do a trillion steps or “merely” a billion steps per second. What we care about is the scaling behavior: How does the number of steps grow as the number to be factored, the molecule to be simulated, or whatever gets bigger and bigger? Scaling behavior is where we see profound differences between today’s computers and quantum computers; it’s the whole reason why anyone wants to build quantum computers in the first place. So, could there be a physical device whose scaling behavior is better than quantum computers’?
The Simulation Machine
A quantum computer, as normally envisioned, would be a very specific kind of quantum system: one built up out of “qubits,” or quantum bits, which exist in “superpositions” of the “0” and “1” states. It’s not immediately obvious that a machine based on qubits could simulate other kinds of quantum-mechanical systems, for example, systems involving particles (like electrons and photons) that can move around in real space. And if there are systems that are hard to simulate on standard, qubit-based quantum computers, then those systems themselves could be thought of as more powerful kinds of quantum computers, which solve at least one problem—the problem of simulating themselves—faster than is otherwise possible.
So maybe Nature could allow more powerful kinds of quantum computers than the “usual” qubit-based kind? Strong evidence that the answer is “no” comes from work by Richard Feynman in the 1980s, and by Seth Lloyd and many others starting in the 1990s. They showed how to take a wide range of realistic quantum systems and simulate them using nothing but qubits. Thus, just as today’s scientists no longer need wind tunnels, astrolabes, and other analog computers to simulate classical physics, but instead represent airflow, planetary motions, or whatever else they want as zeroes and ones in their digital computers, so too it looks likely that a single device, a quantum computer, would in the future be able to simulate all of quantum chemistry and atomic physics efficiently.
So far, we’ve been talking about computers that can simulate “standard,” non-relativistic quantum mechanics. If we want to bring special relativity into the picture, we need quantum field theory—the framework for modern particle physics, as studied at colliders like the LHC—which presents a slew of new difficulties. First, many quantum field theories aren’t even rigorously defined: It’s not clear what we should program our quantum computer to simulate. Also, in most quantum field theories, even a vacuum is a complicated object, like an ocean surface filled with currents and waves. In some sense, this complexity is a remnant of processes that took place in the moments after the Big Bang, and it’s not obvious that a quantum computer could efficiently simulate the dynamics of the early universe in order to reproduce that complexity. So, is it possible that a “quantum field theory computer” could solve certain problems more efficiently than a garden-variety quantum computer? If nothing else, then at least the problem of simulating quantum field theory?
While we don’t yet have full answers to these questions, over the past 15 years we’ve accumulated strong evidence that qubit quantum computers are up to the task of simulating quantum field theory. First, Michael Freedman, Alexei Kitaev, and Zhenghan Wang showed how to simulate a “toy” class of quantum field theories, called topological quantum field theories (TQFTs), efficiently using a standard quantum computer. These theories, which involve only two spatial dimensions instead of the usual three, are called “topological” because in some sense, the only thing that matters in them is the global topology of space. (Interestingly, along with Michael Larsen, these authors also proved the converse: TQFTs can efficiently simulate everything that a standard quantum computer can do.)
Then, a few years ago, Stephen Jordan, Keith Lee, and John Preskill gave the first detailed, efficient simulation of a “realistic” quantum field theory using a standard quantum computer. (Here, “realistic” means they can simulate a universe containing a specific kind of particle called scalar particles. Hey, it’s a start.) Notably, Jordan and his colleagues solve the problem of creating the complicated vacuum state using an algorithm called “adiabatic state preparation” that, in some sense, mimics the cooling the universe itself underwent shortly after the Big Bang. They haven’t yet extended their work to the full Standard Model of particle physics, but the difficulties in doing so are probably surmountable.
So, if we’re looking for areas of physics that a quantum computer would have trouble simulating, we’re left with just one: quantum gravity. As you might have heard, quantum gravity has been the white whale of theoretical physicists for almost a century. While there are deep ideas about it (most famously, string theory), no one really knows yet how to combine quantum mechanics with Einstein’s general theory of relativity, leaving us free to project our hopes onto quantum gravity—including, if we like, the hope of computational powers beyond those of quantum computers!
Boot Up Your Time Machine
But is there anything that could support such a hope? Well, quantum gravity might force us to reckon with breakdowns of causality itself, if closed timelike curves (i.e., time machines to the past) are possible. A time machine is definitely the sort of thing that might let us tackle problems too hard even for a quantum computer, as David Deutsch, John Watrous and I have pointed out. To see why, consider the “Shakespeare paradox,” in which you go back in time and dictate Shakespeare’s plays to him, to save Shakespeare the trouble of writing them. Unlike with the better-known “grandfather paradox,” in which you go back in time and kill your grandfather, here there’s no logical contradiction. The only “paradox,” if you like, is one of “computational effort”: somehow Shakespeare’s plays pop into existence without anyone going to the trouble to write them!
Using similar arguments, it’s possible to show that, if closed timelike curves exist, then under fairly mild assumptions, one could “force” Nature to solve hard combinatorial problems, just to keep the universe’s history consistent (i.e., to prevent things like the grandfather paradox from arising). Notably, the problems you could solve that way include the NP-complete problems: a class that includes hundreds of problems of practical importance (airline scheduling, chip design, etc.), and that’s believed to scale exponentially in time even for quantum computers.
Of course, it’s also possible that quantum gravity will simply tell us that closed timelike curves can’t exist—and maybe the computational superpowers they would give us if they did exist is evidence that they must be forbidden!
Simulating Quantum Gravity
Going even further out on a limb, the famous mathematical physicist Roger Penrose has speculated that quantum gravity is literally impossible to simulate using either an ordinary computer or a quantum computer, even with unlimited time and memory at your disposal. That would put simulating quantum gravity into a class of problems studied by the logicians Alan Turing and Kurt Gödel in the 1930s, which includes problems way harder than even the NP-complete problems—like determining whether a given computer program will ever stop running (the “halting problem”). Penrose further speculates that the human brain is sensitive to quantum gravity effects, and that this gives humans the ability to solve problems that are fundamentally unsolvable by computers. However, virtually no other expert in the relevant fields agrees with the arguments that lead Penrose to this provocative position.
What’s more, there are recent developments in quantum gravity that seem to support the opposite conclusion: that is, they hint that a standard quantum computer could efficiently simulate even quantum-gravitational processes, like the formation and evaporation of black holes. Most notably, the AdS/CFT correspondence, which emerged from string theory, posits a “duality” between two extremely different-looking kinds of theories. On one side of the duality is AdS (Anti de Sitter): a theory of quantum gravity for a hypothetical universe that has a negative cosmological constant, effectively causing the whole universe to be surrounded by a reflecting boundary. On the other side is a CFT (Conformal Field Theory): an “ordinary” quantum field theory, without gravity, that lives only on the boundary of the AdS space. The AdS/CFT correspondence, for which there’s now overwhelming evidence (though not yet a proof), says that any question about what happens in the AdS space can be translated into an “equivalent” question about the CFT, and vice versa.
This suggests that, if we wanted to simulate quantum gravity phenomena in AdS space, we might be able to do so by first translating to the CFT side, then simulating the CFT on our quantum computer, and finally translating the results back to AdS. The key point here is that, since the CFT doesn’t involve gravity, the difficulties of simulating it on a quantum computer are “merely” the relatively prosaic difficulties of simulating quantum field theory on a quantum computer. More broadly, the lesson of AdS/CFT is that, even if a quantum gravity theory seems “wild”—even if it involves nonlocality, wormholes, and other exotica—there might be a dual description of the theory that’s more “tame,” and that’s more amenable to simulation by a quantum computer. (For this to work, the translation between the AdS and CFT descriptions also needs to be computationally efficient—and it’s possible that there are situations where it isn’t.)
The Black Hole Problem
So, is there any other hope for doing something in Nature that a quantum computer couldn’t efficiently simulate? Let’s circle back from the abstruse reaches of string theory to some much older ideas about how to speed up computation. For example, wouldn’t it be great if you could program your computer to do the first step of a computation in one second, the second step in half a second, the third step in a quarter second, the fourth step in an eighth second, and so on—halving the amount of time with each additional step? If so, then much like in Zeno’s paradox, your computer would have completed infinitely many steps in a mere two seconds!
Or, what if you could leave your computer on Earth, working on some incredibly hard calculation, then board a spaceship, accelerate to close to the speed of light, then decelerate and return to Earth? If you did this, then Einstein’s special theory of relativity firmly predicts that, depending on just how close you got to the speed of light, millions or even trillions of years would have elapsed in Earth’s frame of reference. Presumably, civilization would have collapsed and all your friends would be long dead. But if, hypothetically, you could find your computer in the ruins and it was still running, then you could learn the answer to your hard problem!
We’re now faced with a puzzle: What goes wrong if you try to accelerate computation using these sorts of tricks? The key factor is energy. Even in real life, there are hobbyists who “overclock” their computers, or run them faster than the recommended speed; for example, they might run a 1000 MHz chip at 2000 MHz. But the well-known danger in doing this is that your microchip might overheat and melt! Indeed, it’s precisely because of the danger of overheating that your computer has a fan. Now, the faster you run your computer, the more cooling you need—that’s why many supercomputers are cooled using liquid nitrogen. But cooling takes energy. So, is there some fundamental limit here? It turns out that there is. Suppose you wanted to cool your computer so completely that it could perform about 1043 operations per second—that is, one about operation per Planck time (where a Planck time, ~10-43 seconds, is the smallest measurable unit of time in quantum gravity). To run your computer that fast, you’d need so much energy concentrated in so small a space that, according to general relativity, your computer would collapse into a black hole!
And the story is similar for the “relativity computer.” There, the more you want to speed up your computer, the closer you have to accelerate your spaceship to the speed of light. But the more you accelerate the spaceship, the more energy you need, with the energy diverging to infinity as your speed approaches that of light. At some point, your spaceship will become so energetic that it, too, will collapse into to a black hole.
Now, how do we know that collapse into a black hole is inevitable—that there’s no clever way to avoid it? The calculation combines Newton’s gravitational constant G with Planck’s constant h, the central constant of quantum mechanics. That means one is doing a quantum gravity calculation! I’ll end by letting you savor the irony: Even as some people hope that a quantum theory of gravity might let us surpass the known limits of quantum computers, quantum gravity might play just the opposite role, enforcing those limits.
Go Deeper
Editor’s picks for further reading
Computer History Museum
Explore 2000 years of computer history at the web site of this unique Mountain View, California museum.
Quantum Computing Since Democritus
Described by its author as “a candidate for the weirdest book ever to be published by Cambridge University Press,” Scott Aaronson’s book is a romp through the past and present of math, physics, and computer science.
The New York Times: Quantum Computing Promises New Insights, Not Just Supermachines
In this essay, Scott Aaronson argues that the popular conception of quantum computers “misses the most important part of the story,” and that the greatest payoff may be a deeper understanding of quantum mechanics.
No comments:
Post a Comment