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

IEEE Transactions on Information Theory

Shadow bounds for self-dual codes

Eric M. Rains

Published Jan 1, 1998• 237 citations
Publisher

Abstract

Conway and Sloane (1990) have previously given an upper bound on the minimum distance of a singly-even self-dual binary code, using the concept of the shadow of a self-dual code. We improve their bound, finding that the minimum distance of a self-dual binary code of length n is at most 4[n/24]+4, except when n mod 24=22, when the bound is 4[n/24]+6. We also show that a code of length a multiple of 24 meeting the bound cannot be singly-even. The same technique gives similar results for additive codes over GF(4) (relevant to quantum coding theory).

DOI
10.1109/18.651000

Related papers

An improved upper bound on the minimum distance of doubly-even self-dual codes

Ilia Krasikov, Simon N. Litsyn

We derive a new upper bound on the minimum distance d of doubly-even self-dual codes of length n. Asymptotically, for n growing, it gives lim/sub n/spl rarr//spl infin// sup d/n/spl les/(5-5/sup 3/4/)/10<0.165630, thus improving on the Mallows-Odlyzko-Sloane bound of 1/6 and our recent bound of 0.166315.

IEEE Transactions on Information Theory•Jan 1, 2000•11 citations

Linear programming bounds for doubly-even self-dual codes

Ilia Krasikov, Simon N. Litsyn

Using a variant of the linear programming method we derive a new upper bound on the minimum distance d of doubly-even self-dual codes of length n. Asymptotically, for n growing, it gives d/n/spl les/0.166315/spl middot//spl middot//spl middot/+o(1), thus improving on the Mallows-Odlyzko-Sloane bound of 1/6. To establish this, we prove that in any doubly even-self-dual code the distance distribution is asymptotically upper-bounded by the corresponding normalized binomial distribution in a certain interval.

IEEE Transactions on Information Theory•Jul 1, 1997•15 citations

Subcodes of binary self-dual codes of minimum distance six

Xuejun Zhao

The subcodes of binary self-dual codes whose length n between 22 and 30 and minimum distance six are studied by using of a random search algorithm,and the subcodes of dual distance 3,4,5 and 6 of these self-dual codes are constructed.The code chains of these self-orthogonal subcodes and the S-chains obtained from the dual of these self-orthogonal subcodes are also determined.According to Steane’s construction,some very good quantum codes of distance five and six are constructed by the obtained S-chains,and some of these quantum codes have improved parameters than previously known codes.

Computer Engineering and Applications Journal•Jan 1, 2008•0 citations

Performance of extremal codes

Anton Malevich

Assume that a binary linear code is transmitted over a channel with the symbol error probability p and that bounded distance decoding is used. In this case it is known [3] that for sufficiently small p the performance of the code is only a question of the weight distribution (weight enumerators of more efficient codes are lexicographically smaller). Based on this result we study the efficiency of extremal self-dual codes. Extremal doubly-even codes have unique weight enumerators for each length, and at first glance it may seem that these codes should perform worse than other codes with the same minimum distance. However we show that this is not always the case when comparing to singly-even codes. We also show that a doubly-even code may perform better than a non self-dual code. We find the most efficient codes among extremal singly-even codes of length 24m + 8 and 24m + 16. We also consider some families of extremal singly-even codes with uniquely determined weight enumerators (s-extremal codes, codes with minimal shadow). It appears that they always perform better than extremal doublyeven codes of the same length. The results are joint work with Wolfgang Willems (Magdeburg).

•Jan 1, 2006•0 citations

Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance

Rafail Ostrovsky

We prove that the quantum code distance is NP-hard to approximate within an additive error of $c N$, for some constant $c >0$, where $N$ is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to $Ω(N)$ and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical $X$- and $Z$-check spaces, and with a constant rate and constant relative distance. For every fixed $λ>1$, there is a constant $c>0$ such that hardness still holds even when every nonidentity stabilizer has weight greater than $λ$ times the quantum distance. We also improve the hardness gap of graph state distance on $N$ vertices of Grigorescu, Jha, and Samperton from cube-root to $Ω(N)$, resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most $N$. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2). Our main technique for both hardness bounds above is classical: we show how to convert any code $C$ of length $m$ into a self-dual code $A(C)$ of length $N=Θ(m)$ while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of $C$. It comes with a linear embedding $τ: \mathbb F_2^m \hookrightarrow \mathbb F_2^N$. The embedding doubles all Hamming distances between vectors in $\mathbb F_2^m$ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of $A(C)$ of weight at most $2m$ are exactly $τ(C)$.

quant-pharXiv:2609.22669•Sep 22, 2026•0 citations

Some new Results for Additive Self-Dual Codes over GF(4)

Zlatko Varbanov

