  Dynamical decoupling pulse sequences have been used to extend coherence times
in quantum systems ever since the discovery of the spin-echo effect. Here we
introduce a method of recursively concatenated dynamical decoupling pulses,
designed to overcome both decoherence and operational errors. This is important
for coherent control of quantum systems such as quantum computers. For
bounded-strength, non-Markovian environments, such as for the spin-bath that
arises in electron- and nuclear-spin based solid-state quantum computer
proposals, we show that it is strictly advantageous to use concatenated, as
opposed to standard periodic dynamical decoupling pulse sequences. Namely, the
concatenated scheme is both fault-tolerant and super-polynomially more
efficient, at equal cost. We derive a condition on the pulse noise level below
which concatenated is guaranteed to reduce decoherence.
