Thread by @fgrosshans

Now seated for a seminar by Antoine Grospellier, from @inria_paris, on Constant overhead quantum fault-tolerance with quantum expander codes.

Associated paper: arXiv:1808.03821 arxiv.org/abs/1808.03821
#LTQI

@inria_paris Antoine Gropellier recalls the principle of quantum fault tolerance with concateneated Steane codes. Without correction, with error probability p, a circuit C, |C| gates and m qubits, Pr(wrong output)≤p|C|,
With code, 7m qubits, ≤c₀|C| gates, Pr(wrong)≤cp²|C|
#LTQI

@inria_paris Antoine Grospellier: with n iteration, 7ⁿm qubits, ≤c₀ⁿ|C| gates, Pr(Wrong)≤|C| (cp)^2ⁿ /c
This doubly exponenetial scaling of the error translates into a polylog(ε) scaling of the space overhead with the errors.
Ou main interest here is thii overhead
#LTQI

@inria_paris Antoine Gorspellier: To reduce the space overhead, we use the distillation of encoded magic states.
With concatenated codes, this gives a polylog overhead. Using codes with constant rate, Gottesmann showed a constant overhead is possible (at least asymptotically)
#LTQI

@inria_paris Antoine Grospellier: Gottesmann used gates teleportation and still used concatenated codes for state preparation. He also relied on quite strong hypotheses on the codes. This work showed such codes indeed exist.
#LTQI

Antoine Grospellier is interested in CSS codes. This family of stabilizer codes allow to construct quantum error correcting codes from two classical error correcting codes. Here, we use two LDPC codes, since we need this property.
#LTQI

Antoine Grospellier: The (classical) decoding algorithm gives the correction to apply on the qubits from the syndom σ. We want a constant time for constant error rate, distance Ω(n^cst), and decoding failure O(exp(-α√n)).
#LTQI

Antoine Grospellier: uses the Tillich-Zemor hypergraph product codes, with classical expander codes to obtain quantum expander codes.
Classical expander codes have a minimal distance, and simple decoding algorithm (bit-flip algorithm)
#LTQI

Antoine Grospellier: For the quantum expander code, the decoding needs to flip several bits simultaneously.

Antoine Grospellier has shown that expander codes allos:
* fault-tolerance with constatn space overhead
* single-shot error correction
* parallel decoding in constant depth (arXiv:soon )
#LTQI

Atnoine Grospellier also made numerical simulation of these codes in
arxiv:1810.03681 arxiv.org/abs/1810.03681 ,
to check they behave well in finite settings
#LTQI