I have been reading about a family of quantum error correction codes called Quantum Turbo Codes, which are the quantum analog of the well-known classical Turbo codes. This codes were introduced in quantum serial turbo codes and the entanglement-assisted version of those was presented in entanglement-assisted quantum turbo codes.

In such papers, the decoding algorithm presented for is a modification of the classical belief propagation algorithms that are used for obtaining the most probable codeword received based on the channel information and the syndromes read from the information received. The difference in the quantum paradigm is that the belief propagation algorithm here is used to detect the most probable error that happened in the channel and so the recovery operation can be applied to the received quantum states. This modified algorithm is purely classical, and so it would be executed in a classical computer before feeding the decoded information back to the quantum computer.

The fact that it is a classical algorithm presents some problems, such as the fact that if the belief propagation takes more time than the decoherence time of the qubits, then the recovery would be unsuccesfull as more errors would have happened before correction is applied.

That's why I wonder if there are quantum versions of the belief propagation algorithms that use the parallel nature of quantum computers to obtain substantial speedups in the decoding process. I am seeking for reference respect to this topic, or to know if there are research groups concerned about this kind of problem.

  • 2
    This seems like a very circular problem: build a quantum computer to run the algorithm for belief propagation. But that computer is noisy as well, so needs to be error corrected, and so to do the belief propagation you need another quantum computer.... In fact it's probably worse than that because if the second computation takes long enough to require error correction, you've already got extra errors on your original computer, and you're already dead. – DaftWullie Aug 8 at 14:18
  • 1
    Yeah, the thought that you present here is very interesting, however, I think that it may be incorrect at some point, at least as I see the problem. Advanced coding schemes such as the Turbo are too complex in order to generate fault-tolerant schemes, and so they would be used for quantum communications where the complexity of coder/decoder are asumed to be able to support such heavy computations. That way, the potential fault-tolerant computers would use schemes that allow belief propagation algorithms to run, and so those communications could use Turbo like coding with quantum belief prop. – Josu Etxezarreta Martinez Aug 8 at 14:26

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.