PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum serial turbo-codes

David Poulin, Jean-Pierre Tillich, Harold Ollivier

arXiv:0712.2888v2quant-ph

TL;DR

Quantum serial turbo-codes address the challenge of designing quantum codes with practical iterative decoding, amid difficulties with quantum LDPC code construction and decoding. The paper develops a circuit-based theory and decoder, and proves that recursive quantum convolutional encoders have catastrophic error propagation. Its non-recursive constructions have bounded minimum distance but show useful iterative-decoding performance over studied block sizes and word error rates.

  • Problem

    Quantum LDPC codes face design and decoding difficulties, while structured quantum codes need efficient decoding approaches.

    Source: §I · p. 2

  • Method

    The paper develops quantum serial turbo-codes from interleaved serial concatenations of quantum convolutional codes, using a circuit representation, state diagram, and iterative decoder.

    Source: §I · p. 3, §VII · p. 20

  • Results

    All recursive quantum convolutional encoders have catastrophic error propagation, while the non-catastrophic, non-recursive constructions show good iterative-decoding performance across practical ranges despite bounded minimum distance.

    Source: §VII · pp. 20–21

  • Takeaways & Limitations

    Quantum turbo-codes offer design freedom, graphs without 4-cycles, and an iterative decoder that explicitly uses code degeneracy.

    Source: §VII · p. 21

    The resulting code families have bounded minimum distance, and their minimum distance is not guaranteed to grow with the number of encoded qubits.

    Source: §I · p. 2, §VII · p. 21

Abstract

from arXiv · show

We present a theory of quantum serial turbo-codes, describe their iterative decoding algorithm, and study their performances numerically on a depolarization channel. Our construction offers several advantages over quantum LDPC codes. First, the Tanner graph used for decoding is free of 4-cycles that deteriorate the performances of iterative decoding. Secondly, the iterative decoder makes explicit use of the code's degeneracy. Finally, there is complete freedom in the code design in terms of length, rate, memory size, and interleaver choice. We define a quantum analogue of a state diagram that provides an efficient way to verify the properties of a quantum convolutional code, and in particular its recursiveness and the presence of catastrophic error propagation. We prove that all recursive quantum convolutional encoder have catastrophic error propagation. In our constructions, the convolutional codes have thus been chosen to be non-catastrophic and non-recursive. While the resulting families of turbo-codes have bounded minimum distance, from a pragmatic point of view the effective minimum distances of the codes that we have simulated are large enough not to degrade the iterative decoding performance up to reasonable word error rates and block sizes. With well chosen constituent convolutional codes, we observe an important reduction of the word error rate as the code length increases.

I. INTRODUCTION

The introduction motivates structured quantum codes and presents serial turbo-codes as an alternative to quantum LDPC codes, while warning that recursive quantum convolutional encoders are catastrophic. The classical preliminaries frame encoders as reversible circuits, a representation carried into the quantum construction.

I. INTRODUCTION

  • Quantum LDPC codes face design and decoding difficulties, including orthogonality constraints, many 4-cycles, and decoders that do not exploit degeneracy.The introduction notes that whether quantum LDPC families can have both non-vanishing rate and unbounded minimum distance remains unknown.Source: §I · p. 2
  • Quantum turbo-codes avoid 4-cycles, explicitly use degeneracy in iterative decoding, and allow freedom in length, rate, memory size, and interleaver choice.The introduction relates these advantages to the lack of restrictions on the interleaver.Source: §I · p. 2
  • Recursive quantum convolutional encoders all have catastrophic error propagation, making them unsuitable for standard serial turbo-code schemes despite their polynomial minimum distances.The constructions therefore use non-catastrophic, non-recursive encoders; their families are not guaranteed to have growing minimum distance, although simulations show useful performance at moderate word error rates and block sizes.Source: §I · p. 2

II. CLASSICAL PRELIMINARIES

  • A circuit representation of convolutional encoders supports a quantum state diagram for studying recursiveness and catastrophic propagation, and helps derive the iterative decoder.The paper also uses the circuit framework to present quantum convolutional-code decoding.Source: §II · p. 3, §I · p. 3

