  Estimates of the quantum accuracy threshold often tacitly assume that it is
possible to interact arbitrary pairs of qubits in a quantum computer with a
failure rate that is independent of the distance between them. None of the many
physical systems that are candidates for quantum computing possess this
property. Here we study the performance of a concatenated error-detection code
in a system that permits only nearest-neighbor interactions in one dimension.
We make use of a new message-passing scheme that maximizes the number of errors
that can be reliably corrected by the code. Our numerical results indicate that
arbitrarily accurate universal quantum computation is possible if the
probability of failure of each elementary physical operation is below
approximately 10^{-5}. This threshold is three orders of magnitude lower than
the highest known.
