We have all been thought that if elementary physical quantum gates are sufficiently accurate, they can be assembled into a fault-tolerant circuit to simulate a perfect, logical quantum circuit. For more than a decade now, we have also known that this accuracy threshold is around p=1%. Many physical devices are now achieving this level of accuracy. However, we want our gates to be well below threshold, perhaps p=0.1% or even p=0.01%. In fact, the further away we are from the threshold, the ‘cheaper’ it is going to be to realize a fault-tolerant circuit. Indeed, in a fault-tolerant circuit, each logical gate is implemented using R physical gates, where the overhead R can be quite large, i.e., well above 1000. Estimating this overhead R is an active area of research.
I would like to answer the question: “Given a sub-threshold physical noise rate p, how much overhead R do I need to realize a given quantum algorithm?”, or to put it more crudely, “How much is fault tolerance going to cost me?” In this talk, I will show that the overhead depends critically on many aspects of the noise model, not just a single parameter p (e.g. fidelity). For instance, two CNOT gates with fidelities 99.99% may behave widely differently when assembled into a fault-tolerant circuit. Moreover, this fact is not limited to the fidelity, but to all known metrics that are used to measure the strength of the noise. These observations motivate our ongoing efforts at defining new error metrics that enable us to predict the fault-tolerance overhead.