  We show how the execution time of algorithms on quantum computers depends on
the architecture of the quantum computer, the choice of algorithms (including
subroutines such as arithmetic), and the ``clock speed'' of the quantum
computer. The primary architectural features of interest are the ability to
execute multiple gates concurrently, the number of application-level qubits
available, and the interconnection network of qubits. We analyze Shor's
algorithm for factoring large numbers in this context. Our results show that,
if arbitrary interconnection of qubits is possible, a machine with an
application-level clock speed of as low as one-third of a (possibly encoded)
gate per second could factor a 576-bit number in under one month, potentially
outperforming a large network of classical computers. For nearest-neighbor-only
architectures, a clock speed of around twenty-seven gates per second is
required.

Quantum Physics