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

Advances in Mathematics of Communications

Linear programming bounds for unitary codes

Jean Creignou, Hervé Diet

Published Jan 1, 2010• 4 citations
Publisher

Abstract

The linear programming method is developed in the space of unitary matrices in order to obtain bounds for unitary codes relative to the so-called diversity sum and diversity product. Theoretical and numerical results improving previously known bounds are derived.
DOI
10.3934/amc.2010.4.323

Related papers

Upper bounds on codes correcting asymmetric errors (Corresp.)

Torleiv Kløve

A Survey is given of known upper bounds on codes correcting asymmetric errors. The bounds are improved by introducing new Ideas. By solving a linear programming problem an upper bound is given that is easy to compute for all codelengths and all minimum asymmetric distances.

IEEE Transactions on Information Theory•Jan 1, 1981•35 citations

Bounds on the Threshold of Linear Programming Decoding

Pascal O. Vontobel, R. Koetter

Whereas many results are known about thresholds for ensembles of low-density parity-check codes under message-passing iterative decoding, this is not the case for linear programming decoding. Towards closing this knowledge gap, this paper presents some bounds on the thresholds of low-density parity-check code ensembles under linear programming decoding.

arXiv:cs/0602087•IEEE Information Theory Workshop (ITW)•May 25, 2006•16 citations

Upper Bounds on the Size of Quantum Codes

Alexei Ashikhmin, Simon N. Litsyn

Several upper bounds on the size of quantum codes are derived using the linear programming approach. These bounds are strengthened for the linear quantum codes.

arXiv:quant-ph/9709049•Sep 23, 1997•2 citations

Decoding Turbo Codes Based on Their Parity-Check Matrices

Fan Jiang, Eric T. Psota, Lance C. Pérez

The turbo iterative decoding algorithm only performs well for turbo codes with relatively small memories. Moreover, its decoding complexity becomes prohibitively large when the turbo encoders have very large memories. The sum-product and linear programming decoding algorithms are based on the parity-check matrices of the codes. They are widely used to decode low-density parity-check codes. These algorithms do not suffer the limitations of the turbo iterative decoding algorithm. In order to apply them to the turbo codes, the parity-check matrices of turbo codes must be found. By treating turbo codes as serially concatenated codes, the generator and parity-check matrices of the turbo codes are derived in this paper. Turbo codes with low-density parity-check matrices are then designed based on the derived results. Provided these matrices, turbo codes are decoded using the sum-product algorithms. Preliminary results show that the sum-product decoding of turbo codes performs slightly worse than sum-product decoding of conventional low-density parity-check codes. However, since the encoding of turbo codes has less complexity than the straightforward encoding of low-density parity-check codes, this loss in performance may be justified by the drastically decreased encoding complexity. The availability of the parity-check matrices of turbo codes also makes them ready to be decoded by the linear programming decoding algorithm which is optimum for the given linear constraints.

Southeastern Symposium on System Theory (SSST)•Mar 1, 2007•2 citations

Linear Programming Bounds for Entanglement-Assisted Quantum Error-Correcting Codes by Split Weight Enumerators

Ching–Yi Lai, Alexei Ashikhmin

Linear programming approaches have been applied to derive upper bounds on the size of classical and quantum codes. In this paper, we derive similar results for general quantum codes with entanglement assistance by considering a type of split weight enumerator. After deriving the MacWilliams identities for these enumerators, we are able to prove algebraic linear programming bounds, such as the Singleton bound, the Hamming bound, and the first linear programming bound. Our Singleton bound and Hamming bound are more general than the previous bounds for entanglement-assisted quantum stabilizer codes. In addition, we show that the first linear programming bound improves the Hamming bound when the relative distance is sufficiently large. On the other hand, we obtain additional constraints on the size of Pauli subgroups for quantum codes, which allow us to improve the linear programming bounds on the minimum distance of quantum codes of small length. In particular, we show that there is no [[27, 15, 5]] or [[28, 14, 6]] stabilizer code. We also discuss the existence of some entanglement-assisted quantum stabilizer codes with maximal entanglement. As a result, the upper and lower bounds on the minimum distance of maximal-entanglement quantum stabilizer codes with length up to 20 are significantly improved.

arXiv:1602.00413•IEEE Transactions on Information Theory•Jun 2, 2017•103 citations

Finite Classification of Transversal Diagonal Gates Beyond Stabilizer Codes

Xi He, Chao Zhang, Shilin Huang +1 more