A. Linear block codes

  • Classical block codes are represented by an invertible encoding matrix that maps logical and syndrome inputs to encoded outputs.The inverse encoding maps an error into its logical transformation and syndrome, as illustrated by the encoder circuit.Source: A. Linear block codes · p. 3

B. Convolutional codes

The section presents convolutional encoders as repeated applications of an invertible seed transformation, linking a circuit description to a linear-filter representation. It also introduces memory, termination, systematic encoding, and recursiveness as relevant properties of these codes.

B. Convolutional codes

  • A convolutional code is built by repeatedly applying a linear invertible seed transformation, with memory bits connecting successive time slices.The encoding can be padded by setting the final logical inputs to zero; the rate is k/n + O(1/N).Source: B. Convolutional codes · pp. 4–5
  • The circuit and linear-filter descriptions encode the same transformation and have corresponding memory states, enabling the state diagram to be defined from the circuit.The filter representation itself is linear but not invertible; the seed circuits are built from controlled-not gates and are invertible.Source: Figure 3 · p. 4, B. Convolutional codes · p. 5, Figure 4 · p. 5
  • A systematic encoder includes its input stream as a sub-stream of its output, while a recursive encoder has a transfer function involving genuine Laurent series.For recursive encoders, a weight-1 logical input produces an infinite-weight output at infinite duration; systematic encoders are used to avoid catastrophic error propagation.Source: B. Convolutional codes · p. 5
  • Recursive constituent encoders give classical serial turbo-code families unbounded minimum distance, whereas catastrophic encoders cannot be used directly in standard turbo-code schemes.The section links catastrophic behavior to a finite physical error mapping to infinitely many logical bits under the inverse encoder.Source: B. Convolutional codes · p. 5

III. QUANTUM MECHANICS AND QUANTUM CODES

This section reviews quantum codes and error models using discrete representations that connect them to classical coding theory. It introduces Pauli operators and their binary representation, then describes the depolarizing channel considered in the paper.

III. QUANTUM MECHANICS AND QUANTUM CODES

  • Quantum codes can be studied through discrete objects such as parity-check matrices, encoding matrices, and syndromes, while the encoder also clarifies logical cosets.The section emphasizes that logical cosets distinguish quantum stabilizer codes from classical linear codes.Source: §III · p. 5

A. Qubits and the Pauli group

  • Effective Pauli operators can be represented by binary couples, with a symplectic inner product that determines whether two operators commute.The effective Pauli group identifies operators that differ only by a multiplicative constant.Source: A. Qubits and the Pauli group · p. 6
  • The depolarizing channel applies independent coordinate errors, with no error occurring with probability 1 − p and X, Y, or Z errors each occurring with probability p/3.The paper describes this channel as a quantum analogue of the binary symmetric channel.Source: A. Qubits and the Pauli group · pp. 6–7

B. Stabilizer codes: Hilbert space perspective

The section defines stabilizer codes as subspaces specified by commuting Pauli operators and explains how Clifford transformations provide efficient encoding descriptions. It connects the Hilbert-space definition to binary matrices that preserve the symplectic inner product.

B. Stabilizer codes: Hilbert space perspective

  • Clifford transformations preserve the Pauli group under conjugation and can be specified by a binary encoding matrix together with phases.The encoding matrix is symplectic, and Clifford transformations can be implemented using O(n^2) elementary gates.Source: B. Stabilizer codes: Hilbert space… · p. 7
  • A stabilizer code is the subspace fixed by n − k independent, mutually commuting Pauli generators and has dimension 2^k.The generator signs can change the code but not its error-correction properties.Source: B. Stabilizer codes: Hilbert space… · pp. 7–8
  • The stabilizer generators are mutually orthogonal under the symplectic inner product, and their span specifies the stabilizer space.The stabilizer-code subspace can also be described through the encoding transformation acting on logical inputs and fixed stabilizer inputs.Source: B. Stabilizer codes: Hilbert space… · pp. 7–8

C. Decoding

