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:2107.11286

The Diagonal Distance of CWS Codes

Upendra Kapshikar

Published Jul 23, 2021• 3 citations
arXivHTMLPDF

Abstract

Quantum degeneracy in error correction is a feature unique to quantum error correcting codes, unlike their classical counterpart. It allows a quantum error correcting code to correct errors even when they can not uniquely pinpoint the error. The diagonal distance of a quantum code is an important parameter that characterizes if the quantum code is degenerate or not. If code has a distance more than the diagonal distance, then it is degenerate, whereas if it is below the diagonal distance, then it is nondegenerate. We show that most of the CWS codes without a cycle of length four attain the upper bound of diagonal distance d+1, where d is the minimum vertex degree of the associated graph. Addressing the question of degeneracy, we give necessary conditions on CWS codes to be degenerate. We show that any degenerate CWS code with graph $G$ and classical code C will either have a short cycle in the graph $G$ or will be such that the classical code C has one of the coordinates trivially zero for all codewords.

DOI
10.48550/arxiv.2107.11286

Related papers

On the Hardness of the Minimum Distance Problem of Quantum Codes

Upendra Kapshikar, Srijita Kundu

We study the hardness of the problem of finding the distance of quantum error-correcting codes. The analogous problem for classical codes is known to be NP-hard, even in approximate form. For quantum codes, various problems related to decoding are known to be NP-hard, but the hardness of the distance problem has not been studied before. In this work, we show that finding the minimum distance of stabilizer quantum codes exactly or approximately is NP-hard. This result is obtained by reducing the classical minimum distance problem to the quantum problem, using the CWS framework for quantum codes, which constructs a quantum code using a classical code and a graph. A main technical tool used for our result is a lower bound on the so-called graph state distance of 4-cycle free graphs. In particular, we show that for a 4-cycle free graph$G$, its graph state distance is either$\delta $or$\delta +1$, where$\delta $is the minimum vertex degree of$G$. Due to a well-known reduction from stabilizer codes to CSS codes, our results also imply that finding the minimum distance of CSS codes is also NP-hard.

arXiv:2203.04262•IEEE Transactions on Information Theory•Jun 16, 2023•23 citations

On the Hardness of Approximating Distances of Quantum Codes

Elena Grigorescu, Jha, Vatsal, Eric Samperton

The problem of computing distances of error-correcting codes is fundamental in both the classical and quantum settings. While hardness for the classical version of these problems has been known for some time (in both the exact and approximate settings), it was only recently that Kapshikar and Kundu showed the hardness of these problems for non-degenerate quantum codes. As our first main result, we get a direct reduction to CSS codes, the most commonly used type of quantum code, from the minimum distance problem for classical linear codes. In particular, our proof uses arguably simpler constructions based on hypergraph product codes. Our second set of results considers the distance of a graph state, which is a key parameter for quantum codes obtained via the codeword stabilized formalism. We show that it is NP-hard to compute/approximate the distance of a graph state, which is a degenerate quantum code, when the adjacency matrix of the graph is the input. This establishes hardness for even degenerate quantum codes, which was not known before. Furthermore, we show this is true even if we only consider X-type errors of a graph state. Our techniques, moreover, imply an interesting classical consequence: the hardness of computing or approximating the distance of classical codes with rate equal to 1/2. One of the main motivations of the present work is a question raised by Kapshikar and Kundu concerning the NP-hardness of approximation when there is an additive error proportional to a quantum code's length. We show that no such hardness can hold for hypergraph product codes. These observations suggest the possibility of a new kind of square root barrier.

arXiv:2509.21469•Leibniz international proceedings in informatics•Jan 1, 2025•2 citations

Codeword stabilized quantum codes: Algorithm and structure

Isaac L. Chuang, Andrew W. Cross, Graeme Smith +2 more

The codeword stabilized (CWS) quantum code formalism presents a unifying approach to both additive and nonadditive quantum error-correcting codes [IEEE Trans. Inf. Theory 55, 433 (2009)]. This formalism reduces the problem of constructing such quantum codes to finding a binary classical code correcting an error pattern induced by a graph state. Finding such a classical code can be very difficult. Here, we consider an algorithm which maps the search for CWS codes to a problem of identifying maximum cliques in a graph. While solving this problem is in general very hard, we provide three structure theorems which reduce the search space, specifying certain admissible and optimal ((n,K,d)) additive codes. In particular, we find that the re does not exist any ((7,3,3)) CWS code though the linear programming bound does not rule it out. The complexity of the CWS-search algorithm is compared with the contrasting method introduced by Aggarwal and Calderbank [IEEE Trans. Inf. Theory 54, 1700 (2008)].

arXiv:0803.3232•Journal of Mathematical Physics•Apr 1, 2009•40 citations

