The DiVincenzo Criteria
Of course, our goal is to build and use a real quantum computer, not simply sit in our armchairs and hope one magically appears. So, how hard is it to build one? What would have to do? David DiVincenzo outlined the minimum characteristics a technology must have in order to be a useful substrate.
In 1993, Seth Lloyd (then at Los Alamos National Laboratory, now at MIT) proposed a molecular quantum computer. (Note that this proposal predates the publication of Shor’s algorithm, so quantum computing was still an obscure field with only a few such visionaries working in it.) Although he built on techniques from earlier research, this was the first relatively concrete design that showed how operations might be performed. His proposal involved a chain-like molecule, in which a repeating pattern of small blocks could store data, move it up and down the chain as necessary, and execute the necessary gates. It even discusses how to read out the data, and offers some early ideas on error correction. The paper thus stands as perhaps the first true quantum computer engineering document.
The DiVincenzo list
Lloyd’s design was never built, but small experiments began appearing in the late 1990s. At that point experiments were still rather ad hoc, although it was known that error correction would be important, and the key principles of error correction and fault tolerance had been established. In the year 2000, David DiVicenzo brought clarity to the process and a unifying framework to the set of embryonic technologies with his list of criteria. They are:
- A scalable physical system with well characterised qubits.
We not only have to have a single decent qubit, we need the ability to create a set of them.
- The ability to initialise the state of the qubits to a simple
This is the equivalent to the reset button on your computer. If you can’t create a clean state to start with, it’s hard to run any sort of program.
- Long relevant decoherence times.
If you can’t keep data in memory, you can’t compute on it. This has a strong relationship to quantum error correction.
- A “universal” set of quantum gates. For a quantum computer to be completely general, you must be able to execute any algorithm asked of you. When we discussed gates back in Week 1, we vaguely alluded to this. You need to be able to rotate a single qubit to anywhere on the Bloch sphere, and perform some form of two-qubit gate that entangles qubits. With these capabilities, it is possible to build Toffoli gates and any large computation.
- A qubit-specific measurement capability.
If you can’t read the results out, a computer is pretty useless!
- The ability to interconvert stationary and flying qubits.
In order to transfer data over long distances, we need to be able to convert from data held in something stationary (like a computer chip) to light (photons).
- The ability to faithfully transmit flying qubits between specified
Obviously, we also need to be able to move those photons from one place to another with reasonable fidelity!
The first five are known as DiVincenzo’s computation criteria, and the last two as his communication criteria, but many scalable quantum computer designs involve connecting smaller computers together, so the communication criteria are important for computing as well.
DiVincenzo’s criteria are necessary, but alone not sufficient, criteria for a quantum computing technology to meet. I (Van Meter) outlined in my 2006 Ph.D. thesis additional criteria necessary for building a useful and attractive quantum computer. The technology must result in a computer that is small enough to be buildable (say, no larger than a football stadium), consume tolerable amounts of power (no more than a few megawatts), and cost no more than a large classical supercomputer (around US$100M). Otherwise, a system will never be realized.
As we saw at the end of our discussion on Shor’s algorithm, it also must be fast. The potential benefits in computational class beguiled many people at the beginning, and they failed to realize that slow gate times could still be anathema to systems of practical interest.
We won’t explicitly address each criterion in each upcoming article and video; assessing the complete readiness of each technology is an exercise in hitting a moving target. We encourage you to follow up on individual technologies and discuss them at the end of the course.
© Keio University