Quantum decoding uses the measured syndrome to identify the most likely logical transformation, while accounting for errors that are indistinguishable but harmless. This makes decoding a search over logical cosets rather than individual physical errors.

C. Decoding

  • The syndrome reveals only the X component Sx of the inverse-encoded error's stabilizer component, leaving its Z component Sz undetermined.The decoding discussion is explicitly for Pauli channels.Source: C. Decoding · pp. 8–9
  • Errors with the same syndrome and logical transformation are degenerate and need not be distinguished, so decoding seeks the most likely logical coset.The harmless undetected errors form C(I), and each logical coset groups errors that differ by such errors.Source: C. Decoding · p. 9
  • Maximum-likelihood decoding chooses the logical transformation L with highest conditional probability given Sx.The decoder is defined as an argmax over L of P(L|Sx).Source: C. Decoding · p. 9
  • The quantum likelihood calculation sums over Sz, reflecting the code's coset structure.The syndrome is obtained from the stabilizer checks through the symplectic product.Source: C. Decoding · pp. 8–9

D. Comparison between stabilizer codes and classical linear codes

The paper recasts stabilizer codes and quantum convolutional codes in circuit and symplectic terms. These representations expose how quantum codewords, encoding, and decoding relate to their classical counterparts.

D. Comparison between stabilizer codes and classical linear codes

  • Quantum codewords are grouped into cosets of C(I), which plays the role of the zero codeword; minimum distance counts the least-weight element outside that coset.The stabilizer parity-check rows are symplectically orthogonal, and the syndrome uses the symplectic product rather than ordinary matrix multiplication.Source: D. Comparison between stabilizer codes… · pp. 9–10

A. Quantum convolutional codes

  • A quantum convolutional encoder repeats a seed transformation U across time, with memory qubits linking slices and termination parameter t setting the final constrained slices.Its rate is kN/(n(N+t)+m), approaching k/n for fixed t as N grows.Source: A. Quantum convolutional codes · pp. 10–11
  • For fixed memory size, convolutional encoding has linear circuit complexity in N, and its decoding complexity scales linearly with the number K of encoded qubits.By contrast, maximum-likelihood decoding of a general stabilizer code is NP-hard without additional structure.Source: A. Quantum convolutional codes · p. 11

B. State diagram

The quantum state diagram represents how memory states transition under logical and physical Pauli labels. It supports tests of catastrophic error propagation and recursive behavior in convolutional encoders.

B. State diagram

  • Each state-diagram edge records a transition between memory states with logical and physical labels, while the stabilizer input is restricted to I or Z.The diagram omits information about that stabilizer input and therefore captures only partial information about the seed transformation.Source: B. State diagram · p. 12
  • A non-catastrophic encoder has no cycle with zero physical weight and nonzero logical weight.The example seed transformation is catastrophic because it has such a cycle, allowing finite physical error to produce unbounded logical error with finite syndrome.Source: B. State diagram · p. 12
  • All simulated encoders were non-catastrophic; the paper notes that catastrophic encoders can have large minimum distance yet perform poorly under iterative decoding.A stronger condition used in the simulations permits only the zero-state self-loop to have zero physical weight.Source: B. State diagram · p. 12
  • Systematic quantum encoding forces stabilizers to act trivially on the first k output qubits, giving minimum distance 1; non-catastrophicity must therefore be built in separately.The state diagram provides an efficient way to verify it.Source: B. State diagram · p. 13
  • Quantum recursiveness requires infinite-weight responses for every element in the coset of an impulsive logical input, not only for the encoded Pauli representatives.The paper defines recursive encoders through admissible paths and says the property can be tested by constructing the state diagram.Source: B. State diagram · p. 13

C. Interleaved serial concatenation

A serial quantum turbo-code interleaves an outer and inner convolutional code, with the interleaver preserving Pauli-stream weight. The section also introduces distance spectra and operational error-rate measures for assessing code performance.