A Hamming-Like Bound for Degenerate Stabilizer Codes

Andrew Nemec, Theerapat Tansuwannont

The quantum Hamming bound was originally put forward as an upper bound on the parameters of nondegenerate quantum codes, but over the past few decades much work has been done to show that many degenerate quantum codes must also obey this bound. In this paper, we show that there is a Hamming-like bound stricter than the quantum Hamming bound that applies to degenerate $t$-error-correcting stabilizer codes of length greater than some positive integer $N(t)$. We show that this bound holds for all single-error-correcting degenerate stabilizer codes, forcing all but a handful of optimal distance-3 stabilizer codes to be nondegenerate.

arXiv:2306.00048•May 31, 2023•5 citations

Symmetries of Codeword Stabilized Quantum Codes

Salman Beigi, Jianxin Chen, Markus Grassl +3 more

Symmetry is at the heart of coding theory. Codes with symmetry, especially cyclic codes, play an essential role in both theory and practical applications of classical error-correcting codes. Here we examine symmetry properties for codeword stabilized (CWS) quantum codes, which is the most general framework for constructing quantum error-correcting codes known to date. A CWS code Q can be represented by a self-dual additive code S and a classical code C, i.,e., Q=(S,C), however this representation is in general not unique. We show that for any CWS code Q with certain permutation symmetry, one can always find a self-dual additive code S with the same permutation symmetry as Q such that Q=(S,C). As many good CWS codes have been found by starting from a chosen S, this ensures that when trying to find CWS codes with certain permutation symmetry, the choice of S with the same symmetry will suffice. A key step for this result is a new canonical representation for CWS codes, which is given in terms of a unique decomposition as union stabilizer codes. For CWS codes, so far mainly the standard form (G,C) has been considered, where G is a graph state. We analyze the symmetry of the corresponding graph of G, which in general cannot possess the same permutation symmetry as Q. We show that it is indeed the case for the toric code on a square lattice with translational symmetry, even if its encoding graph can be chosen to be translational invariant.

arXiv:1303.7020•Leibniz international proceedings in informatics•Jan 1, 2013•4 citations

Nonbinary codeword-stabilized quantum codes

Xie Chen, Bei Zeng, Isaac L. Chuang

The codeword-stabilized (CWS) quantum code formalism presents a unifying approach to both additive and nonadditive quantum error-correcting codes [see A. Cross et al., e-print arXiv:0708.1021], but only for binary states. Here we generalize the CWS framework to the nonbinary case (of both prime and nonprime dimensions) and map the search for nonbinary quantum codes to a corresponding search problem for classical nonbinary codes with specific error patterns. We show that while the additivity properties of nonbinary CWS codes are similar to the binary case, the structural properties of the nonbinary codes differ substantially from the binary case, even for prime dimensions. In particular, we identify specific structure patterns of stabilizer groups, based on which efficient constructions might be possible for codes that encode more dimensions than any stabilizer codes of the same length and distance; similar methods cannot be applied in the binary case. Understanding of these structural properties can help prune the search space and facilitate the identification of good nonbinary CWS codes.

