Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Science China Information Sciences

Construction of minimal trellises for quantum stabilizer codes

Xiao Fang

Published Jan 1, 2013• 0 citations
OpenAlex

Abstract

The size of vertex set of quantum trellises affects the efficiency of decoding algorithms,which can be improved by reducing the number of vertices.Based on the standard check matrix of stabilizer codes,an algorithm to construct trellis-oriented generators for quantum stabilizer codes is presented.By using this algorithm,the trellises with minimal vertex set can be constructed.In addition,an algorithm to construct trellises iteratively for quantum stabilizer codes is also introduced.The algorithm proposed in this paper is more efficient and less complex than the one proposed by Olliver,and so is more suitable for the applications of larger scale and stricter timeliness.

Related papers

Minimal Trellises for Degenerate Decoding of Quantum Stabilizer Codes

Evagoras Stylianou, Vladimir R. Sidorenko, Christian Deppe +1 more

This paper introduces several techniques for minimal trellis construction for degenerate decoding of quantum stabilizer codes, specifically the minimal multi-goal trellis for the cosets of the stabilizer group S in the normalizer group N. The methods include a merging algorithm, a Shannon-product approach, and the BCJR-Wolf method. The study establishes the necessary properties of multi-goal trellises and bounds on the decoding complexity of the minimal multi-goal trellis using the sum-product Viterbi algorithm. The proposed multi-goal trellises decrease the decoding complexity by a factor O(n), where n is the code length.

Globecom•Dec 8, 2024•1 citation

Trellises for stabilizer codes: Definition and uses

Harold Ollivier, Jean–Pierre Tillich

Trellises play an important theoretical and practical role for classical codes. Their main utility is to devise complexity-efficient error estimation algorithms. Here, we describe trellis representations for quantum stabilizer codes. We show that they share the same properties as their classical analogs. In particular, for any stabilizer code it is possible to find a minimal trellis representation. Our construction is illustrated by two fundamental error estimation algorithms.

arXiv:quant-ph/0512041•Physical Review A•Sep 7, 2006•10 citations

Trellis Decoding for Qudit Stabilizer Codes and Its Application to Qubit Topological Codes

Eric Sabo, Arun B. Aloshious, Kenneth R. Brown

Trellis decoders are a general decoding technique first applied to qubit-based quantum error correction codes by Ollivier and Tillich in 2006. Here, we improve the scalability and practicality of their theory, show that it has strong structure, extend the results using classical coding theory as a guide, and demonstrate a canonical form from which the structural properties of the decoding graph may be computed. The resulting formalism is valid for any prime-dimensional quantum system. The modified decoder works for any stabilizer code$S$and separates into two parts: 1) a one-time offline computation that builds a compact graphical representation of the normalizer of the code,$\mathcal {S}^{\perp}$and 2) a quick, parallel, online query of the resulting vertices using the Viterbi algorithm. We show the utility of trellis decoding by applying it to four high-density length-20 stabilizer codes for depolarizing noise and the well-studied Steane, rotated surface, and 4.8.8/6.6.6 color codes for$Z$only noise. Numerical simulations demonstrate a 20% improvement in the code-capacity threshold for color codes with boundaries by avoiding the mapping from color codes to surface codes. We identify trellis edge number as a key metric of difficulty of decoding, allowing us to quantify the advantage of single-axis ($X$or$Z$) decoding for Calderbank–Steane–Shor codes and block decoding for concatenated codes.

arXiv:2106.08251•IEEE Transactions on Quantum Engineering•Jan 1, 2024•12 citations

Construction and complement circuit of a quantum stabilizer code with length 7

Duc Manh Nguyen, Sunghwan Kim

In this paper, a new method for the construction of a quantum stabilizer code from circulant permutation matrices is discussed. First, we choose a finite-length vector randomly, and we can construct circulant permutation matrices from the vectors. Then, the parity-check matrix can be produce from the circulant permutation matrices. Hence, the generators of stabilizer code are determined according to the parity-check matrix and quantum stabilizer group are defined from the generators. From the stabilizer group, codewords of the proposed quantum codes can also be generated. Finally, a complete efficient encoding and decoding quantum circuit of [[7,1,3]] is proposed. [[7,1,3]] is stabilizer code that construction based on our method is an seven-qubit code that protects a one-qubit state with up to one error, which is very important for quantum information processing.

International Conference on Ubiquitous and Future Networks•Jul 1, 2016•9 citations

A survey on decoding quantum LDPC codes

Jean–Pierre Tillich

Quantum low-density parity-check (LDPC) codes are stabilizer codes in which each stabilizer generator acts on O(1) qubits and each qubit participates in O(1) generators. Some famous classes of codes such as the toric code are quantum LDPC codes. There are several reasons that explain why this subclass of stabilizer codes is particularly interesting. For instance, last year it was shown by Gottesman that such codes would in principle allow fault-tolerant quantum computing with constant overhead.However, for this application we need quantum LDPC codes that are able to encode a linear fraction of qubitswith good minimum distance properties and that are equipped with an efficient decoding algorithm.The fact that their classical counterpart enjoys all these nice properties could lead to think that it will be easyto obtain the same result in the quantum setting. However it has turned out that decoding quantum LDPC codes is a much more involved issue than decoding classical LDPC codes.The latter class of codes is decoded successfully by low complexity iterative decoding algorithms.In principle, such algorithms could also be used to decode quantum LDPC codes.However, this approach fails for quantum LDPC codes due to the fact that suchcodes are inherently highly degenerate. I will survey and discuss in this talk alternative approaches that have been successful for some subclasses of quantum LDPC codes.

