GZGilles Zémor

Gilles Zémor

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Gilles Zémor has a total of 130 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    The injective norm of CSS quantum error-correcting codes

    by Stephane Dartois, Gilles Zémor

    In this paper, we compute the injective norm - a.k.a. geometric entanglement—of standard basis states of CSS quantum error-correcting codes. The injective norm of a quantum state is a measure of genuine multipartite entanglement. Computing this measure is generically NP-hard. However, it has been exactly computed in condensed matter theory—notably in the context of topological phases—for the Kitaev code and its extensions, in works by Orús and collaborators. We extend these results to all CSS codes and thereby obtain the injective norm for a nontrivial, infinite family of quantum states. In doing so, we uncover an interesting connection to matroid theory and Edmonds” intersection theorem.

  • Open Access

    Efficient Decoding up to a Constant Fraction of the Code Length for Asymptotically Good Quantum Codes

    by Anthony Leverrier, Gilles Zémor

    We introduce and analyse an efficient decoder for quantum Tanner codes that can correct adversarial errors of linear weight. Previous decoders for quantum low-density parity-check codes could only handle adversarial errors of weight \(O(\sqrt{n\log n})\) . We also work on the link between quantum Tanner codes and the lifted product codes of Panteleev and Kalachev and show that our decoder can be adapted to the latter. The decoding algorithm alternates between sequential and parallel procedures and converges in linear time.


  • Open Access

    Kneser's theorem for codes and $\ell$-divisible set families

    by Chenying Lin, Gilles Zémor

    A $k$-wise $\ell$-divisible set family is a collection $\mathcal{F}$ of subsets of ${ \{1,\ldots,n \} }$ such that any intersection of $k$ sets in $\mathcal{F}$ has cardinality divisible by $\ell$. If $k=\ell=2$, it is well-known that $|\mathcal{F}|\leq 2^{\lfloor n/2 \rfloor}$. We generalise this by proving that $|\mathcal{F}|\leq 2^{\lfloor n/p\rfloor}$ if $k=\ell=p$, for any prime number $p$. For arbitrary values of $\ell$, we prove that $4\ell^2$-wise $\ell$-divisible set families $\mathcal{F}$ satisfy $|\mathcal{F}|\leq 2^{\lfloor n/\ell\rfloor}$ and that the only families achieving the upper bound are atomic, meaning that they consist of all the unions of disjoint subsets of size $\ell$. This improves upon a recent result by Gishboliner, Sudakov and Timon, that arrived at the same conclusion for $k$-wise $\ell$-divisible families, with values of $k$ that behave exponentially in $\ell$. Our techniques rely heavily upon a coding-theory analogue of Kneser's Theorem from additive combinatorics.

  • Efficient error-correcting codes for the HQC post-quantum cryptosystem

    by Carlos Aguilar-Melchor, Nicolas Aragon, Jean-Christophe Deneuville, Philippe Gaborit, Jérôme Lacan, Gilles Zémor


  • Analysis of the Error-Correcting Radius of a Renormalization Decoder for Kitaev’s Toric Code

    by Wouter Rozendaal, Gilles Zémor

    Kitaev’s toric code is arguably the most studied quantum code and is expected to be implemented in future generations of quantum computers. The renormalisation decoders introduced by Duclos-Cianci and Poulin exhibit one of the best trade-offs between accuracy and efficiency, with a time complexity in O ( n log 2 n ). One question that was left open is how they handle worst-case or adversarial errors, i.e. what is the order of magnitude of the smallest weight of an error pattern that will be wrongly decoded. We initiate such a study involving a simple hard-decision and deterministic version of a renormalisation decoder. We exhibit an uncorrectable error pattern whose weight scales like d 1/2 and prove that the decoder corrects all error patterns of weight less than 5/6 d log2(6/5) , where d is the minimum distance of the toric code.


  • Top Cited Papers

    Decoding Quantum Tanner Codes

    by Anthony Leverrier, Gilles Zémor

    We introduce sequential and parallel decoders for quantum Tanner codes. When the Tanner code construction is applied to a sufficiently expanding square complex with robust local codes, we obtain a family of asymptotically good quantum low-density parity-check codes. In this case, our decoders provably correct arbitrary errors of weight linear in the code length, respectively in linear or logarithmic time. The same decoders are easily adapted to the expander lifted product codes of Panteleev and Kalachev. Along the way, we exploit recently established bounds on the robustness of random tensor codes to give a tighter bound on the minimum distance of quantum Tanner codes.


  • Open Access

    Decoding quantum Tanner codes

    by Anthony Leverrier, Gilles Zémor

    We introduce sequential and parallel decoders for quantum Tanner codes. When the Tanner code construction is applied to a sufficiently expanding square complex with robust local codes, we obtain a family of asymptotically good quantum low-density parity-check codes. In this case, our decoders provably correct arbitrary errors of weight linear in the code length, respectively in linear or logarithmic time. The same decoders are easily adapted to the expander lifted product codes of Panteleev and Kalachev. Along the way, we exploit recently established bounds on the robustness of random tensor codes to give a tighter bound on the minimum distance of quantum Tanner codes.


  • Open Access

    Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes

    by Anthony Leverrier, Gilles Zémor

    We introduce and analyse an efficient decoder for the quantum Tanner codes of that can correct adversarial errors of linear weight. Previous decoders for quantum low-density parity-check codes could only handle adversarial errors of weight $O(\sqrt{n \log n})$. We also work on the link between quantum Tanner codes and the Lifted Product codes of Panteleev and Kalachev, and show that our decoder can be adapted to the latter. The decoding algorithm alternates between sequential and parallel procedures and converges in linear time.

  • Open Access

    Quantum Tanner codes

    by Anthony Leverrier, Gilles Zémor

    Tanner codes are long error correcting codes obtained from short codes and a graph, with bits on the edges and parity-check constraints from the short codes enforced at the vertices of the graph. Combining good short codes together with a spectral expander graph yields the celebrated expander codes of Sipser and Spielman, which are asymptotically good classical LDPC codes. In this work we apply this prescription to the left-right Cayley complex that lies at the heart of the recent construction of a $c^3$ locally testable code by Dinur et al. Specifically, we view this complex as two graphs that share the same set of edges. By defining a Tanner code on each of those graphs we obtain two classical codes that together define a quantum code. This construction can be seen as a simplified variant of the Panteleev and Kalachev asymptotically good quantum LDPC code, with improved estimates for its minimum distance. This quantum code is closely related to the Dinur et al. code in more than one sense: indeed, we prove a theorem that simultaneously gives a linearly growing minimum distance for the quantum code and recovers the local testability of the Dinur et al. code.