arXiv:0808.3086•Physical Review A•Dec 8, 2008•31 citations
Quantum degeneracy in error correction is a feature unique to quantum error correcting codes, unlike their classical counterpart. It allows a quantum error correcting code to correct errors even when they can not uniquely pinpoint the error. The diagonal distance of a quantum code is an important parameter that characterizes if the quantum code is degenerate or not. If code has a distance more than the diagonal distance, then it is degenerate, whereas if it is below the diagonal distance, then it is nondegenerate. We show that most of the CWS codes without a cycle of length four attain the upper bound of diagonal distance d+1, where d is the minimum vertex degree of the associated graph. Addressing the question of degeneracy, we give necessary conditions on CWS codes to be degenerate. We show that any degenerate CWS code with graph GGG and classical code C will either have a short cycle in the graph GGG or will be such that the classical code C has one of the coordinates trivially zero for all codewords.
We study the hardness of the problem of finding the distance of quantum error-correcting codes. The analogous problem for classical codes is known to be NP-hard, even in approximate form. For quantum codes, various problems related to decoding are known to be NP-hard, but the hardness of the distance problem has not been studied before. In this work, we show that finding the minimum distance of stabilizer quantum codes exactly or approximately is NP-hard. This result is obtained by reducing the classical minimum distance problem to the quantum problem, using the CWS framework for quantum codes, which constructs a quantum code using a classical code and a graph. A main technical tool used for our result is a lower bound on the so-called graph state distance of 4-cycle free graphs. In particular, we show that for a 4-cycle free graphGGG, its graph state distance is either$\delta ororor\delta +1,where, where,where\delta istheminimumvertexdegreeofis the minimum vertex degree ofistheminimumvertexdegreeofG$. Due to a well-known reduction from stabilizer codes to CSS codes, our results also imply that finding the minimum distance of CSS codes is also NP-hard.
The problem of computing distances of error-correcting codes is fundamental in both the classical and quantum settings. While hardness for the classical version of these problems has been known for some time (in both the exact and approximate settings), it was only recently that Kapshikar and Kundu showed the hardness of these problems for non-degenerate quantum codes. As our first main result, we get a direct reduction to CSS codes, the most commonly used type of quantum code, from the minimum distance problem for classical linear codes. In particular, our proof uses arguably simpler constructions based on hypergraph product codes. Our second set of results considers the distance of a graph state, which is a key parameter for quantum codes obtained via the codeword stabilized formalism. We show that it is NP-hard to compute/approximate the distance of a graph state, which is a degenerate quantum code, when the adjacency matrix of the graph is the input. This establishes hardness for even degenerate quantum codes, which was not known before. Furthermore, we show this is true even if we only consider X-type errors of a graph state. Our techniques, moreover, imply an interesting classical consequence: the hardness of computing or approximating the distance of classical codes with rate equal to 1/2. One of the main motivations of the present work is a question raised by Kapshikar and Kundu concerning the NP-hardness of approximation when there is an additive error proportional to a quantum code's length. We show that no such hardness can hold for hypergraph product codes. These observations suggest the possibility of a new kind of square root barrier.
The codeword stabilized (CWS) quantum code formalism presents a unifying approach to both additive and nonadditive quantum error-correcting codes [IEEE Trans. Inf. Theory 55, 433 (2009)]. This formalism reduces the problem of constructing such quantum codes to finding a binary classical code correcting an error pattern induced by a graph state. Finding such a classical code can be very difficult. Here, we consider an algorithm which maps the search for CWS codes to a problem of identifying maximum cliques in a graph. While solving this problem is in general very hard, we provide three structure theorems which reduce the search space, specifying certain admissible and optimal ((n,K,d)) additive codes. In particular, we find that the re does not exist any ((7,3,3)) CWS code though the linear programming bound does not rule it out. The complexity of the CWS-search algorithm is compared with the contrasting method introduced by Aggarwal and Calderbank [IEEE Trans. Inf. Theory 54, 1700 (2008)].
The quantum Hamming bound was originally put forward as an upper bound on the parameters of nondegenerate quantum codes, but over the past few decades much work has been done to show that many degenerate quantum codes must also obey this bound. In this paper, we show that there is a Hamming-like bound stricter than the quantum Hamming bound that applies to degenerate ttt-error-correcting stabilizer codes of length greater than some positive integer N(t)N(t)N(t). We show that this bound holds for all single-error-correcting degenerate stabilizer codes, forcing all but a handful of optimal distance-3 stabilizer codes to be nondegenerate.
Symmetry is at the heart of coding theory. Codes with symmetry, especially cyclic codes, play an essential role in both theory and practical applications of classical error-correcting codes. Here we examine symmetry properties for codeword stabilized (CWS) quantum codes, which is the most general framework for constructing quantum error-correcting codes known to date. A CWS code Q can be represented by a self-dual additive code S and a classical code C, i.,e., Q=(S,C), however this representation is in general not unique. We show that for any CWS code Q with certain permutation symmetry, one can always find a self-dual additive code S with the same permutation symmetry as Q such that Q=(S,C). As many good CWS codes have been found by starting from a chosen S, this ensures that when trying to find CWS codes with certain permutation symmetry, the choice of S with the same symmetry will suffice. A key step for this result is a new canonical representation for CWS codes, which is given in terms of a unique decomposition as union stabilizer codes. For CWS codes, so far mainly the standard form (G,C) has been considered, where G is a graph state. We analyze the symmetry of the corresponding graph of G, which in general cannot possess the same permutation symmetry as Q. We show that it is indeed the case for the toric code on a square lattice with translational symmetry, even if its encoding graph can be chosen to be translational invariant.
The codeword-stabilized (CWS) quantum code formalism presents a unifying approach to both additive and nonadditive quantum error-correcting codes [see A. Cross et al., e-print arXiv:0708.1021], but only for binary states. Here we generalize the CWS framework to the nonbinary case (of both prime and nonprime dimensions) and map the search for nonbinary quantum codes to a corresponding search problem for classical nonbinary codes with specific error patterns. We show that while the additivity properties of nonbinary CWS codes are similar to the binary case, the structural properties of the nonbinary codes differ substantially from the binary case, even for prime dimensions. In particular, we identify specific structure patterns of stabilizer groups, based on which efficient constructions might be possible for codes that encode more dimensions than any stabilizer codes of the same length and distance; similar methods cannot be applied in the binary case. Understanding of these structural properties can help prune the search space and facilitate the identification of good nonbinary CWS codes.