We establish that transversal diagonal gates on exact qubit codes of distance at least two can be exhaustively classified within a finite search space. Although code-preserving physical gates can have continuous phases, any projective logical action induced by a transversal diagonal gate can always be realized by a physical gate of finite order. Crucially, we prove that this physical order has an upper bound determined solely by the code parameters. This order bound enables the subset-sum-linear-programming (SSLP) framework introduced in arXiv:2504.20847 to exhaustively enumerate all candidate discrete symmetries, after which the Knill-Laflamme equations determine the remaining continuous code parameters. Applying this method to the nontrivial diagonal sector of exact $((6,2,3))$ codes, SSLP yields $66$ candidate symmetry classes, of which exactly $15$ are realizable, supporting full projective diagonal logical cyclic groups of orders $2$, $3$, and $5$. In particular, for order $5$, the code is unique up to local unitaries and qubit permutations, equivalent to the code constructed in arXiv:2504.20847. This code also attains the minimum length $n=6$ among exact $((n, 2, \ge 3))$ codes whose full projective transversal group cannot be conjugated into the projective Clifford group.

quant-pharXiv:2610.29955•Oct 22, 2026•0 citations
The turbo iterative decoding algorithm only performs well for turbo codes with relatively small memories. Moreover, its decoding complexity becomes prohibitively large when the turbo encoders have very large memories. The sum-product and linear programming decoding algorithms are based on the parity-check matrices of the codes. They are widely used to decode low-density parity-check codes. These algorithms do not suffer the limitations of the turbo iterative decoding algorithm. In order to apply them to the turbo codes, the parity-check matrices of turbo codes must be found. By treating turbo codes as serially concatenated codes, the generator and parity-check matrices of the turbo codes are derived in this paper. Turbo codes with low-density parity-check matrices are then designed based on the derived results. Provided these matrices, turbo codes are decoded using the sum-product algorithms. Preliminary results show that the sum-product decoding of turbo codes performs slightly worse than sum-product decoding of conventional low-density parity-check codes. However, since the encoding of turbo codes has less complexity than the straightforward encoding of low-density parity-check codes, this loss in performance may be justified by the drastically decreased encoding complexity. The availability of the parity-check matrices of turbo codes also makes them ready to be decoded by the linear programming decoding algorithm which is optimum for the given linear constraints.
Linear programming approaches have been applied to derive upper bounds on the size of classical and quantum codes. In this paper, we derive similar results for general quantum codes with entanglement assistance by considering a type of split weight enumerator. After deriving the MacWilliams identities for these enumerators, we are able to prove algebraic linear programming bounds, such as the Singleton bound, the Hamming bound, and the first linear programming bound. Our Singleton bound and Hamming bound are more general than the previous bounds for entanglement-assisted quantum stabilizer codes. In addition, we show that the first linear programming bound improves the Hamming bound when the relative distance is sufficiently large. On the other hand, we obtain additional constraints on the size of Pauli subgroups for quantum codes, which allow us to improve the linear programming bounds on the minimum distance of quantum codes of small length. In particular, we show that there is no [[27, 15, 5]] or [[28, 14, 6]] stabilizer code. We also discuss the existence of some entanglement-assisted quantum stabilizer codes with maximal entanglement. As a result, the upper and lower bounds on the minimum distance of maximal-entanglement quantum stabilizer codes with length up to 20 are significantly improved.
We establish that transversal diagonal gates on exact qubit codes of distance at least two can be exhaustively classified within a finite search space. Although code-preserving physical gates can have continuous phases, any projective logical action induced by a transversal diagonal gate can always be realized by a physical gate of finite order. Crucially, we prove that this physical order has an upper bound determined solely by the code parameters. This order bound enables the subset-sum-linear-programming (SSLP) framework introduced in arXiv:2504.20847 to exhaustively enumerate all candidate discrete symmetries, after which the Knill-Laflamme equations determine the remaining continuous code parameters. Applying this method to the nontrivial diagonal sector of exact ((6,2,3))((6,2,3))((6,2,3)) codes, SSLP yields 666666 candidate symmetry classes, of which exactly 151515 are realizable, supporting full projective diagonal logical cyclic groups of orders 222, 333, and 555. In particular, for order 555, the code is unique up to local unitaries and qubit permutations, equivalent to the code constructed in arXiv:2504.20847. This code also attains the minimum length n=6n=6n=6 among exact ((n,2,≥3))((n, 2, \ge 3))((n,2,≥3)) codes whose full projective transversal group cannot be conjugated into the projective Clifford group.