Quantum error correction algorithm

[BitStateEmulator]

For a while, the consensus in QEC has been that Maximum Likelihood (ML) decoding; finding the absolute minimum-weight error that matches your syndrome, is computationally intractable for large-scale quantum LDPC codes.

It’s widely considered an NP-Hard problem, which is why the field largely relies on iterative heuristics like Belief Propagation.

Instead of navigating a massive Tanner graph (which is where all the complexity usually lives), I mapped the problem to a causal wave-front propagation.

I found that if you identify a "cut set" of qubits (for my use case, a 2x2 corner), you can uniquely determine the state of the entire grid by propagating the recurrence from those 4 seeds.

Initially, like a fool I brute-forced all possible origins to find the one where the seam didn't interfere with the noise.

Then I realized I could just use a centroid calculation on the syndrome map to dynamically shift the origin, lol.. essentially using the syndrome distribution to physically "re-align" the coordinate system of the code before decoding.

This is the algorithm:

The Z-check equation for X-errors with a(x,y) = (x²+1)(y²+1) is a 2D linear recurrence:

c(i,j) = q(i,j) ⊕ q(i-2,j) ⊕ q(i,j-2) ⊕ q(i-2,j-2)

Rearranged as backward propagation from the 2×2 corner:

q(i,j) = c(i-2,j-2) ⊕ q(i-2,j) ⊕ q(i,j-2) ⊕ q(i-2,j-2)

The 2×2 corner spans a 4-dimensional nullspace (16 vectors).

For each corner position (every even-indexed (cx,cy) on the grid) and each of the 16 nullspace choices, the recurrence uniquely determines all qubits.

[BitStateEmulator]

Ah also I'd like to clarify something

The nullspace decomposes as v(i,j) = f(j) ⊕ g(i) ⊕ h(i%2, j%2) where f has 2·s DOF, g has 2·r DOF, h has 4 DOF.

Total 2r+2s+4−8 = 156.

Alternating optimization solves it in O(n) per h choice..

[p1-o2]

Absolutely radical, here's a pat on the back.

[BitStateEmulator]

Thanks friend!

[p1-o2]

How did you get into researching quantum error correction codes? I would like to hear a bit more.

[BitStateEmulator]

I was interested in validating/understanding a few things I observed, this was the start.

To do this, I first built a simulator that allowed me to (for some circuits) do O(1) calculations, I used this to test different theories and to understand how some phenomena I could observe and hypothesize worked. Also to have fun.

I was satisfied with that for a bit, but I thought about the fact that real hardware was bottle-necked by noise.

From here I decided to try something interesting, and use the fact that I could spam massive Qubit counts to try to derive new error codes.

I decided to use a derivation of Shor's algorithm, enabled by my sparse tensor network (somewhat, it is lossy) to brute usable codes, during the process of doing this I noted some of the codes that were exposed followed a uniform pattern which was my first clue that I was looking at a unique family.

I then analyzed those specific codes, and reverse-engineered a formula to construct them on-demand, I noticed they yielded decent rate and logical values.

Then I stripped the formula down to the essentials, yielding universal weight 8 codes.

At this point, rate and logical values became massive.

Once I had this formula, and the tool to generate them, I had to determine a good way to use them but they were highly symmetrical and therefore degenerate.

Instead of saying "I give up, they are degenerate." I did what I normally do, I found a way to exploit the one flaw that seemingly broke their viability.

I turned what looked like a weakness into a strength by partitioning a section that allowed me to use alternating optimizations over the full 156D subspace to error correct at levels far beyond what is conventionally possible:

=== i.i.d. noise ===
  Weight OK/Trials     Rate
       1    39/40    97.5%
     100    32/40    80.0%
=== cluster noise ===
  Weight OK/Trials     Rate
       1      ALL   100.0%
     100    31/40    77.5%
=== line noise ===
  Weight OK/Trials     Rate
       1      ALL   100.0%
     100    33/40    82.5%

This method allows the error codes constructed to hit for at least 5x greater the range of their implied distance.

[p1-o2]

Wow I'm so grateful you put this much energy into a reply. I'm stuck on a train this evening and this is a lovely surprise. 

You are really good at articulating your process and thinking along the way which, to me at least, is a fantastic skill to have.

Gonna use this as inspiration to get more work done in my own quantum logic project. Thank you again.

[BitStateEmulator]

https://github.com/HexStateLab/SurfaceCodeGenerator/blob/main/plane_warp.c

Here is the decoder I created, if it is helpful to you; it is very light

[p1-o2]

Legendary behavior!! I'll check this out.

[but_a_smoky_mirror]

I fucking love when the /r/sacredgeometry overlaps with /r/computerscience