•Jan 10, 2015•0 citations

Minimal error-trellises for linear block codes

M. Ariel, Jakov Snyders

An error-trellis is an efficient means to accomplish maximum likelihood decoding of a linear (n,k) block code C over GF(q). It represents the coset of C that contains the symbol-by-symbol detected version of the received vector. The trellis we construct has only n-k sections and the structure of each section is determined solely by the value of an associated q-ary symbol of the syndrome. Hence, the entire set of q/sup n-k/ trellises for all the cosets of C is formed by a set of q(n-k) distinct sections. The error-trellis is invariant under permutation of coordinates and attains the vertex count of a minimal code-trellis with the same sectionalization.

IEEE International Symposium on Information Theory (ISIT)•Nov 27, 2002•1 citation
The size of vertex set of quantum trellises affects the efficiency of decoding algorithms,which can be improved by reducing the number of vertices.Based on the standard check matrix of stabilizer codes,an algorithm to construct trellis-oriented generators for quantum stabilizer codes is presented.By using this algorithm,the trellises with minimal vertex set can be constructed.In addition,an algorithm to construct trellises iteratively for quantum stabilizer codes is also introduced.The algorithm proposed in this paper is more efficient and less complex than the one proposed by Olliver,and so is more suitable for the applications of larger scale and stricter timeliness.
This paper introduces several techniques for minimal trellis construction for degenerate decoding of quantum stabilizer codes, specifically the minimal multi-goal trellis for the cosets of the stabilizer group S in the normalizer group N. The methods include a merging algorithm, a Shannon-product approach, and the BCJR-Wolf method. The study establishes the necessary properties of multi-goal trellises and bounds on the decoding complexity of the minimal multi-goal trellis using the sum-product Viterbi algorithm. The proposed multi-goal trellises decrease the decoding complexity by a factor O(n), where n is the code length.
Trellis decoders are a general decoding technique first applied to qubit-based quantum error correction codes by Ollivier and Tillich in 2006. Here, we improve the scalability and practicality of their theory, show that it has strong structure, extend the results using classical coding theory as a guide, and demonstrate a canonical form from which the structural properties of the decoding graph may be computed. The resulting formalism is valid for any prime-dimensional quantum system. The modified decoder works for any stabilizer codeSSSand separates into two parts: 1) a one-time offline computation that builds a compact graphical representation of the normalizer of the code,S⊥\mathcal {S}^{\perp}S⊥and 2) a quick, parallel, online query of the resulting vertices using the Viterbi algorithm. We show the utility of trellis decoding by applying it to four high-density length-20 stabilizer codes for depolarizing noise and the well-studied Steane, rotated surface, and 4.8.8/6.6.6 color codes forZZZonly noise. Numerical simulations demonstrate a 20% improvement in the code-capacity threshold for color codes with boundaries by avoiding the mapping from color codes to surface codes. We identify trellis edge number as a key metric of difficulty of decoding, allowing us to quantify the advantage of single-axis (XXXorZZZ) decoding for Calderbank–Steane–Shor codes and block decoding for concatenated codes.
In this paper, a new method for the construction of a quantum stabilizer code from circulant permutation matrices is discussed. First, we choose a finite-length vector randomly, and we can construct circulant permutation matrices from the vectors. Then, the parity-check matrix can be produce from the circulant permutation matrices. Hence, the generators of stabilizer code are determined according to the parity-check matrix and quantum stabilizer group are defined from the generators. From the stabilizer group, codewords of the proposed quantum codes can also be generated. Finally, a complete efficient encoding and decoding quantum circuit of [[7,1,3]] is proposed. [[7,1,3]] is stabilizer code that construction based on our method is an seven-qubit code that protects a one-qubit state with up to one error, which is very important for quantum information processing.
Quantum low-density parity-check (LDPC) codes are stabilizer codes in which each stabilizer generator acts on O(1) qubits and each qubit participates in O(1) generators. Some famous classes of codes such as the toric code are quantum LDPC codes. There are several reasons that explain why this subclass of stabilizer codes is particularly interesting. For instance, last year it was shown by Gottesman that such codes would in principle allow fault-tolerant quantum computing with constant overhead.However, for this application we need quantum LDPC codes that are able to encode a linear fraction of qubitswith good minimum distance properties and that are equipped with an efficient decoding algorithm.The fact that their classical counterpart enjoys all these nice properties could lead to think that it will be easyto obtain the same result in the quantum setting. However it has turned out that decoding quantum LDPC codes is a much more involved issue than decoding classical LDPC codes.The latter class of codes is decoded successfully by low complexity iterative decoding algorithms.In principle, such algorithms could also be used to decode quantum LDPC codes.However, this approach fails for quantum LDPC codes due to the fact that suchcodes are inherently highly degenerate. I will survey and discuss in this talk alternative approaches that have been successful for some subclasses of quantum LDPC codes.
An error-trellis is an efficient means to accomplish maximum likelihood decoding of a linear (n,k) block code C over GF(q). It represents the coset of C that contains the symbol-by-symbol detected version of the received vector. The trellis we construct has only n-k sections and the structure of each section is determined solely by the value of an associated q-ary symbol of the syndrome. Hence, the entire set of q/sup n-k/ trellises for all the cosets of C is formed by a set of q(n-k) distinct sections. The error-trellis is invariant under permutation of coordinates and attains the vertex count of a minimal code-trellis with the same sectionalization.