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

arXiv:1308.3578 · IEEE International Symposium on Information Theory (ISIT)

Quantum Gilbert-Varshamov bound through symplectic self-orthogonal codes

Lingfei Jin, Chaoping Xing

Published Jul 1, 2011• 16 citations
arXivHTMLPDF

Abstract

It is well known that quantum codes can be constructed through classical symplectic self-orthogonal codes. In this paper, we give a kind of Gilbert-Varshamov bound for symplectic self-orthogonal codes first and then obtain the Gilbert-Varshamov bound for quantum codes. The idea of obtaining the Gilbert-Varshamov bound for symplectic self-orthogonal codes follows from counting arguments.

DOI
10.1109/isit.2011.6034167

Related papers

A Varshamov-Gilbert bound for a class of formally self-dual codes and related quantum codes

Vladimir D. Tonchev

It is proved that a class of q-ary (2n,n) formally self-dual codes obtained from symmetric matrices over GF (q), contains codes that meet the Varshamov-Gilbert bound. The codes are self-dual with respect to the symplectic inner product and yield quantum codes encoding one state with n q-ary qubits and having minimum distance proportional to n.

IEEE Transactions on Information Theory•Apr 1, 2002•2 citations

Improvement of the Gilbert-Varshamov Bound for Linear Codes and Quantum Codes

Chen Yuan, Ruiqi Zhu

The Gilbert--Varshamov (GV) bound is a central benchmark in coding theory, establishing existential guarantees for error-correcting codes and serving as a baseline for both Hamming and quantum fault-tolerant information processing. Despite decades of effort, improving the GV bound is notoriously difficult, and known improvements often rely on technically heavy arguments and do not extend naturally to the quantum setting due to additional self-orthogonality constraints. In this work we develop a concise probabilistic method that yields an improvement over the classical GV bound for $q$-ary linear codes. For relative distance $δ=d/n<1-1/q$, we show that an $[n,k,d]_q$ linear code exists whenever $\frac{q^{k}-1}{q-1}\;<\;\frac{c_δ\sqrt{n}\, q^{n}}{\mathrm{Vol}_q(n,d-1)}$, for positive constant $c_δ$ depending only on $δ$, where $\mathrm{Vol}_q(n,d-1)$ denotes the volume of a $q$-ary Hamming ball. We further adapt this approach to the quantum setting by analyzing symplectic self-orthogonal structures. For $δ<1-1/q^2$, we obtain an improved quantum GV bound: there exists a $q$-ary quantum code $[[n,\,n-k,\,d]]$ provided that $\frac{q^{2n-k}-1}{q-1}<\frac{c_δ\sqrt{n}\cdot q^{2n}}{\sum_{i=0}^{d-1}\binom{n}{i}(q^2-1)^i}$. In particular, our result improves the standard quantum GV bound by an $Ω(\sqrt{n})$ multiplicative factor.

arXiv:2601.18590•Jan 26, 2026•0 citations

A Finite Gilbert–Varshamov Bound for Pure Stabilizer Quantum Codes

Kai Feng, Zhi Ma

A finite Gilbert-Varshamov (GV) bound for pure stabilizer (binary and nonbinary) quantum error correcting codes is presented in analogy to the GV bound for classical codes by using several enumerative results in finite unitary geometry. From this quantum GV bound we obtain several new binary quantum codes in a nonconstructive way having better parameters than the known codes.

IEEE Transactions on Information Theory•Nov 30, 2004•110 citations

Quantum self-dual codes and symmetric matrices

Vladimir D. Tonchev

This paper has been withdrawn since a Gilbert-Varshamov bound for general quantum codes has already appeared in Ekert and Macchiavello, Prys. Rev. Lett. 77, p. 2585, and a Gilbert-Varshamov bound for stabilizer codes connected with orthogonal geometry, or equivalently, with symmetric matrices as in this paper, has been proved by Calredbank, Rains, Shor and Sloane, Phys. Rev. Lett. 78, p. 405. I would like to thank Robert Calderbank for pointing out these references to me.

arXiv:quant-ph/9711047•Nov 20, 1997•0 citations

On the List-Decodability of Random Self-Orthogonal Codes

Lingfei Jin, Chaoping Xing, Xiande Zhang

Guruswami et al. showed that the list-decodability of random linear codes is as good as that of general random codes. In this paper, we further strengthen the result by showing that the list-decodability of random Euclidean self-orthogonal codes is as good as that of general random codes as well, i.e., achieves the classical Gilbert-Varshamov bound. In particular, we show that, for any fixed finite field Fq, error fraction δ ∈ (0,1 - 1/q) satisfying 1 - Hq(δ) ≤ 1/2, and small ε > 0, with high probability a random Euclidean self-orthogonal code over Fqof rate 1 - Hq(δ) - ε is (δ, O(1/ε))-list-decodable. This generalizes the result of linear codes to Euclidean self-orthogonal codes. In addition, we extend the result to list decoding symplectic dual-containing codes by showing that the list-decodability of random symplectic dual-containing codes achieves the quantum Gilbert-Varshamov bound as well. This implies that list-decodability of quantum stabilizer codes can achieve the quantum Gilbert-Varshamov bound. The counting argument on self-orthogonal codes is an important ingredient to prove our result.

