A Caltech Library Service

Optimal and efficient decoding of concatenated quantum block codes

Poulin, David (2006) Optimal and efficient decoding of concatenated quantum block codes. Physical Review A, 74 (5). Art. No. 052333. ISSN 1050-2947.

See Usage Policy.


Use this Persistent URL to link to this item:


We consider the problem of optimally decoding a quantum error correction code—that is, to find the optimal recovery procedure given the outcomes of partial "check" measurements on the system. In general, this problem is NP hard. However, we demonstrate that for concatenated block codes, the optimal decoding can be efficiently computed using a message-passing algorithm. We compare the performance of the message-passing algorithm to that of the widespread blockwise hard decoding technique. Our Monte Carlo results using the five-qubit and Steane's code on a depolarizing channel demonstrate significant advantages of the message-passing algorithms in two respects: (i) Optimal decoding increases by as much as 94% the error threshold below which the error correction procedure can be used to reliably send information over a noisy channel; and (ii) for noise levels below these thresholds, the probability of error after optimal decoding is suppressed at a significantly higher rate, leading to a substantial reduction of the error correction overhead.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:©2006 The American Physical Society (Received 23 June 2006; published 22 November 2006) I thank Harold Ollivier for several useful conversations on message-passing algorithms and quantum error correction, and Graeme Smith and Jon Yard for comments. This work was supported, in part, by the Gordon and Betty Moore Foundation through Caltech’s Center for the Physics of Information, by the National Science Foundation under Grant No. PHY-0456720, and by the National Science and Engineering Research Council of Canada.
Subject Keywords:error correction codes; quantum computing; decoding; concatenated codes; Monte Carlo methods; quantum noise; quantum communication
Issue or Number:5
Record Number:CaltechAUTHORS:POUpra06
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6388
Deposited By: Archive Administrator
Deposited On:06 Dec 2006
Last Modified:02 Oct 2019 23:32

Repository Staff Only: item control page