Quantum low-density parity-check code

“A CSS code defined by a couple of binary code (CX,CZ) is said to be a quantum LDPC code if CX and CZ are LDPC codes, i.e. if CX and CZ have parity-check matrices HX and HZ that are both sparse.”

Stabilizer code

def ldpc (C : quantum_code) [stabilizer_code C] :=
∃ l, ∀ n,
each check acts on ≤ l qubits
∧
each qubit participates ≤ l checks

  • Instances:

  • How do k and d scale with n in the Surface code?

    • d² = n. Logical error happens when error chain from boundary to boundary.

      • code distance grows as √n

    • classical codes scale linearly.

    • “Surface code family does not compare favourably”

  • There exist quantum codes which match the properties of classical codes.

    • But the parity checks we have to measured involve a growing number of physical qubits per logical qubit.”

  • “Classical LDPC codes solve similar issues in classical coding theory.”

  • “Gottesman2013: Quantum LDPC codes with a constant encoding rate can reduce the overhead of fault-tolerant quantum computation to be constant.”

    • “In contrast, some other quantum fault tolerance schemes with a lower logical error rate require a larger code.”

  • Can Quantum LDPC codes approach Capacity for classical communication like classical LDPC codes?”

/-
But taking two random parity check matrices to define HX and HZ of a quantum code does not work.
-/

But they only encode a low constant number of qubits and have d ∝ best.

Want LDPC codes with larger distance.

Some Quantum LDPC codes significantly outperform surface codes in terms asymptotic parameters.

For a Quantum code from two binary linear codes this means that the Hamming weight of each row and column of HX and HZ is bounded by a constant.”

/-- code distance and message length scale linearly -/
def good := k ∈ Θ(n) and d ∈ Θ(n).

/-- code distance scales as √n -/
lemma not_good_surface_code : 
¬ good surface_code := sorry

/-- There exist good quantum codes that are not LDPC -/
lemma exist_good_non_ldpc_code :
∃ (Q : quantum_code), good Q ∧ ¬ LDPC Q := sorry

“Quantum codes can be constructed using tools from homological algebra.”

  • A classical code corresponds to a Chain complex of length two via its parity check matrix.

  • A Quantum code from two binary linear codes is a Chain complex of length three.

    • A single Chain complex can yield many CSS codes if you take any two consecutive boundary operators.”

  • “The logical Z-operators correspond to the homology group H₁(C) = ker(∂₁)/im(∂₂).

  • And the logical X-operators correspond to the cohomology group H₁(C) = ker(∂tr)/ im(∂tr).

  • The number of logical qubits is k = dim H₁(C) = dim H₁(C).

  • The Z-distance dZ and X-distance dX is the minimum Hamming weight of all non-trivial homology and cohomology classes, respectively.

  • The distance d is the minimum of dX and dZ.

  • Hamiltonians with all complex low-energy states

“The study of quantum LDPC codes arguably started with the Surface code. It encodes a constant number of logical qubits into n physical qubits and achieves a distance of √n.

Taking the tensor product of chain complexes that represent the two classical codes yields quantum codes of contant rate and minimum distance Θ(√n).

Combinations of chain complex products together with graph lifts.

non-abelian lifts of products of (classical) Tanner codes: Asymptotically good QLDPC code”

References

“in the asymptotic limit of large circuits, the ratio of physical qubits to logical qubits can be a constant. The construction makes use of quantum low-density parity check codes, and the asymptotic overhead of the protocol is equal to that of the family of quantum error-correcting codes underlying the fault-tolerant protocol.”