arXiv:1611.06673•IEEE Transactions on Information Theory•Oct 3, 2014•4 citations

Symmetric matrices and quantum codes

Vladimir D. Tonchev

This paper has been withdrawn since a Gilbert-Varshamov bound for general quantum codes has already appeared in Ekert and Macchiavello, Prys. Rev. Lett. 77, p. 2585, and a Gilbert-Varshamov bound for stabilizer codes connected with orthogonal geometry, or equivalently, with symmetric matrices as in this paper, has been proved by Calredbank, Rains, Shor and Sloane, Phys. Rev. Lett. 78, p. 405. I would like to thank Robert Calderbank for pointing out these references to me.

arXiv:alg-geom/9711026•Nov 20, 1997•0 citations
It is well known that quantum codes can be constructed through classical symplectic self-orthogonal codes. In this paper, we give a kind of Gilbert-Varshamov bound for symplectic self-orthogonal codes first and then obtain the Gilbert-Varshamov bound for quantum codes. The idea of obtaining the Gilbert-Varshamov bound for symplectic self-orthogonal codes follows from counting arguments.
The Gilbert--Varshamov (GV) bound is a central benchmark in coding theory, establishing existential guarantees for error-correcting codes and serving as a baseline for both Hamming and quantum fault-tolerant information processing. Despite decades of effort, improving the GV bound is notoriously difficult, and known improvements often rely on technically heavy arguments and do not extend naturally to the quantum setting due to additional self-orthogonality constraints. In this work we develop a concise probabilistic method that yields an improvement over the classical GV bound for qqq-ary linear codes. For relative distance δ=d/n<1−1/qδ=d/n<1-1/qδ=d/n<1−1/q, we show that an [n,k,d]q[n,k,d]_q[n,k,d]q​ linear code exists whenever qk−1q−1  <  cδn qnVolq(n,d−1)\frac{q^{k}-1}{q-1}\;<\;\frac{c_δ\sqrt{n}\, q^{n}}{\mathrm{Vol}_q(n,d-1)}q−1qk−1​<Volq​(n,d−1)cδ​n​qn​, for positive constant cδc_δcδ​ depending only on δδδ, where Volq(n,d−1)\mathrm{Vol}_q(n,d-1)Volq​(n,d−1) denotes the volume of a qqq-ary Hamming ball. We further adapt this approach to the quantum setting by analyzing symplectic self-orthogonal structures. For δ<1−1/q2δ<1-1/q^2δ<1−1/q2, we obtain an improved quantum GV bound: there exists a qqq-ary quantum code [[n, n−k, d]][[n,\,n-k,\,d]][[n,n−k,d]] provided that q2n−k−1q−1<cδn⋅q2n∑i=0d−1(ni)(q2−1)i\frac{q^{2n-k}-1}{q-1}<\frac{c_δ\sqrt{n}\cdot q^{2n}}{\sum_{i=0}^{d-1}\binom{n}{i}(q^2-1)^i}q−1q2n−k−1​<∑i=0d−1​(in​)(q2−1)icδ​n​⋅q2n​. In particular, our result improves the standard quantum GV bound by an Ω(n)Ω(\sqrt{n})Ω(n​) multiplicative factor.
Guruswami et al. showed that the list-decodability of random linear codes is as good as that of general random codes. In this paper, we further strengthen the result by showing that the list-decodability of random Euclidean self-orthogonal codes is as good as that of general random codes as well, i.e., achieves the classical Gilbert-Varshamov bound. In particular, we show that, for any fixed finite field Fq, error fraction δ ∈ (0,1 - 1/q) satisfying 1 - Hq(δ) ≤ 1/2, and small ε > 0, with high probability a random Euclidean self-orthogonal code over Fqof rate 1 - Hq(δ) - ε is (δ, O(1/ε))-list-decodable. This generalizes the result of linear codes to Euclidean self-orthogonal codes. In addition, we extend the result to list decoding symplectic dual-containing codes by showing that the list-decodability of random symplectic dual-containing codes achieves the quantum Gilbert-Varshamov bound as well. This implies that list-decodability of quantum stabilizer codes can achieve the quantum Gilbert-Varshamov bound. The counting argument on self-orthogonal codes is an important ingredient to prove our result.