TY - GEN

T1 - Upper bounds on the noise threshold for fault-tolerant quantum computing

AU - Kempe, Julia

AU - Regev, Oded

AU - Unger, Falk

AU - De Wolf, Ronald

PY - 2008

Y1 - 2008

N2 - We prove new upper bounds on the tolerable level of noise in a quantum circuit. Our circuits consist of unitary k-qubit gates each of whose input wires is subject to depolarizing noise of strength p, and arbitrary one-qubit gates that are essentially noise-free. We assume the output of the circuit is the result of measuring some designated qubit in the final state. Our main result is that for p > 1 - Θ(1/√k), the output of any such circuit of large enough depth is essentially independent of its input, thereby making the circuit useless. For the important special case of k = 2, our bound is p > 35.7%. Moreover, if the only gate on more than one qubit is the CNOT, then our bound becomes 29.3%. These bounds on p are notably better than previous bounds, yet incomparable because of the somewhat different circuit model that we are using. Our main technique is a Pauli basis decomposition, which we believe should lead to further progress in deriving such bounds.

AB - We prove new upper bounds on the tolerable level of noise in a quantum circuit. Our circuits consist of unitary k-qubit gates each of whose input wires is subject to depolarizing noise of strength p, and arbitrary one-qubit gates that are essentially noise-free. We assume the output of the circuit is the result of measuring some designated qubit in the final state. Our main result is that for p > 1 - Θ(1/√k), the output of any such circuit of large enough depth is essentially independent of its input, thereby making the circuit useless. For the important special case of k = 2, our bound is p > 35.7%. Moreover, if the only gate on more than one qubit is the CNOT, then our bound becomes 29.3%. These bounds on p are notably better than previous bounds, yet incomparable because of the somewhat different circuit model that we are using. Our main technique is a Pauli basis decomposition, which we believe should lead to further progress in deriving such bounds.

UR - http://www.scopus.com/inward/record.url?scp=49149125223&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=49149125223&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-70575-8_69

DO - 10.1007/978-3-540-70575-8_69

M3 - Conference contribution

AN - SCOPUS:49149125223

SN - 3540705740

SN - 9783540705741

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 845

EP - 856

BT - Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings

T2 - 35th International Colloquium on Automata, Languages and Programming, ICALP 2008

Y2 - 7 July 2008 through 11 July 2008

ER -