C. Interleaved serial concatenation

  • Interleaving preserves the weight of N-Pauli streams, while the interleaved concatenation's rate is kOut/nIn.The encoding is assembled from the outer encoder, interleaver, and inner encoder.Source: C. Interleaved serial concatenation · p. 13
  • A serial quantum turbo-code combines outer and inner quantum convolutional encoders through an interleaver that permutes qubits and may apply single-qubit Clifford transformations.The inner code's input size matches the outer code's output size, and the concatenated rate is the product of their rates.Source: C. Interleaved serial concatenation · p. 13

D. Figure of merit

  • The distance spectrum F(w) counts admissible paths with physical weight w and positive logical weight, while F1(w) restricts the count to logical weight one.The free distance is the smallest weight with F(w)>0; d1 is the smallest weight with F1(w)>0.Source: D. Figure of merit · p. 14
  • The concatenated code's minimum distance is at most d1 of the outer code, so design favors large outer free distance and inner d1 while suppressing low-weight spectrum counts.The word error rate is the probability that at least one qubit in the block is decoded incorrectly, unlike the qubit error rate, which is per logical qubit.Source: D. Figure of merit · p. 14

E. Recursive convolutional encoders are catastrophic

Theorem 1 establishes that every recursive quantum convolutional encoder has catastrophic error propagation. The proof connects this result to a zero-physical-weight cycle carrying nonzero logical weight in the encoder’s state diagram.

E. Recursive convolutional encoders are catastrophic

  • Non-catastrophic error propagation is necessary for good iterative-decoding performance, while recursive inner encoders yield unbounded minimum distance in classical serial turbo-codes.The paper identifies this trade-off as relevant background for the quantum result.Source: E. Recursive convolutional encoders… · p. 14
  • The quantum proof is more subtle than the classical analogue because of the code’s coset structure.The paper says the classical proof carries over almost verbatim under its definition of recursive encoders.Source: E. Recursive convolutional encoders… · p. 14
  • Every recursive quantum convolutional encoder is catastrophic, a result attributed to the symplectic constraints on its seed transformation.The paper notes that catastrophic and recursive encoders are distinct notions in the classical setting.Source: E. Recursive convolutional encoders… · p. 14
  • The kernel graph of a recursive encoder has more than the zero vertex, while the kernel graph has constant in-degree one and positive out-degree at every vertex.The proof uses these properties to establish the cycle result.Source: E. Recursive convolutional encoders… · p. 15
  • A recursive encoder’s kernel graph contains an edge with nonzero logical weight, which leads to a zero-physical-weight cycle with nonzero logical weight.That cycle makes the encoder catastrophic.Source: E. Recursive convolutional encoders… · p. 15

V. DECODING

The decoding section adapts soft-input soft-output decoding to quantum convolutional codes on memoryless Pauli channels. It describes a circuit-based constituent-code decoder and an iterative turbo procedure, while noting that the overall decoder is suboptimal because it ignores correlations in the induced outer channel.

V. DECODING

  • For memoryless Pauli channels, the quantum soft-input soft-output decoder computes logical-variable probabilities conditioned on the measured syndrome.The procedure adapts the classical serial-turbo soft-input soft-output algorithm to quantum codes.Source: §V · p. 15, A. Decoding of convolutional codes · p. 16

A. Decoding of convolutional codes

  • The convolutional-code decoder is presented through the circuit description, which is essentially equivalent to sum-product decoding on the code trellis.The circuit formulation alleviates complications arising from quantum-specific decoding features.Source: A. Decoding of convolutional codes · p. 16
  • Convolutional-code decoding combines a backward probability pullback, a forward push-forward, and a local update to produce the final probabilities.These passes propagate probabilities through the circuit and combine them.Source: A. Decoding of convolutional codes · p. 16

B. Turbo decoder

  • Turbo decoding alternates inner- and outer-code SISO decoding, passing the inner decoder’s logical-variable probabilities to the outer decoder and feeding information back for another iteration.Iterations can stop after a fixed number of rounds or when the estimate stops changing.Source: B. Turbo decoder · pp. 16–18
  • The overall iterative turbo decoder is suboptimal because the induced outer channel is correlated, but the decoder uses only its marginals for efficiency.The constituent-code decoding procedure itself is exact.Source: B. Turbo decoder · p. 18

