A loophole in quantum error correction


Quantum computers hold the promise of exponential speed up of certain calculations. Building such a machine requires being able to control its quantum state with an extreme precision, a formidable challenge. Yet, the theory of quantum error correction, which culminated in the fault tolerant threshold theorems, showed that it is merely a technical challenge: provided one can make the individual building blocks (quantum bits) with enough precision, it is possible to systematically improve the precision through a clever correcting scheme. Fault tolerant theorems show that an arbitrary good precision can be obtained using a limited amount of hardware -- they form the cornerstone of the current belief that a general purpose quantum computer can be built.
Submitted 24 Feb 2017 to Quantum Physics [quant-ph]
Published 27 Feb 2017
Updated 24 Mar 2017
Author comments: I no longer believe that the conclusions are supported by the calculations done in this manuscript. The paper tried to determine what will limit the precision in practice. I incorrectly pointed to small 1 qubit (precision) errors happening everywhere in the circuits


Christopher Chamberland Feb 27 2017 04:26 UTC (2 points)

Could you be more specific by what you mean when you say "the ability to perform quantum measurements with infinite precision"? Several circuit level noise thresholds have been computed where measurement errors are taken into account. Even with measurement errors, thresholds as high as 10^-2 have been reported for depolarizing noise.

Edited Feb 27 2017 04:27 UTC by Christopher Chamberland

Ben Criger in reply to Christopher Chamberland Feb 27 2017 09:04 UTC (8 points)

It seems like the problem is that the measurement basis is unknown (the actual operator being measured isn't exactly Z, for example, but some other Hermitian operator close to Z). However, this seems like it can be re-expressed using an unknown operation that occurs immediately before measurement of the correct operator. It is indeed known that this kind of noise can be corrected using repeated measurement, a technique which doesn't appear in this paper.

In any event, when you perform a syndrome measurement, you get classical information out. If you bin this information into two categories, you either put the syndrome in the right category or you don't, leading to bit-flip errors on the syndrome, which are correctable.

James Wootton Feb 27 2017 13:10 UTC (3 points)

Do any fault-tolerance theorems claim to hold for small codes without repeated measurement, as is the case in these supposed counter examples?

The assumption that no-one ever thought about this noise before is the faulty one here.

Robin Blume-Kohout Feb 27 2017 13:30 UTC (10 points)

@Chris: as Ben says, the model for measurement errors is "You measure in a basis that's off by a small rotation".

@Ben: I don't think either of the techniques you mention will directly resolve the paper's concern/confusion. That concern is with the post-QEC state of the system. That state isn't invariant under re-expressing measurement noise as a small unitary followed by measurement in the right basis. And repeated measurement in the same (wrong) basis won't fix the putative problem either.

@James: You're right that this has been thought about before. However, the paper isn't complaining that asymptotic FT fails; it's complaining that the O(p^2) error scaling that *is* supposed to hold for distance-3 codes fails. It's true that repeated measurement would be necessary to achieve that scaling, but it's not sufficient to fix the putative problem.

The basic problem here is misinterpretation of the "success" condition for QEC. This paper assumes that the metric of success is the overlap between the post-QEC state $|\Psi\rangle$ and the predefined $|0_L\rangle$ logical state. But it's not. It's actually kinda hard to precisely define what "success" means in a completely rigorous way. The simplest way I know of is to consider the sequence: (1) logical prep in one of the 4 BB84 states; (2) $N$ rounds of QEC; (3) logical measurement (in whichever of X or Z commutes with the desired initial prep). Then, look at the probability of correctly deducing the initial state, and fit it to $(1-p)^N$.

If your syndrome measurements are slightly rotated as in this paper, you're actually performing good QEC in a slightly deformed code. Which means that $|0_L\rangle$ moves around, depending on the measurement error. FTQEC still works, as measured by the operational criterion I gave above, but the naive criterion "Overlap with the $|0_L\rangle$ that I intended to implement" doesn't reveal it.

Edited Feb 27 2017 13:30 UTC by Robin Blume-Kohout

James Wootton in reply to Robin Blume-Kohout Feb 28 2017 08:54 UTC (1 points)

I think I was mostly reacting to where he tries to sell the importance of the work.

>Fault tolerant theorems show that an arbitrary good precision can be obtained using a limited amount of hardware...we unveil the role of an implicit assumption made in these mathematical theorems: the ability to perform quantum measurements with infinite precision.

Robin Blume-Kohout in reply to James Wootton Feb 28 2017 09:55 UTC (3 points)

I totally agree -- that part is confusing. It's not clear whether "arbitrary good precision ... using a limited amount of hardware" is supposed to mean that arbitrarily low error rates can be achieved with codes of fixed size (clearly wrong) or just that the resources required to achieve arbitrarily low error rates scale well (polylog) with the error rate. I assumed the latter, but maybe the former was meant.

Either way, carefully deconstructing the language is probably not a good use of time. I think the paper is well-intentioned, but not correct; as you point out, this *has* been thought of. Another colleague pointed out to me (by email) that there's a much better and more elegant resolution than the one I suggested; the extended rectangle formalism provides a definition of "FTQEC succeeds" that incorporates this issue *and* others.

Ben Criger in reply to Robin Blume-Kohout Mar 02 2017 08:58 UTC (1 points)

Good point, I wish I knew more about ExRecs.

Anirudh Krishna in reply to Ben Criger Mar 02 2017 18:40 UTC (2 points)

Here's a link to a lecture from Dan Gottesman's course at PI about exRecs.

You can find all the lectures here:

Edited Mar 02 2017 18:41 UTC by Anirudh Krishna

Christopher Chamberland in reply to Ben Criger Mar 02 2017 18:48 UTC (1 points)

A good paper for learning about exRec's is this one https://arxiv.org/abs/quant-ph/0504218. Also, rigorous threshold lower bounds are obtained using an adversarial noise model approach.