My Washington 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 [almost] 100 years. It’s hard to get across with newspaper-friendly analogies.
Quantum mechanics is a 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. 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. [But in quantum mechanics], 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 [a bunch of numbers called amplitudes]. 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.