VI. RESULTS

The simulations show lower word error rates below pseudo-thresholds as block size increases, with the observed improvement saturating around K=4000. The results also show that memory size mainly affects error suppression below the pseudo-threshold, while the reported minimum-distance bounds do not directly determine decoder performance.

VI. RESULTS

  • The construction generates random seed transformations and rejects any whose state diagram indicates catastrophic behavior; non-catastrophicity is the only systematic selection criterion.Source: §VI · p. 19
  • The estimated turbo-code minimum-distance upper bounds are 24, 42, and 48 for the listed concatenations, but these bounds do not directly predict code performance.The actual minimum distance depends on the interleaver, and decoding is not performed with a minimum-distance decoder.Source: §VI · p. 19
  • For rate 1 4, the turbo-code reaches p_th ≈0.048 versus p_th ≈0.033 for LDPC codes, with the turbo result achieved at a smaller block size.The paper notes that a larger block should further improve the turbo-code result.Source: §VI · pp. 19–20
  • Below pseudo-thresholds, WER decreases as encoded-qubit count grows, but improvement appears to saturate around K=4000.Reported pseudo-thresholds are approximately 0.098 for U(3,1,3) and 0.067 for U(2,1,4).Source: §VI · p. 19, Figure 12 · p. 20, Figure 13 · p. 20
  • For fixed K, larger memory chiefly sharpens the WER slope below the pseudo-threshold rather than changing its value.The reported WER slope increases with memory size across the configurations shown.Source: §VI · p. 20, Figure 15 · p. 20

VII. CONCLUSION

The paper develops quantum serial turbo-codes and a state-diagram method for analyzing convolutional encoders. It proves recursive encoders have catastrophic error propagation, while its non-recursive, non-catastrophic constructions show good iterative decoding performance despite bounded minimum distance.

VII. CONCLUSION

  • The circuit representation simplifies the state diagram and supports an intuitive derivation of the efficient decoding algorithm.The state diagram is used to analyze encoder properties, including recursiveness and catastrophic error propagation.Source: §VII · p. 20
  • Every recursive quantum convolutional encoder has catastrophic error propagation, so the constructions use non-recursive, non-catastrophic encoders.The resulting codes have bounded minimum distance but perform well under iterative decoding across practical block sizes and word error rates.Source: §VII · pp. 20–21
  • Turbo-codes allow flexible choices of length, rate, memory size, and interleaver, avoid 4-cycles in the decoding graph, and explicitly use code degeneracy.The paper identifies freedom in interleaver choice as crucial because it supplies the randomness associated with these codes’ success.Source: §VII · p. 21
  • The authors identify operator quantum error correction and doping as possible future approaches to the obstacle of catastrophic error propagation.The theorem’s conclusions are established in the context of subspace stabilizer codes.Source: §VII · p. 21

APPENDIX

The appendix supplies linear-algebra arguments used in the proofs about quantum convolutional encoders and their state diagrams, including results bearing on recursive and non-recursive behavior.

APPENDIX

  • The appendix derives a dimension for the subspace orthogonal to the rows of Ueff and identifies the rows of [ΣP : ΣM] as a basis.The stated dimension is n − k.Source: APPENDIX · p. 21
  • The appendix establishes that a kernel-graph vertex has a unique incoming zero-physical-weight edge, using orthogonality and uniqueness arguments.The proof identifies a unique predecessor satisfying the stated equality.Source: APPENDIX · p. 22
  • A finite path with logical weight 1 and non-zero physical weight can be extended with zero transformations until it reaches the zero state, contradicting recursiveness.The argument uses a finite power of the memory transformation whose null space contains the relevant state.Source: APPENDIX · p. 22
  • A path with logical weight 1 can be extended by stabilizer inputs and then zero transformations to return to the origin, completing the non-recursiveness argument.The final return follows because the resulting memory state lies in the kernel of a finite power of the memory transformation.Source: APPENDIX · pp. 22–23
Loading 0712.2888v2…