January 3, 2014
Confused about the NSA’s quantum computing project? This MIT computer scientist can explain.
Timothy B. Lee
Washington Post, January 3, 2014
My Washinton Post colleagues have reported on an National Security Agency program to to build a quantum computer. In principle, the unique capabilities of a quantum computer could allow it to easily crack cryptographic codes that cannot be cracked by even the most powerful conventional computers.
But right now, quantum computing is more a theoretical research topic than a practical technology. To understand how quantum computers could work and what the implications would be if they did, I talked to Scott Aaronson. Aaronson is a Computer Science professor at the Massachusetts Institute of Technology who has written extensively about quantum computation and its implications. We spoke by phone on Wednesday. The transcript has been edited for length and clarity.
Timothy B. Lee: Let’s start at the beginning, how does a quantum computer differ from a conventional computer?
Scott Aaronson: The easiest way to say it is that a quantum computer would exploit quantum mechanics, laws of physics that are not familiar in everyday life but have been familiar to physics for more than 100 years. It’s hard to get across with newspaper-friendly analogies.
Quantum mechanics is the framework for subatomic physics which is probabilistic. You can only calculate the probability that an electron or proton will be in a certain place when you make a measurement with certainty. That’s not the most important part of it. We use probability all the time in everyday life.
But quantum mechanics has a completely different way to find probability. People talk about a 20 percent chance of rain tomorrow. But nobody talks about a negative 20 percent chance of rain. That would be nonsense. To find the probability that a photon will be found on the screen or the probability that a computer will come up with a particular number, you have to add up something called amplitude. Amplitudes can be positive or negative, or even complex numbers. What’s important is there are different ways that something can happen, and some of those ways have positive amplitude and some have negative amplitude. They can cancel each other out.
That’s the thing that’s totally unfamiliar to us. [In a famous physics experiment called the double-slit experiment], the two slits that the light can travel through can interfere with each other with the result that the light isn’t there at all. If you close one of the slits, you do see light there because you no longer have this interference. By decreasing the number of ways that a photon can get to a certain point, you can increase the chance that it will be found at a point. That’s what interference means.
The idea with quantum computing is to exploit the phenomenon of interference which is the core of quantum mechanics on a massive scale. To try to choreograph a whole computation, not just two possibilities with two slits of light to go through, but 2 to the 1000th power. What you could try to do is arrange things for each so of the wrong answers, some have positive amplitude and some have negative amplitude. So those would cancel each other, [while states representing the] right answer would be in phase with each other.
If you arrange that, then when you measure the computer, the right answer will be found with high probability. So that’s the idea.
This is different from what most of the popular articles describe. Most of them take this lazy way out, they say a quantum computer will be unlike a classical one because it will explore all the possible answers in parallel. That’s not a good way to describe it because you have to measure the computer.
While you can in some sense try every possibility in parallel, there’s a sense in which that’s true, but as soon as you make a measurement, you’re going to see one of these answers, not all of them. You could get a random answer. So the only hope of getting a benefit with a quantum computer relies on this interference effect. So it’s really something subtle.
How long have people been thinking about quantum computation?
The idea of quantum computing was proposed in the 1980s by physicists like Richard Feynman and David Deutsch, but it wasn’t obvious that a quantum computer would be good for anything. The only application people could see immediately was you could use a quantum computer to simulate quantum mechanics. That’s sort of obvious.
The big discovery that sort of got people excited about this field: Peter Shor discovered in the 1990s that [if you had a quantum computer], you could use it to find the prime factors of enormous numbers. That’s a practical problem we don’t know how to solve with practical computers in any reasonable amount of time.
People care about it because the security of e-commerce is based on the difficulty of finding prime factors. If you can do that you can break most of the cryptography on the Internet.
It is important to find out that in order to develop his algorithm, Shor had to exploit very special properties of the factoring problems. So even quantum computers have significant limitations. There’s a famous class of NP-complete problems [which are among the most computationally difficult problems in computer science]. We don’t know if quantum computer will be able to [solve these problems in a reasonable amount of time].
If you could build a quantum computer and it worked according to the theory, we know for sure it could factor large numbers. There’s something special about factoring. So it’s not a matter of trying every possible divisor in quantum superposition, that wouldn’t work. You have to do something more clever to arrange this interference problem.
Shor discovered a few other quantum algorithms that give similarly dramatic speedups, for special problem. For modern cryptography, you need special algorithms to make it work.
Can you give me some concrete details about how a quantum computer works? Conventional computers are built with switches made out of transistors. Is there something similar for quantum computers?
The reason I haven’t been concrete about it is that there’s a lot of different ideas on the table about what a quantum computer could be built out of. We don’t know which of these ideas is going to be the best one. Regardless of which one, they lead to the same theory. It’s very much like if you’re in a classical computer programming, if you’re building a computer program, you don’t need to know the physics of the transistor, if that’s what you’re concerned about.
I can tell you some of the ideas. Basically what you need is some physical system. You have to be able to place it in a quantum superposition of two states. If you have such a system, you call that a quantum bit or a qubit. You have to be able to set them, you have to be able to do operations on them, and you have to be able to make pairs of the qubits talk to each other.
You have to be able to [get them] correlated or entangled. You have to be able to measure the qubits at the end to read out an answer. Finally you have to do this while keeping the qubits insulated from the external environment to maintain their characteristic.
People say that in quantum mechanics, the act of looking at something changes it. That’s a little misleading. It doesn’t have to be a conscious being. [Being exposed to the] air in the room works just as well. But if the system leaks out information into its external environment, then it loses its quantum characteristics. As soon as the system becomes too correlated with the rest of the world, then you no longer see the quantum characteristics.
This is why we don’t notice these quantum effects in day to day life. It’s why they were only discovered in the 1920s, why you have to do fairly complex experiments to notice these effects. They only come to predominate at the atomic scale. What makes it so hard is you’ve got these requirements that you’ve got to be able to do these operations while keeping things isolated from the environment.
So what ideas have people had for how to build qubits?
Different ideas are being explored in parallel. One is that you could use ions that are trapped in a magnetic field. The spin of the field, whether it’s spinning clockwise or counter-clockwise, is your qubit. You could use a laser to manipulate them. Another one is superconducting qubits. You’d have current that is in a superposition of flowing clockwise and counterclockwise. These [qubits] are much larger [than ions]. These coils would be large enough that you can see them with a magnifying glass. If you cool them to absolute zero is you can get superposition.
Another is photonics. Use optical elements like beam splitters to move information around. There are a dozen of other proposal.
You describe quantum computers as a mostly theoretical concept, but a company called D-Wave claims to have created a practical quantum computer. What’s their story?
I’ve been writing about D-Wave on my blog for the last decade. They’ve been the leaders on generating hype and generating press. For a long time they were literally a black box. We didn’t really know what was going on, they would make press announcements with these deals, they’d sell these machines to Lockheed Martin and Google. We didn’t really know.
Academics are very skeptical. They hadn’t given evidence that they were doing anything beyond what you could do with a conventional computer. They were making extravagant claims, but we didn’t see any evidence that there were really quantum effects going on or that we had a speed-up.
We know a lot more in the last year about what’s going on with these devices. After they sold to Lockheed, an independent group led by Matthias Troyer actually did independent investigations of this machine. What they found briefly is that there is pretty good circumstantial evidence that there’s some kind ofquantum annealing behavior, which means that there’s a little bit of quantumness there.
Not even D-Wave is claiming that what they have or what they’t trying to do is a full-scale quantum computer. They’re not even trying to get universal quantum computer. A universal one is one that can do any quantum computation, like Shor’s factoring algorithm. D-Wave is aiming to build something much more limited. [D-Wave uses an approach called] adiabatic optimization.
There’s no evdience that [D-Wave’s device is a] practical computer. Even if you could build this adiabatic optimization approach totally perfectly, you’d still sort of don’t really know if there’s a practically important speedup using quantum computers. It’s very different than the situation with Shor’s factoring algorithm. If you could do it, we’re extremely confident we could get this speedup. With the optimization problem, we don’t really know if we’d get a speedup. It’s going to boil down to people trying it out and seeing what happens.
Another issue: D-Wave’s hardware is nowhere close to the theoretical ideal. It’s mostly classical with a little bit of quantumness. Most of the scientists have focused on getting qubits that really work. Most people view this as basic research at this stage. That’s how I think about it.
If you can’t even build one qubit that you can really control and make work, it seems ridiculously premature to be trying to build commercial devices. But D-Wave’s approach is very different. Take the [low-quality] qubits that exist and throw them together and see what happens.
I think it’s great to try things out. Where the rubber meets the road and supposing you do that and find you don’t get a speedup. Then what happens? Unfortunately, D-Wave has taken the path of obfuscating what the issues are and counting on journalists and people in the business world not caring enough to understand. They’re just [talking about] quantum mechanics and parallel universes and it sounds cool, you know, and so people hear that Google is involved and Lockheed Martin is involved, and they don’t ask the question, “Is this really giving you a benefit over what you could do with a classical computer?”
What would be the implications for cryptography if we were able to build true quantum computers? Would today’s cryptographic algorithms be in danger?
Almost all of the public-key encryption that is currently used would be breakable in principle by a quantum computer. [A public-key, or asymmetric, encryption algorithm uses a “public key” that is published to the world and a “private key” known only to the recipient. Public-key algorithms are widely used online.]
That includes RSA, Diffie-Hellman, ElGamal, elliptic curve cryptography, and several other things also. That accounts for 99.9 percent of public key cryptography that anyone uses. That’s all breakable by a quantum computer.
On the other side, if you look at private-key cryptography, the kind where you have to agree on the key in advance, then most private-key cryptography you don’t know how to break with a quantum computer.
Even with public-key cryptography, there are proposals out there for public-key cryptosystems that could resist quantum computers. The most important is lattice-based cryptography. These are mostly theoretical. Hardly anyone uses them. The industry coalesced around RSA instead. These lattice-based systems are much less efficient. You might need a key that’s 100 megabytes or something.
The advantage is that we don’t know how to break them with a quantum computer. If quantum computing became a reality, these would be an option: Make things like lattice-based cryptography more efficient so they could compete with standards like RSA.
Another response that you could take, ironically, is to switch to quantum cryptography. It’s a completely different way of doing encryption. It uses fiber-optic cables that can transmit photons that maintain polarization. Cryptography based on quantum mechanics, the uncertainty principle. This is actually practical right now. There are companies that sell quantum crypto devices: ID Quantiqueand Magiq. People are selling these devices. They do work, but there is a limited market for them. It’s an exotic solution to a problem that most people think is solved with existing cryptography. Some people joke that the point of quantum computers is to create a market for quantum cryptography.
How much progress have scientists been making toward creating quantum computers in the lab?
I think there’s a lot of progress on the hardware side. The problem is it looks unimpressive to an outsider. Fifteen years ago, people were messing around with one or two or three qubits. That’s still what people are doing. But the one or two or three qubits are way better than they were 10 or 15 years ago. People are trying to get the qubits to behave well enough that you can start applying an idea which is called quantum error correction. That was a big discovery that convinced people that quantum computation could work.
To build a reliable, scalable quantum computer, you don’t have to get it perfectly isolated. Only have to get it very well isolated. If you can get the amount of interaction below a certain threshold, then you can start applying these very clever error-correcting codes. Assuming you’re below this threshold, it’s like you’ve passed a critical point for a nuclear weapon, you start correcting errors faster than they’re introduced. There’s this critical point where once you pass it you should be able to scale it up in principle to be as big as you want.
Until you’re at that point, nothing you do is going to be as impressive. You don’t get half a nuclear explosion if you’re below that critical mass. Experimentalist are focusing on understanding and getting real understanding of how the qubits behave with the idea being that once you have good enough qubits then you can scale it up. Until you do that trying to scale up with dirty qubits, it’s like juggling on a unicycle. It’s on impressive parlor trick good for generating headlines, but we know from the beginning that it’s going to crap out before too long.
So most people know the real goal is not to get more and more qubits, but to get better and better qubits, because that’s what’s ultimately going to be needed.
How likely do you think it is that the NSA has succeeded in creating practical quantum computers?
People have speculated about that possibility and joked about it for a long time. I don’t know. I don’t have the security clearance. But there are some things that make me think it’s not likely. One of them is that we know who the best experimentalists are, and yes the NSA is interested and talks to them and funds them, but we haven’t seen them hoovering them up like the Manhattan project.
The more important thing is that if your goal is to read peoples’ e-mail, there are so many more straightforward ways to go about that than building a quantum computer. It’s an exotic possibility that captures peoples imagination, but in reality, when these systems are broken, it’s not by bashing down the fortress, it’s by finding a back door. Finding a bug in the implementation or rigging the standards and strong-arming Microsoft and Google into just giving it backdoors. If the NSA were able to break all of this strong crypto, why would they be going to all this effort to do these things?
Snowden himself said properly implemented strong crypto is one of the things you can rely on. There are so many more prosaic possibilities I’d want to examine before considering the possibility that the NSA is building a quantum computer.
There’s also just that it looks to most of us like it’s in a basic research stage. It doesn’t look like it’s at the point where people could say here’s how much money it would take and here’s how many years it would take and we can build a device. We still don’t know. We’re still just trying to figure out which are the basic architectures. Maybe in 5 or 10 or 20 years it becomes a question of time and money and manpower and how much do people want this thing. Right now, it’s a research question of how do you do it at all.
No comments:
Post a Comment