Proofs of correctness for fault-tolerance schemes rarely give tight constants for error correction performance. However, they do provide formal reasoning that a scheme is correct and all the pieces fit together in the appropriate way. The combination of a proof and simulations could be said to be the gold standard for a fault-tolerance scheme.

A threshold for memory was shown in the well known paper by Dennis-Kitaev-Landahl-Preskill, but, as far as I can tell, there has not been a published threshold theorem for universal fault-tolerant computation using surface codes.

Fixing the scheme to be the usual lattice surgery + magic state distillation and considering circuit-level depolarizing noise, I am satisfied that a threshold for the lattice surgery steps nearly immediately follows from the usual LDPC threshold techniques by Kovalev-Pryadko and Gottesman.

However, in order to perform magic state distillation, we need a way of performing state injection. That is, for an arbitrary state $|\psi\rangle$, to prepare a logical state $\rho$ of a distance-$d$ surface code such that it is correctable to $|\bar{\psi} \rangle$ with probability at least $1-\epsilon$** as $d \to \infty$. There is a gadget that appears to have these properties numerically in Li's paper, but I believe it was not formally argued.

Is there a known formal proof in the literature of the existence of such a gadget?

** $\epsilon$ should be a small constant like $1/100$ such that we can use magic state distillation.

  • $\begingroup$ Isn't any encoding circuit good enough, for a sufficiently low physical noise strength? If the non-fault-tolerant encoding circuit uses N gates and the Pauli error rate per gate is less than 1/(1000N), then the injected state will necessarily be correct 99.9% of the time. That's enough for distillation to work. What's left to prove? The numerics are the proof. $\endgroup$ Commented Jun 5 at 7:15
  • $\begingroup$ I left the quantifiers slightly implicit. For threshold theorems, we are generally looking for constant physical rate and an asymptotically large logical circuit (that is, d is unbounded). I would say that state injection into an arbitrarily large code block is non-trivial since the size of any injection circuit will necessarily be increasing. $\endgroup$ Commented Jun 5 at 7:54
  • $\begingroup$ You don't inject at the operating distance, you inject at a fixed distance sufficient to hold the state long enough for a distillation factory to consume it and produce the next level state which is stored in a slightly larger patch, and so forth until reaching full size. There's no point in storing a 1e-3 state in a distance 30 surface code patch when distance 9 is sufficient. If you do inject at full size, all you need to show is short error chains near the injection site in spacetime dominate the rest of the growth due to exponential suppression of longer error chains. $\endgroup$ Commented Jun 5 at 8:01
  • $\begingroup$ I would say that this is more or less the desired solution interlaced with steps of distillation. That said, one still needs to do the growth step which IMO is slightly nontrivial. For conceptual simplicity, I’m fine with avoiding this optimization (slowly increasing distance) and doing the injection into a large surface code all at once. $\endgroup$ Commented Jun 5 at 8:18

1 Answer 1


A sketch of one sub-optimal construction follows by repurposing known techniques in roughly the following way:

  • Define an error correction (EC) gadget on distance-$d$ surface codes by $d$ rounds of syndrome extraction followed by minimum-weight decoding and application of the correction. If the noise rate (on both the input and the gates) is below a threshold value $p^*$, then the probability the output state is uncorrectable** is at most $e^{-\alpha d}$ for some $\alpha > 0$. Furthermore, there is a bound on the output noise rate in the event it is correctable.
  • Define a "growth" gadget to be the unitary circuit that takes a distance-$d$ surface code to a distance-$(d+1)$ surface code. This requires a layer of CNOTs, so existing errors are spread to at most one other qubit. If the input noise rate is $p$ then the output noise rate*** is some fixed polynomial in $p$ $\mathrm{poly}(p)$.
  • The state injection gadget will be the non-fault-tolerant encoding of some arbitrary state $|\psi \rangle$ into a distance-3 surface code followed by repeated alternate application of EC and growth gadgets until the distance reaches some fixed value $D$.
  • The initial encoding gadget is constant sized, and so has some constant probability of failure $\epsilon_{\mathrm{init}}$. There exists a threshold physical noise rate such that the following growth and EC gadgets operating on a distance-$d$ surface code have a probability of failure at most $e^{-\alpha' d}$ for some $\alpha' > 0$.
  • The final output state is the correctable to $|\bar\psi\rangle$ when none of the gadgets (constant sized encoding circuit, EC, and growth) have failed. This happens with probability at least $ 1-\epsilon$ where $$ \epsilon \le \epsilon_{\mathrm{init}} + \sum_{i=3}^D \left(e^{-\alpha'}\right)^i \le \epsilon_{\mathrm{init}} + \sum_{i=3}^\infty \left(e^{-\alpha'}\right)^i \le \mathrm{const.}$$ Which can be made an arbitrarily small constant by appropriate choice of gate error rate (affecting $\alpha'$ and $\epsilon_{\mathrm{init}}$)

** Using $\alpha$ to replace the usual $\lceil\frac{d}{2}\rceil$ with $d$. It is not important.

*** Noise rate is used as short-hand for the parameters of a local stochastic error model.

  • $\begingroup$ I felt this was relevant to the question despite it not strictly speaking answering the question. $\endgroup$ Commented Jun 4 at 21:49
  • $\begingroup$ You don't need any extra CNOT gates to grow a surface code. You grow the code by adding data qubits, prepared into the basis of the closest boundary of the smaller code (|0> near the Z boundaries, |+> near the X boundaries), and then just start running cycles on the larger code. This lets you grow from any distance to any other distance in 1 round, though it will take d_big - d_small rounds before there are no more spacetimelike fault chains shorter than d_big. You can also do the reverse and shrink by measuring data qubits instead of preparing data qubits. $\endgroup$ Commented Jul 6 at 20:56
  • $\begingroup$ That's true. I chose to grow with CNOT, because it makes the proof cleaner. It doesn't require any further properties (e.g. lattice surgery) beyond the standard properties of an error correction gadget. Growing all at once is definitely more optimal, but the combinatorics of the number of fault chains is a bit messy $\endgroup$ Commented Jul 7 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.