Quantum Error Correcting Codes

This work is funded by ANR project “C.O.C.Q.”

Richard Feynman was the first physicist to coin the idea of using quantum systems for processing information. This idead has developed since then into an exciting research area (with links to cryptography to complexity theory etc.). For instance quantum computer should be able to efficiently solve several “hard” problems such as integer factorization, a process which makes it possible to crack cryptographic schemes very quickly. In order to take advantage of the quantum nature of physical systems to process information, it is however mandatory to protect them from unwanted evolutions. If quantum registers that are not protected from noise, the very fragile superpositions required for efficiently manipulating quantum information tend to disappear exponentially fast with the number of qubits involved. This effect – called decoherence – can nonetheless be reduced by using quantum error correcting codes. Peter Shor was the first one to propose a correcting scheme in 1995, followed by the introduction of the stabilizer formalism by Gottesman in 1997. It has also been shown that quantum information processing can be done fault-tolerantly (would be feasible even in the presence of – rare enough – qubit errors and gate faults)

In spite of these important results, properties of quantum channels and codes are less well understood than is the case with their classical counterparts. With D. Declercq (ETIS) and J.P. Tillich (INRIA/CODES) we try to devise versatile constructions of quantum codes inspired by the best classical codes, and analyze their performance. Among the most prominent families of classical codes for which it is interesting to obtain a quantum analogue are LDPC codes and turbo-codes. These have created a breakthrough in coding theory, mostly because for a large class of channels and with an iterative decoding algorithm of reasonable complexity they display astonishing performance at rates extremely close to the Shannon limit. We thus aim at proposing good quantum versions of these two families of classical codes. The main goal here is to find quantum LDPC and turbo-code families of non vanishing rate, unbounded minimum distance and good iterative decoding performance.

Designing pure quantum decoding algorithms We are seeking improvements to iterative decoding algorithms which are used to decode QECCs. There is some substantial gain in performance which can be expected here because quantum LDPC codes have necessarily many small cycles in their Tanner graph which degrade iterative decoding performance. We are working on a better local decoding operations based on generalized belief propagation techniques to overcome the presence of such small cycles.