Error scaling in fault tolerant quantum computation

The threshold theorem states that quantum computations can scale robustly in the presence of certain types of noise processes (e.g., Markovian) as long as the probability of error for each physical component remains below a critical threshold. To satisfy this threshold a theoretical circuit requiring O(s) idealized noiseless gates can be implemented with O(s polylog s) gates to maintain an error rate that is constant with increasing s. In this paper, we argue that maintaining a fixed error rate is necessary but not sufficient to preserve complexity results obtained under an assumption of noiseless gates. Specifically, we show that nontrivial quantum algorithms exhibit nonlinear sensitivity to any circuit error and that this sensitivity affects algorithmic complexity. The joint effects of circuit error and quantum-algorithmic iteration are examined for the case of quantum search, and more complete complexity results are derived.