Error scaling in fault tolerant quantum computation

详细信息    查看全文

• 作者：Marco Lanzagorta ; Jeffrey Uhlmann
• 关键词：Quantum computing ; Quantum error correction ; Fault tolerant quantum computation ; Threshold theorem ; Quantum complexity ; Quantum algorithms
• 刊名：Applied Mathematics and Computation
• 出版年：2012
• 出版时间：15 September, 2012
• 年：2012
• 卷：219
• 期：1
• 页码：24-30
• 全文大小：209 K

文摘

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.