6
$\begingroup$

I am trying to understand why we need to keep in memory $d$ clock cycles in order to correct efficiently for the surface code where the syndrome qubits are also faulty ($d$ is the code distance).

[edit]: It seems that there is no real "proof" of that. This is something one has to check numerically and it is not obvious from a theoretical perspective (look at the comments below the answer from Craig Gidney)

What I understand: case with perfect syndromes

I summarize my understanding in case it might help potential future readers and in order to help you see where my struggles are exactly.

In the case of perfect syndrome measurement, for a code distance being $d$, we can resist to chain of errors which total weight verifies $|\sum_i E_i| \leq (d-1)/2$.

Here $E_i$ is a $1$-chain inducing errors. And we might have different independent $1$-chains occuring resulting on the total error $E=\sum_i E_i$ on which the condition of maximum weight being $(d-1)/2$ is expressed.

The reason why we can resist to such chain of errors comes from the fact that a logical operator is connecting two rough edges of the surface. Hence its weight is at least $d$. Then, if I assume that correction will apply a minimum weight recovery, and that it "fixes" the syndrome, we have:

  1. $\partial R = \partial E$ (we "fix" the syndrome)
  2. The recovery necessarily verifies $|R| \leq |E| \leq (d-1)/2$ (we apply a minimum weight recovery)

Then:

  1. $\partial R = \partial E \rightarrow$ The syndromes are now "fixed".
  2. $|R+E| \leq d-1$: the net operation cannot be a logical operation.

1+2 imply that the net effect is then a product of stabilizer: the data is preserved.

Where I struggle: we assume that the syndrome can also be faulty

When the syndrome can be faulty we have to include the time dimension in the reasoning (note: in what follow I assume a bit-flip code so that my surface is $1$-dimensional). The time dimension is vertical while the surface is represented horizontally. Data qubits errors are then horizontal line and syndrome qubit error vertical lines and they will always be written (as before) with the letter $E$. They will be in red colors. Places where a non trivial syndrome is detected (i.e we we are no longer in the $+1$ eigenstate of the associated syndrome) are in green colors. The associated chain will be written with the letter $S$. The boundary of those syndromes are in blue (written with the letter $\partial S$). Below is an image to clarify all this (with examples of errors occuring):

enter image description here

My question: how can we show that we necessarily have to store a history of $d$ cycle in order to be able to resist again error chains which total weight is $|\sum_i E_i| \leq (d-1)/2$? I would ideally be interested by a good pedagogic reference on this.

My struggles:

  1. The syndrome chain $S$ does not always verify $\partial S = \partial E$ in the case we take a finite slice of data (see an example in the image below). Because of that, condition that the recovery $R$ I apply should verify $\partial R = \partial S$ is not always correct. This fact confuses me in how we should reason. This issue will typically occur when the non trivial syndrome is reaching the time edges (at $t_0$ or at $t_0-5dt$).
  2. Should we keep in memory $d$ timesteps of error correction and then do a big correction or should we actually consider than when a non trivial syndrome is detected, we have to look at it for $d$ timesteps in order to differentiate between space and time errors? I guess it is a hint to solve my previous struggle but I am not sure...

An example where $\partial S \neq \partial E$ (on the left), and $\partial S = \partial E$ (on the right).

enter image description here

In term of references, what I looked at was this paper. The issue that I have with it latter is that it considers an ideal case with an infinite recording in time. I also looked for instance at ref but it is explained in a very "condensed matter" style and I basically don't get the point. In short: Overall, I looked at various refs on the question but I haven't found a good explanation if you leave the simple case where your time record is "infinite".

[edit]:

