18
$\begingroup$

Which quantum error correction code currently holds the record in terms of the highest threshold for fault-tolerance? I know that the surface code is pretty good ($\approx10^{-2}$?), but finding exact numbers is difficult. I also read about some generalizations of the surface code to 3D clusters (topological quantum error correction). I guess the main motivation for this research was to increase the threshold for calculations of arbitrary length.

My question is: Which quantum error correction code has the highest threshold (as proven at the time of writing this)?

In order to judge this value it would be nice to know what threshold is theoretically achievable. So if you know of (non-trivial) upper bounds on thresholds for arbitrary quantum error correction codes that would be nice.

$\endgroup$
  • $\begingroup$ Only "noise" isn't a good tag. Maybe use something like "error-correction-codes". $\endgroup$ – Sanchayan Dutta Mar 13 '18 at 16:20
  • $\begingroup$ Are you looking for implementations or papers detailing possible ones? $\endgroup$ – Riker Mar 13 '18 at 16:43
  • $\begingroup$ I'm interested in theoretical proofs / calculations of the threshold. Hints to research papers are greatly appreciated! $\endgroup$ – M. Stern Mar 13 '18 at 18:55
  • $\begingroup$ You should probably add caveats on what architecture. For example, the surface code is still probably most efficient for a 2D lattice of superconducting qubits. $\endgroup$ – Alan Ho Mar 19 '18 at 17:40
  • $\begingroup$ @Alan Long-range interactions may not be easy to implement in some architectures, but the threshold is independent of the architecture. I think we can ignore experimental difficulties here. $\endgroup$ – M. Stern Mar 19 '18 at 17:55
6
$\begingroup$

As far as I’m aware, the surface code is still regarded as the best. With an assumption of all elements failing with equal probability (and doing so in a certain way) it has a threshold of around 1%.

Note that the paper you linked to doesn’t have a 3D surface code. It is the decoding problem that is 3D, due to tracking changes to the 2D lattice over time. As I think you suspected, this is the required procedure when try to keep the stored information coherent for as long as possible. Check out this paper for an earlier reference in some of these things.

Exact threshold numbers mean you need a specific error model, as you know. And for that you need a decoder, which ideally adapts to the specifics of the error model while remaining fast enough to keep up. Your definition of what is fast enough for the task at hand will have a big effect on what the threshold is.

To get upper bounds for a specific code and specific noise model, we can sometimes map the model to one of statistical mechanics. The threshold then corresponds to the point of a phase transition. See this paper for an example of how to do this, and the references therein for others.

Other than the threshold, another important factor is how easy it is to do quantum computation on the stored information. The surface code is quite bad at this, which is a major reason that people still consider other codes, despite the great advantages of the surface codes.

The surface code can only do the X, Z and H gates very simply, but they aren’t enough. The Color code can also manage the S gate without too much trouble, but that still just restricts us to the Clifford gates. Expensive techniques like magic state distillation will still be needed for both cases to get additional operations, as required for universality.

Some codes don’t have this restriction. They can let you do a full universal gate set in a straightforward and fault-tolerant way. Unfortunately, they pay for this by being much less realistic to build. These slides might point you in the right directions for more resources on this matter.

It’s also worth noting that even within the family of surface codes there are variations to explore. The stabilizers can be changed to an alternating pattern, or a YYYY stabilizer can used, to better deal with certain noise types. More drastically, we could even make quite big changes to the nature of the stabilizers. There are also the boundary conditions, which are what distinguishes a planar code from a toric code, etc. These and other details give us lots to optimize over.

$\endgroup$
3
$\begingroup$

I believe that the Centre for Engineered Quantum Systems, School of Physics, The University of Sydney and the Center for Theoretical Physics, Massachusetts Institute of Technology use of a tensor network decoder of Bravyi, Suchara and Vargo (BSV), to achieve the highest error correction threshold to date.

In their whitepaper from last December, "Ultrahigh Error Threshold for Surface Codes with Biased Noise", the use of a tensor network decoder resulted in pure $Z$ noise of $p_c=43.7\left(1\right)\%$, which is a fourfold increase over the previous optimal surface code threshold for pure $Z$ noise of $10.9\%$. The $10.9\%$ number comes from S. Bravyi, M. Suchara, and A. Vargo, “Efficient algorithms for maximum likelihood decoding in the surface code”.

$\endgroup$
  • $\begingroup$ Thanks a lot for your answer and for linking the paper, which I was not aware of. It's interesting to note that the threshold strongly depends on the noise model and that asymmetric noise can be much less catastrophic. I should make clear, however, that I am looking for the best code (with worst-case noise). $\endgroup$ – M. Stern Mar 19 '18 at 22:21
  • $\begingroup$ The quoted result, and other similar ones (such as my own) relate to error correction, not fault tolerance. $\endgroup$ – DaftWullie Apr 19 '18 at 19:34
1
$\begingroup$

In the dim and distant past (I.e. I don’t remember the details any more), I tried to calculate an upper bound on a fault tolerant threshold. I suspect the assumptions that I made to get there wouldn’t apply to every possible scenario, but I came up with an answer of 5.3% (non-paywall version).

The idea was roughly to make use of a well-known connection between error correction codes and distillation of multiple noisy Bell states into a single, less noisy Bell state. In essence, if you have multiple noisy Bell states, one strategy for making a single high quality Bell state is to teleport the codewords of an error correction code through them. It's a two-way relationship; if you come up with a better distillation strategy, that defines a better error correcting code and vice-versa. So, I wondered what would happen if you allowed a concatenated scheme of distillation of noisy Bell pairs, but allowed some errors to occur when applying the various operations. This would map directly to fault tolerance via concatenated error correcting codes. But the different perspective allowed me to estimate a threshold beyond which the noise accumulation would simply be too high, and thus the error correction scheme would fail.

Different works have made different assumptions. For example, this one restricts to specific gate sets, and derives an upper bound to the fault-tolerant threshold of 15% in a specific case (but then the question arises as to why you wouldn't pick the scheme with the highest upper bound, rather than the lowest!).

$\endgroup$
  • $\begingroup$ Looks interesting! Do you have a link to a version of this that's not behind a paywall? Also, would you be able to elaborate a bit on how you got to that result? Thanks $\endgroup$ – Mithrandir24601 Apr 19 '18 at 19:53
  • $\begingroup$ @DaftWullie You’ve given away your secret identity now! $\endgroup$ – James Wootton Apr 19 '18 at 20:43
  • $\begingroup$ @JamesWootton no particular attempt at secrecy! That’s only for superheroes and trolls. $\endgroup$ – DaftWullie Apr 20 '18 at 5:37
  • $\begingroup$ @Mithrandir24601 i’ll Try to recall and post further details when I can, but it’s likely to be a week $\endgroup$ – DaftWullie Apr 20 '18 at 5:38
  • $\begingroup$ @DaftWullie And I thought you were a superhero :-/ $\endgroup$ – Norbert Schuch May 4 '18 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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