Reasonable quantum computing target?

Hal Finney (
Tue, 24 Mar 1998 11:10:38 -0800

I want to make a claim on the FX site (the current name for the game
based on Robin Hanson's Idea Futures) about quantum computing. There
is nothing there now except insofar as it would affect some of the
factoring and other crypto claims.

I need to define what is meant by a quantum computer, set a minimum of
performance and capacity, and choose a date. People will then bet on
whether such a machine will exist by the specified date.

The quantum computer's capacity can be measured in qubits, which are
capable of being put into a superposition of two states. It also needs
to have one or more operators which can change the states of the bits.
The operators have to be "universal" in the sense that any possible
logical operation can be created by combining the operators appropriately.

It also needs to be possible to prepare the qubits in a desired initial
state, and to read the state of at least some of them at the end of the

The computer's performance will be limited by noise and by coherence time.
Operations will not be perfectly reliable due to noise, and over time,
interactions with the environment will also destroy the coherence of
the quantum superpositions. These can be addressed to some extent by
using quantum error correction.

My idea is to specify some minimum number of logical qubits, perhaps
about 50, and some minimum number of operations which can be done by
the computer before coherence is lost. Doing error correction requires
redundancy, and so more than 50 actual qubits may be needed in order to
give the effect of 50 logical bits. I don't have a good sense for how
many operations would be a good target, or even how to count operations
since different machines may have operators with differing amounts
of power.

Another approach would be to require successfully factoring a 50 bit
number using Shor's algorithm or some improvement. I'm a little worried
though that someone would claim that since the quantum computer is allowed
to be aided by a non-quantum computer (which I think actually happens
in Shor's algorithm) and since factoring 50 bit values is trivial on an
ordinary computer, they might argue that the claim was already satisfied.
Some players delight in finding loopholes in claims, although I think
it ruins the game.

Looking at some of the recent work,
it is pretty amazing what is happening in this field. I have been
skeptical about quantum computing, but the pieces appear to be falling
into place. I am thinking of a 5 year target for the 50 qubit computer.
Does that seem too short? If so I might reduce the number of qubits to
keep the claim within a reasonably short time frame.

Any comments or suggestions are most welcome!