The belief that quantum computation is possible in practice is founded strongly on a set of theorems that are generally called ‘the’ Threshold Theorem for Fault-Tolerant Quantum Computation. Though there is non-trivial variation between threshold theorems based on differing assumptions about the errors that will affect the quantum computer, the essential content of ‘the’ theorem is that errors can be efficiently corrected if they are small enough.
‘Smallness’ is a vague term. Different performance metrics may disagree about whether one type of error is truly ‘larger’ than another, so discussion on the smallness of error can easily descend into meaningless apples-versus-oranges comparisons. The distinction between performance metrics is nonetheless tangential to the essential content of the Threshold
Theorem because the theorem guarantees only existence. Indeed, the actual threshold value depends not only on the choice of performance metric but also on the nature of errors that can affect the quantum computer as well as the choice of universal gate set. To the best of
my knowledge, no reliable technique for estimating a threshold has ever been established.
My purpose is to explain the ‘essential content’ of ‘the’ Threshold Theorem. By ‘essential content’, I mean those aspects of the theorem which justify a belief that quantum computing is indeed possible in practice. I divide this essential content into two categories: promises
about the noise affecting a device and the guarantee that a given quantum circuit can be altered so as to be robust against the promised noise model. This essay discusses only the second point; the first is rather more complicated. I may discuss noise in a follow-up essay.
For the sake of definiteness, I focus on a specific (though somewhat rough) formulation of the theorem given by Aharonov and Ben-Or in 2008:
Thus a given function can be computed to within a specified total variation distance with polylogarithmic overhead in the presence of “local noise” with a small enough error rate. The guarantee of the Threshold Theorem is that “small enough” is non-zero. More formally, the theorem guarantees that a quantum circuit Q’ can be found for every quantum circuit Q such
that Q and Q’ are ε-equivalent and the overhead of Q’ with respect to Q is polylogarithmic.
To explain the meaning of ε-equivalence, I must first point out that a quantum circuit is a set of instructions about how to operate on a quantum register. Although Q and Q’ are distinct instructions, they are considered approximately equal if they execute almost the same function on the input. The nearness of the two functions can be measured in a variety of ways, but ε refers to a particular metric on the space of functions that Aharonov and Ben-Or call the ‘total variation distance’. This appears to be a minor mistake in the paper.
Aharonov and Ben-Or refer to total variation distance as a metric on the space of probability distributions or, more generally1, over the space of density matrices. This definition does not apply directly to functions. My understanding is that Q and Q’ are computing the functions f and f’, respectively, on a register with a state represented by x. Thus f(x) and f’(x) are states of the output register that can be represented as density matrices. The total variation distance between f(x) and f’(x) is well-defined, but the total variation distance between f and f’ was not
clearly stated as far as I could tell (though I may have missed something). When Aharonov and Ben-Or refer to the total variation distance between f and f’, they seem to be referring to the maximum over x of the total variation distance between f(x) and f’(x). This is a perfectly reasonable metric on the space of functions over a finite domain, but it can easily be
conflated with the total variation of a function — an inequivalent concept.
Thus ε expresses the maximum possible deviation between the output of Q and the output of Q’. The Threshold Theorem is then guaranteeing that a given circuit Q can be cost-efficiently approximated by a circuit Q’ to within ε total variation distance.
What does it mean for Q’ to be cost-efficient? I first need to explain the meaning of cost for a quantum circuit, which is analogous to the cost of a classical circuit. A circuit is a labelled directed acyclic graph, each of whose nodes represent a logic gate. The size of a circuit is the number of nodes of the graph, the depth of the circuit is the longest path between an input
and output node, and the width of a circuit is (roughly) the maximum number of gates to be executed simultaneously. The theorem then states that the cost of Q’ is polylogarithmic (i.e., a polynomial of the logarithms of the variables) in the cost of Q as well as in 1/ε.
Based on the above discussion, I can summarize much of the content of the Threshold Theorem as a statement that Q’ can be found for every Q and ε > 0 that is cost-efficient and approximates Q to within total variation distance ε in the presence of small local noise.
Though I am avoiding a full discussion of “small local noise”, I at least point out that local noise is noise that affects each gate independently. This locality assumption together with a guarantee that the effect of noise is small enough is enough to ensure that Q’ operates correctly even in the presence of such noise. Not only are Q’ and Q are ε-equivalent, but Q’
plus noise of the promised form is ε-equivalent to Q. Furthermore, the amount of tolerable noise is independent of the target total variation distance ε.
1 The relationship between the definition of total variation distance used by Aharonov and Ben-Or was established by Fuchs and van de Graaf, though they call it the “Kolmogorov distance”.