1 of 35

Single-Shot Decoding

of Linear Rate LDPC Quantum Codes

with High Thresholds

Nikolas P. Breuckmann & Vivien Londe

2 of 35

linear rate

LDPC

1x

Single-shot

[Fawzi, Pryadko]

2014

3 of 35

Background

Our contribution:

    • Construction of examples
    • Analyze properties
    • Performance simulation via Monte Carlo

Motivation: disprove conjectured bound

[Delfosse 2013: holds for 2D]

​

​

​

by showing that 4D hyperbolic codes have parameters

4 of 35

Homological Codes

Brief review (without homology)

5 of 35

Homological codes

Recipe

​

  1. Take tessellated D-manifold

​

  • Pick dimension 0 < i < D

​

  • Identify:
    1. i-cells with qubits
    2. i-1-cells with X-checks
    3. i+1-cells with Z-checks

6 of 35

Homological codes: 2D Toric Code

Recipe

​

  • Take tessellated D-manifold

​

  • Pick dimension 0 < i < D

​

  • Identify:
    • i-cells with qubits
    • i-1-cells with X-checks
    • i+1-cells with Z-checks

7 of 35

Homological codes: 3D Toric Code

In 3D we can choose i = 1: put qubits on edges

8 of 35

Homological codes: 3D Toric Code

In 3D we can choose i = 2: put qubits on faces

9 of 35

Homological codes: 4D

10 of 35

Homological codes: 4D

  • The lower-dimension-checks can see boundaries
  • Z-Logical operators have to be closed surfaces to commute with all X-stabilizers (2-cycles)
  • Should not be the boundary of a 3-volume

(otherwise trivial)

​

11 of 35

Hyperbolic codes

How does negative curvature affect the properties of the quantum code?

12 of 35

Hyperbolic codes

Use connection between code properties and geometry

13 of 35

Hyperbolic codes: encoding rate k/n

Chern-Gauss-Bonnet Theorem:

In 2D: Gaussian curvature

2D

4D

14 of 35

Hyperbolic codes: distance d

Anderson’s Theorem: Volume of non-contractible i-cycle γ is lower bounded by volume of i-dimensional ball with radius being the injectivity radius R.

Guth-Lubotzky (2014):

Definition: Injectivity Radius R -- largest radius of a ball that can be embedded without self-intersections

In hyperbolic space:

15 of 35

Construction

How do we obtain examples?

What are their properties?

16 of 35

Tessellation of

  • 5 regular tessellations
  • Focus on {5,3,3,5} tessellation
  • Self-dual tessellation by 120-cells
  • 4D polytope with 120 dodecahedra at boundary

17 of 35

Symmetries of Regular Tessellations

Described by Coxeter groups

given by angles in which reflections intersect

generated by reflections

18 of 35

Construction via Finitely Presented Groups

  • Group elements serve as coordinates (label simplices)
  • Consider cosets with respect to a subgroup

19 of 35

Construction via Finitely Presented Groups

  • Find suitable set of translations based on rewriting systems
    • “Brute-force” methods like Todd-Coxeter algorithm
    • Randomized search

​

  • Identify points which differ by these translations

20 of 35

Construction via Finitely Presented Groups

For example, the translation

​

ababacbdedcbabacedcbaedced

​

gives [[144,72]] code

This method is not scalable

21 of 35

Construction via Linear Representation: Dream

22 of 35

Construction via Linear Representation

[Londe & Leverrier (2019), Abresch & Schroeder (1992)]

Can embed D-dim. hyperbolic space into D+1-dim. Minkowski space

  • Symmetry group is
  • Symmetry group of tessellation is (isomorphic to) subgroup

23 of 35

Construction via Linear Representation

Instead of factoring out number N we factor out maximal ideal I

Work with polynomials

Ideals come in two flavours

Factoring out ideal gives finite symmetry group

24 of 35

Small 4D Hyperbolic Codes

[Abresch & Schroeder (1992)]

25 of 35

Logical operators

  • 2D surfaces of some genus embedded in 4D

​

  • Lubotzky (1996):

There exist an embedded 2D hyperbolic surface which has area growing as p^6.

​

Since n ~ p^20 we get that

​

​

This bound does not necessarily hold in general!

26 of 35

Decoding

27 of 35

Errors & Syndromes

28 of 35

Cellular Automaton Decoder

  • Do majority vote around face
  • Can only shrink syndrome & does not increase it

[Dennis et. al. (2001), Pastawski et. al. (2013), Breuckmann et. al. (2016), Kubicka et.al. (2019)]

  • Appealing:
    • low complexity
    • easy to implement

Z

Z

Z

29 of 35

Cellular Automaton Decoder

Linear plot

Log-log plot

Independent X-/Z-flip error model (no syndrome noise)

30 of 35

Cellular Automaton Decoder

CA decoder can not make use of full distance

CA decoder in 4D hyperbolic code can get stuck locally

Need a decoder which can “see farther”

[Breuckmann, Duivenvoorden, Michels & Terhal (2016)]

31 of 35

Belief Propagation

  • Decoder for classical LDPC codes

[Talks by Grouès & Panteleev]

  • Very low computational complexity
  • Operates iteratively via message passing
  • We use the vanilla version of BP [no OSD, no SSF]
  • Expect to work well because
    • girth is 6
    • is an expander
    • qubit degree is 5

32 of 35

Belief Propagation

  1. Add random errors
  2. Compute syndrome
  3. Add syndrome noise (p = q)
  4. Run BP decoder (GOTO 1)
  5. After T steps: can we decode back to code word with perfect syndrome?

T = 1

T = 5

33 of 35

Belief Propagation

Results for n = 19,584 with varying number of steps

34 of 35

Conclusion

Future work

  • Proof that error suppression is exponential
  • Increase performance by switching decoder
  • Can stabilizer weight be decreased?
  • Are there overhead savings compared to other schemes?
  • Gave construction of 4D hyperbolic codes
  • {5,3,3,5} family has examples with ~20% encoding rate
  • BP decoding with noisy syndrome (p=q):
    • MC results consistent with threshold at ~4%

35 of 35

Vivien Londe

ArXiv:1908:?????

​

​

Thank you for your attention!

​

​

Questions?