As suggested in Craig Gidney answer below, storing data in time might only be necessary if we perform non-trivial logical operations on the lattice. It is also said that errors in time are not dangerous for a quantum memory as they are in the up direction (while logical error are in the left-right direction). However, from my perspective, a time error could indirectly induce a space (i.e left to right) error, and hence be indirectly dangerous. Below is an attempt to show such example. I assume:

  1. For each clock cycle I have less (or equal) than $(d-1)/2$ errors which include measurement and data qubits.
  2. I perform correction "ASAP" (i.e I don't wait for $d$ clock cycle to do something, I perform corrections live).
  3. I apply a correction with minimum weight. Different corrections could be possible (and I consider in those examples the ones that would cause me troubles for the sake of illustration).

enter image description here

Comments on this image:

  • At $t_0$, the first and last (i.e fourth) syndrome have an error.
  • Because of that, at $t_0+dt$ I perform a (wrong) correction on first and last data qubits. It will induce an error on my lattice. On this new timestep, I can also have no more than $2$ errors. They happen to be on the first syndrome and second data qubit.
  • At $t_0+2dt$, the (correct) third and last syndromes are non-trivial. A possible minimum weight correction is to flip the third and fourth data qubits. It induces a logical error.
  • At $t_0+3dt$ the logical error stays.

Of course this example is not necessarily contradictory with the fact we can correct with $O(1)$ in the case of a quantum memory, but it illustrates my confusion. Having less (or equal) than $(d-1)/2$ errors, "live" correction induces a logical error. For this reason the code distance cannot anymore be $d$.

Would it be possible to have an intuitive algorithm that shows how we can correct in the quantum memory case when the syndrome happen to be faulty?

$\endgroup$

1 Answer 1

2
$\begingroup$

I don't know a hard rule for how many rounds you need to keep in memory. For example, suppose you were using phenomenological noise with an extremely low data error rate of 1 in a billion but an extremely high measurement error rate of 49.99%. One way to deal with this is to fold together a million rounds into one super-round and do majority voting for the super-round measurement results. Each super-round has an effective measurement error rate of 2.5% and a data error rate of 0.1%. That's pretty reasonable so you'd use 'standard techniques' on the super-rounds, keep 50 or 100 of them in memory or whatever. But now your history is effectively going to span tens of super-rounds, which is tens of millions of the original rounds, to achieve a code distance of (say) 5!

That being said, to me the key problem that jumps out when you have $r < d$ rounds of memory is that a chain of $r$ measurement errors can create a pair of detection events separated by enough time that only one is in memory at a time. And if there's only one in memory, you are forced to match it to a spatial boundary. So suppose these measurement errors are happening next to the center of the patch, and then one additional data error at the future side pushes the future detection event across the center. On the past side you will match to one boundary and on the future side you will match to the other, completing an error chain across the patch (which is a logical error).

$\endgroup$
5
  • $\begingroup$ Hey again. I am trying to come up with an example associated with your last paragraph but I am struggling to know how we do the correction in practice. For this reason, I have a few questions. I call $d_t$ the number of physical clock cycles I store in memory. (i): Is the principle to apply "once for all" a single recovery every $d_t$ or is the algorithm working differently (like it applies a recovery each time but is using info from the last $d_t$ steps). (ii): A way to find a sufficient condition so that we never have logical error is to ask that the weight of the error $|E| \leq (d-1)/2$ $\endgroup$ Feb 8 at 17:29
  • $\begingroup$ where $E$ is the sum of all data qubit 1-chain and measurement qubit 1-chain. Is it the case on which your reasoning is based? If so, it implies that I should only look at chains composed of $2$ errors for $d=5$ for instance. In this case, I would be surprised if we need $d_t=5$ I would "intuitively" expect something like $d_t=2$ or $3$ would be largely sufficient. If you are considering a different worst-case scenario, could you explain me which one (and why). $\endgroup$ Feb 8 at 17:31
  • 1
    $\begingroup$ @StarBucK I would recommend just doing simulations where you use different sizes of $d_t$ and see what it does to the logical error rate. The concept of code distance gets a lot hazier once you transition from "create an undetectable error" to "create an error that's just confusing enough to fool the decoder". $\endgroup$ Feb 8 at 19:04
  • $\begingroup$ Ok thank you! When reading paper it is often said that you should consider $d_t=d$ as if there were some "logical analytical" reason for that but it is probably not the case then! $\endgroup$ Feb 8 at 19:21
  • $\begingroup$ FYI: I took some time to find papers "showing" that $d_t \geq d$ is required and I also exchanged with people more familiar than me in surface code and it seems that indeed there is no "fundamental proof" that $d_t \geq d$ is required. This is something you usually see with simulations. (It confirms your intuition). $\endgroup$ Feb 18 at 16:08

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.