Is there a proof in the literature of magic state injection for surface codes?

Question

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.

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.