[PhD] Efficient Fault-Tolerant Quantum Computation with Quantum LDPC Codes


The thesis will be hosted in the MOCQUA team under Emmanuel Jeandel and Christophe Vuillot’s supervision. There will be frequent meetings and interactions with other members of the team will be encouraged.


Quantum computers, if built, would be able to solve some problems that are as of today intractable in practice for classical computers, and also speed up significantly some others. These remarkable theoretical results kick-started a global effort, academic as well as industrial, to address the roadblocks still preventing the construction of a large scale universal quantum computer. One of the main roadblocks is the sensitivity of real physical quantum systems to uncontrolled perturbation from their environment as well as imperfect control of the system, ever present in any real physical machine. So-called threshold theorems proved that this issue can be tackled by the implementation of fault-tolerant quantum computation [1, 2, 3]. Different schemes for universal and fault-tolerant quantum computation combine in some ways some families of quantum error correcting codes with techniques to obtain a set of universal fault-tolerant gates acting on them [4]. These schemes detect and remove errors from the computation at the cost of an overhead in physical qubits used and length of the computation. The magnitude of these overheads with state of the art techniques remain today prohibitive and comes at odds with the possibility of building a quantum computer [5]. This subject proposes to address this issue by exploring new schemes with the potential to reduce these overheads both from an asymptotic point of view and a finite-size practical one.

Subject Details

Most schemes for fault-tolerant quantum computation such as concatenated codes as well as the leading candidate, surface code [6] with magic state distillation [7] all have a poly-logarithmic overhead in both time and space. The study of single-shot error correction and quantum error correcting codes admitting transversal gates yielded schemes with only a constant time overhead [8]. Yet, all the above techniques suffer from one drawback of the underlying quantum error correcting code families: namely their encoding rate is asymptotically vanishing. Hence they cannot achieve better than poly-logarithmic space overhead.

The field of quantum low-density parity-check (LDPC) codes has attracted a lot of interest in recent years since such codes can have constant encoding rates with growing minimum distance. Moreover their LDPC property makes them suitable for fault-tolerant implementations. The possibility for having to pay only a constant overhead in space using such codes was put forward in [9] and recently proved to be achievable using quantum expander codes [10]. However by encoding several logical qubits within the same block of code these codes render difficult to act independently on different logical qubits of the same block. Indeed the scheme in [9, 10] can only work by applying one gate at a time and therefore cannot work on parallel circuits which need to be first linearized. More recently it was proposed to use some 2D hyperbolic
codes with constant space overhead and efficient code deformation techniques which could have a poly-logarithmic time overhead (including for parallel circuits) [11]. Yet the question of being able to achieve a constant overhead in both time and space remains, to this day, open.

A first approach is to design code families with built-in capabilities for fault-tolerant gates, for instance generalizing ideas from quantum color codes [8]. A first step in this direction was taken by generalizing quantum color codes to quantum pin codes [12] which are block codes retaining some structure from quantum color codes responsible for their interesting computing properties. Finding good instances of quantum pin codes as well as a full scheme using them for fault-tolerant quantum computation is a promising direction.

A second approach is to apply general techniques to already known good families of code such as code deformation techniques [13]. First results along this direction were taken for hyperbolic codes and hypergraph-product codes [14, 11, 15]. Extending these techniques is also a promising direction.

Candidate Profile

Candidates should posses a creative as well as mathematically rigorous mindset, a master degree or equivalent in either theoretical physics, computer science or mathematics. Previous work or interest in the theory of quantum computing and/or error correction would be a strong asset.


[1] D. Aharonov and M. Ben-Or. Fault-tolerant Quantum Computation with Constant Error. In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC ’97, pages 176–188, New York, NY, USA, 1997. ACM. event-place: El Paso, Texas, USA.
[2] John Preskill. Reliable quantum computers. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454(1969):385–410, January 1998.
[3] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43(9):4452–4505, 2002.
[4] Earl T. Campbell, Barbara M. Terhal, and Christophe Vuillot. Roads towards fault-tolerant universal quantum computation. Nature, 549(7671):172–179, September 2017.
[5] Craig Gidney and Martin Ekerå. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. arXiv:1905.09749 [quant-ph], December 2019. arXiv: 1905.09749.
[6] A Yu Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303(1):2–30, 2003.
[7] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A, 71(2):022316, February 2005.
[8] Héctor Bombı́n. Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes. New Journal of Physics, 17(8):083002, 2015.
[9] D. Gottesman. Fault-Tolerant Quantum Computation with Constant Overhead. Quant. Information and Computation, 14:1338–1371, 2014.
[10] O. Fawzi, A. Grospellier, and A. Leverrier. Constant Overhead Quantum Fault-Tolerance with Quantum Expander Codes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 743–754, October 2018.
[11] Ali Lavasani, Guanyu Zhu, and Maissam Barkeshli. Universal logical gates with constant overhead: instantaneous Dehn twists for hyperbolic quantum codes. Quantum, 3:180, August 2019. Publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften.
[12] Christophe Vuillot and Nikolas P. Breuckmann. Quantum Pin Codes. arXiv:1906.11394 [quant-ph], June 2019. arXiv:1906.11394.
[13] Christophe Vuillot, Lingling Lao, Ben Criger, Carmen Garcı́a Almudéver, Koen Bertels, and Barbara M. Terhal. Code deformation and lattice surgery are gauge fixing. New Journal of Physics, 21(3):033028, March 2019.
[14] Nikolas P. Breuckmann, Christophe Vuillot, Earl Campbell, Anirudh Krishna, and Barbara M. Terhal. Hyperbolic and semi-hyperbolic surface codes for quantum storage. Quantum Science and Technology, 2(3):035007, 2017.
[15] Anirudh Krishna and David Poulin. Fault-Tolerant Gates on Hypergraph Product Codes. Physical Review X, 11(1):011023, February 2021. Publisher: American Physical Society.

No offers are available for now.

Logo d'Inria