(This is the second of two background posts for a peer-reviewed research blogging post that has now slipped to tomorrow. I started writing it, but realized that it needed some more background information, which became this post. And now I don’t have time to write the originally intended post…)
Making a quantum computer is a tricky business. The process of quantum computing requires the creation of both superposition states of individual quantum bits (in which the “qubit” is in some mixture of “0″ and “1″ at the same time) and also entangled states of different qubits (states where the state of one qubit depends on the state of another bit so that measuring one absolutely determines the value of the other). The only way to do this is to have some sort of controllable interaction between the qubits in your quantum computer, but once they’re created, these states are extremely fragile, and the only way to keep them around long enough to finish a calculation is to shield them from interactions with the outside world. But, of course, at the end of the day, you need to be able to get your answer out of the quantum computer, which requires interaction with the world outside the machine…
Finding the right sort of system, and getting everything to work in the right way, is an incredibly fiddly balancing act. You need to have just the right amount of interaction, and just the right amount of coupling, but if you’re too far off in one direction or another, the whole thing falls apart.
A few years back, a group from Los Alamos created a “Road Map for Quantum Computation laying out the state of research, and what you need to make a practical quantum computer in very clear language. The detailed notes about research are kind of dated now– a lot has been accomplished since the 2004 publication of the “Road Map”– but the list of qualities that a workable system needs to have is still as good a description as I’ve seen. This takes the form of five “criteria” originally listed by David DiVincenzo of IBM:
- A scalable physical system with well-characterized qubits.
- The ability to initialize the state of the qubits to a simple fiducial state.
- Long (relative) decoherence times, much longer than the gate-operation time.
- A universal set of quantum gates.
- A qubit-specific measurement capability.
These can probably use a little unpacking…
A scalable physical system with well-characterized qubits. A “qubit” is basically any quantum system that has two distinct states that can be used as the “0″ and “1″ for computation. These should ideally be long-lived states– there’s not much point to making a computer whose “bits” decay back to zero in a matter of nanoseconds– and you would like it to be as close to a two-level system as possible. As Bill Phillips was once misquoted, “there are no two-level atoms, and sodium is not one of them,” so it’s almost impossible to find real two-level systems, but you can find lots of systems where there are two levels that are well away from any other states in the system, and that’s good enough.
“Well-characterized” means that you should know what the states are, where they are, and what possible interactions they have. If there’s some other state or outside factor that can affect the states, you need to know about it.
“Scalable” means that you need to be able to stick a lot of qubits together. The killer app for a quantum computer is the factoring of very large numbers for code-breaking, and this will require hundreds of qubits even under ideal circumstances (about 330 just to represent a 100-digit number to be factored), and probably thousands of qubits if you want to use error correction techniques to protect your calculation. A candidate quantum computer system that only allows a maximum of 10 qubits isn’t much more than a toy.
The ability to initialize the state of the qubits to a simple fiducial state. The nature of quantum measurement means that once you start a computation, you can’t just look at the system partway through and make sure it’s working properly. All you can do is set the system up, and run through a prescribed series of operations, then look at the end result, and see if that’s the answer you wanted.
As a result, it’s absolutely critical to be able to “initialize” the quantum computer. You typically imagine setting the bits to “00000000…” but it could be anything at all– “1101001010111…..” is perfectly fine, as long as you know exactly what state you start with, and can get exactly that state every time you start out. If your initialization process doesn’t give the same result every time, you’ll never be sure whether you actually ran the right calculation.
Long (relative) decoherence times, much longer than the gate-operation time. “Decoherence” refers to the tendency of quantum states to fall apart over time due to interactions with the environment. If you create a quantum superposition state consisting of some mixture of “0″ and “1,” and wait a while, you’ll find that it ends up in either “0″ or “1,” with some probability. You need the superposition states to do quantum computing, so this is a Bad Thing.
In order to be able to complete a computation, you need to do lots and lots of operations, each of which takes some finite time (the “gate-operation time”). The time it takes a superposition of two qubit states to fall apart (the “decoherence time”) needs to be longer than the time it takes to run all the operations for the calculation you want to do, otherwise your computer will lose its quantum nature partway through, and then you’re screwed.
A universal set of quantum gates. “Gates” is a term of art meaning “operations on one or more qubits.” A “universal set of gates” is the smallest number of possible operations that you need in order to be able to do any computation you want.
There are a couple of ways of doing this, but one example of a “universal set” of gates is a rotation operation (that takes a “0″ to a “1″ or any arbitrary superposition of “0″ and “1″) plus a “controlled-NOT” operation (that flips the state of a target bit only if a second, “control” bit is 1). If you have a way to do those two operations on your system, you can do absolutely any operation you want to do, in the same way that you can do any classical computing operation using NAND gates.
A qubit-specific measurement capability. Once you’ve done the computation, you need to read the answer out. In order to do this, you need some way of measuring the state of each and every qubit individually. A computer that doesn’t let you find out the result of the computation isn’t much good.
There are a bunch of different schemes out there for doing quantum computation, none of which have managed to meet all of these criteria yet (to the best of my knowledge). All of them have different strengths and weaknesses, and some of them have obvious paths forward toward meeting these criteria, while others really have no clear road to progress.
At present, there is still no obvious perfect system for building a quantum computer, but I’ll post some peer-reviewed blogging tomorrow talking about a particularly cool idea for a candidate system.