Additive code C over GF(4) of length n is an additive subgroup of GF(4)n. It is well known [4] that the problem of finding stabilizer quantum error-correcting codes is transformed into problem of finding additive self-orthogonal codes over the Galois field GF(4) under a trace inner product. Our purpose is to construct good additive self-dual codes of length 13 ≤ n ≤ 21. In this paper we classify all extremal (optimal) codes of lengths 13 and 14, and we construct many extremal codes of lengths 15 and 16. Also, we construct some new extremal codes of lengths 17,18,19, and 21. We give the current status of known extremal (optimal) additive self-dual codes of lengths 13 to 21.

Serdica Journal of Computing•Jul 4, 2007•11 citations
Conway and Sloane (1990) have previously given an upper bound on the minimum distance of a singly-even self-dual binary code, using the concept of the shadow of a self-dual code. We improve their bound, finding that the minimum distance of a self-dual binary code of length n is at most 4[n/24]+4, except when n mod 24=22, when the bound is 4[n/24]+6. We also show that a code of length a multiple of 24 meeting the bound cannot be singly-even. The same technique gives similar results for additive codes over GF(4) (relevant to quantum coding theory).
Using a variant of the linear programming method we derive a new upper bound on the minimum distance d of doubly-even self-dual codes of length n. Asymptotically, for n growing, it gives d/n/spl les/0.166315/spl middot//spl middot//spl middot/+o(1), thus improving on the Mallows-Odlyzko-Sloane bound of 1/6. To establish this, we prove that in any doubly even-self-dual code the distance distribution is asymptotically upper-bounded by the corresponding normalized binomial distribution in a certain interval.
The subcodes of binary self-dual codes whose length n between 22 and 30 and minimum distance six are studied by using of a random search algorithm,and the subcodes of dual distance 3,4,5 and 6 of these self-dual codes are constructed.The code chains of these self-orthogonal subcodes and the S-chains obtained from the dual of these self-orthogonal subcodes are also determined.According to Steane’s construction,some very good quantum codes of distance five and six are constructed by the obtained S-chains,and some of these quantum codes have improved parameters than previously known codes.
Assume that a binary linear code is transmitted over a channel with the symbol error probability p and that bounded distance decoding is used. In this case it is known [3] that for sufficiently small p the performance of the code is only a question of the weight distribution (weight enumerators of more efficient codes are lexicographically smaller). Based on this result we study the efficiency of extremal self-dual codes. Extremal doubly-even codes have unique weight enumerators for each length, and at first glance it may seem that these codes should perform worse than other codes with the same minimum distance. However we show that this is not always the case when comparing to singly-even codes. We also show that a doubly-even code may perform better than a non self-dual code. We find the most efficient codes among extremal singly-even codes of length 24m + 8 and 24m + 16. We also consider some families of extremal singly-even codes with uniquely determined weight enumerators (s-extremal codes, codes with minimal shadow). It appears that they always perform better than extremal doublyeven codes of the same length. The results are joint work with Wolfgang Willems (Magdeburg).
We prove that the quantum code distance is NP-hard to approximate within an additive error of cNc NcN, for some constant c>0c >0c>0, where NNN is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to Ω(N)Ω(N)Ω(N) and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical XXX- and ZZZ-check spaces, and with a constant rate and constant relative distance. For every fixed λ>1λ>1λ>1, there is a constant c>0c>0c>0 such that hardness still holds even when every nonidentity stabilizer has weight greater than λλλ times the quantum distance. We also improve the hardness gap of graph state distance on NNN vertices of Grigorescu, Jha, and Samperton from cube-root to Ω(N)Ω(N)Ω(N), resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most NNN. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2). Our main technique for both hardness bounds above is classical: we show how to convert any code CCC of length mmm into a self-dual code A(C)A(C)A(C) of length N=Θ(m)N=Θ(m)N=Θ(m) while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of CCC. It comes with a linear embedding τ:F2m↪F2Nτ: \mathbb F_2^m \hookrightarrow \mathbb F_2^Nτ:F2m​↪F2N​. The embedding doubles all Hamming distances between vectors in F2m\mathbb F_2^mF2m​ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of A(C)A(C)A(C) of weight at most 2m2m2m are exactly τ(C)τ(C)τ(C).
Additive code C over GF(4) of length n is an additive subgroup of GF(4)n. It is well known [4] that the problem of finding stabilizer quantum error-correcting codes is transformed into problem of finding additive self-orthogonal codes over the Galois field GF(4) under a trace inner product. Our purpose is to construct good additive self-dual codes of length 13 ≤ n ≤ 21. In this paper we classify all extremal (optimal) codes of lengths 13 and 14, and we construct many extremal codes of lengths 15 and 16. Also, we construct some new extremal codes of lengths 17,18,19, and 21. We give the current status of known extremal (optimal) additive self-dual codes of lengths 13 to 21.