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:1104.1171 · IEEE International Symposium on Information Theory (ISIT)

Quantum codes and symplectic matroids

Pradeep Kiran Sarvepalli

Published Jun 1, 2014• 2 citations
arXivHTMLPDF

Abstract

The correspondence between linear codes and representable matroids is well known. But a similar correspondence between quantum codes and matroids is not known. We show that representable symplectic matroids over a finite field Fqcorrespond to Fq-linear quantum codes. This connection is straightforward but it does not appear to have been made earlier in literature. This correspondence is made through isotropic subspaces. We show that Calderbank-Shor-Steane (CSS) codes correspond to homogenous symplectic matroids while graph states, which figure so prominently in measurement based quantum computation, correspond to a special class of symplectic matroids, namely Lagrangian matroids. This association is useful in that it enables the study of symplectic matroids in terms of quantum codes and vice versa. Furthermore, it has application in the study of quantum secret sharing schemes.

DOI
10.1109/isit.2014.6874998

Related papers

New Methods for Constructing Classical and Quantum Codes from Graphs and Matroids

Anderson S. Barbosa, Franklin de L. Marquezino, Giuliano G. La Guardia

In this paper, we present a method for constructing linear codes derived from book graphs. Applying such a method, we construct binary codes that have the greatest possible minimum distance for their length and dimension by means of the $2$-sum of two equal book graphs. We then utilize matroid and graph theory together to investigate some properties of the resulting linear codes. Furthermore, we show that, from the incidence matrix of any graph, we can obtain a linear code over any finite field maintaining the same parameters. Furthermore, we show how the condition for two linear codes to generate a Calderbank-Shor-Steane (CSS) code translates into matroid theory and, utilizing cycle graphs, we exhibit a way to generate codes that meet this condition.

cs.DMCross-listedarXiv:2610.04617•Oct 6, 2026•0 citations

Nonbinary quantum codes

Eric M. Rains

We present several results on quantum codes over general alphabets (that is, in which the fundamental units may have more than two states). In particular, we consider codes derived from finite symplectic geometry assumed to have additional global symmetries. From this standpoint, the analogs of Calderbank-Shor-Steane codes and of GF(4)-linear codes turn out to be special cases of the same construction. This allows us to construct families of quantum codes from certain codes over number fields; in particular, we get analogs of quadratic residue codes, including a single-error-correcting code encoding one letter in five, for any alphabet size. We also consider the problem of fault-tolerant computation through such codes, generalizing ideas of Gottesman (see Phys. Rev. A, vol.57, no.1, p127-37, 1998).

arXiv:quant-ph/9703048•IEEE Transactions on Information Theory•Jan 1, 1999•383 citations

Matroids and quantum-secret-sharing schemes

Pradeep Kiran Sarvepalli, Robert Raussendorf

A secret-sharing scheme is a cryptographic protocol to distribute a secret state in an encoded form among a group of players such that only authorized subsets of the players can reconstruct the secret. Classically, efficient secret-sharing schemes have been shown to be induced by matroids. Furthermore, access structures of such schemes can be characterized by an excluded minor relation. No such relations are known for quantum secret-sharing schemes. In this paper we take the first steps toward a matroidal characterization of quantum-secret-sharing schemes. In addition to providing a new perspective on quantum-secret-sharing schemes, this characterization has important benefits. While previous work has shown how to construct quantum-secret-sharing schemes for general access structures, these schemes are not claimed to be efficient. In this context the present results prove to be useful; they enable us to construct efficient quantum-secret-sharing schemes for many general access structures. More precisely, we show that an identically self-dual matroid that is representable over a finite field induces a pure-state quantum-secret-sharing scheme with information rate $1$.

arXiv:0909.0549•Physical Review A•May 24, 2010•33 citations

Encoding matroids into quantum states

Nathan Ferreira, Alison A. Silva, Giuliano G. La Guardia +1 more

Efficient representations of multipartite quantum states play a fundamental role in quantum information theory, providing both conceptual insight and practical tools for characterizing entanglement. Motivated by the axiomatic framework for graph states [Phys. Rev. A 85, 062313 (2012)] and its subsequent extension to hypergraph states [Phys. Rev. A 87, 022311 (2013)], we introduce an axiomatic construction of \emph{matroid states}, a new family of multipartite quantum states associated with matroids. Our constructions are based on a set of axioms analogous to those that define graph and hypergraph states, yielding a consistent quantum representation of arbitrary matroids. Two ways of constructing matroid states are proposed: the first is defined in terms of circuits, and the second in terms of independent sets. In both approaches, we establish the existence of universal global operators that satisfy desirable properties such as locality, symmetry, commutativity, and are associated with the combinatorial structure of matroids. Furthermore, we establish a hierarchy connecting graph, matroid, and hypergraph states within a unified framework. Additionally, we show how to obtain an arbitrary graph state by applying suitable families of matroid states, whose corresponding operators are the generators of the stabilizer subgroup of the graph state. These results identify matroid theory as a natural combinatorial language for the efficient description of multipartite quantum states and open new perspectives for the investigation of quantum entanglement and related combinatorial structures.

quant-pharXiv:2607.02736•Jul 6, 2026•0 citations

Local equivalence, surface-code states, and matroids

Pradeep Kiran Sarvepalli, Robert Raussendorf

Recently, Ji et al. disproved the local-unitary--local Clifford (LU-LC) conjecture and showed that the local unitary (LU) and local Clifford (LC) equivalence classes of the stabilizer states are not always the same. Despite the fact that this settles the LU-LC conjecture, a sufficient condition for stabilizer states that violate the LU-LC conjecture is not known. In this paper, we investigate further the properties of stabilizer states with respect to local equivalence. Our first result shows that there exist infinitely many stabilizer states that violate the LU-LC conjecture. In particular, we show that for all numbers of qubits $n\ensuremath{\geqslant}28$, there exist distance-two stabilizer states which are counterexamples to the LU-LC conjecture. We prove that, for all odd $n\ensuremath{\geqslant}195$, there exist stabilizer states with distance greater than two that are LU equivalent but not LC equivalent. Two important classes of stabilizer states that are of great interest in quantum computation are the cluster states and stabilizer states of the surface codes. We show that, under some minimal restrictions, both these classes of states preclude any counterexamples. In this context, we also show that the associated surface codes do not have any encoded non-Clifford transversal gates. We characterize the Calderbank-Shor-Steane (CSS) surface-code states in terms of a class of minor closed binary matroids. In addition to making a connection to an important open problem in binary matroid theory, this characterization does in some cases provide an efficient test for CSS states that are not counterexamples.

arXiv:0911.1571•Physical Review A•Aug 5, 2010•11 citations

Sharing classical secrets with Calderbank-Shor-Steane codes

Pradeep Kiran Sarvepalli, Andreas Klappenecker

In this paper we investigate the use of quantum information to share classical secrets. While every quantum secret sharing scheme is a quantum error-correcting code, the converse is not true. Motivated by this we sought to find quantum codes which can be converted to secret sharing schemes. If we are interested in sharing classical secrets using quantum information, then we show that a class of pure ${[[n,1,d]]}_{q}$ Calderbank-Shor-Steane (CSS) codes can be converted to perfect secret sharing schemes. These secret sharing schemes are perfect in the sense that the unauthorized parties do not learn anything about the secret. Gottesman had given conditions to test whether a given subset is an authorized or unauthorized set; they enable us to determine the access structure of quantum secret sharing schemes. For the secret sharing schemes proposed in this paper the access structure can be characterized in terms of minimal codewords of the classical code underlying the CSS code. This characterization of the access structure for quantum secret sharing schemes is thought to be notable.

arXiv:0905.1661•Physical Review A•Aug 18, 2009•43 citations
The correspondence between linear codes and representable matroids is well known. But a similar correspondence between quantum codes and matroids is not known. We show that representable symplectic matroids over a finite field Fqcorrespond to Fq-linear quantum codes. This connection is straightforward but it does not appear to have been made earlier in literature. This correspondence is made through isotropic subspaces. We show that Calderbank-Shor-Steane (CSS) codes correspond to homogenous symplectic matroids while graph states, which figure so prominently in measurement based quantum computation, correspond to a special class of symplectic matroids, namely Lagrangian matroids. This association is useful in that it enables the study of symplectic matroids in terms of quantum codes and vice versa. Furthermore, it has application in the study of quantum secret sharing schemes.
In this paper, we present a method for constructing linear codes derived from book graphs. Applying such a method, we construct binary codes that have the greatest possible minimum distance for their length and dimension by means of the 222-sum of two equal book graphs. We then utilize matroid and graph theory together to investigate some properties of the resulting linear codes. Furthermore, we show that, from the incidence matrix of any graph, we can obtain a linear code over any finite field maintaining the same parameters. Furthermore, we show how the condition for two linear codes to generate a Calderbank-Shor-Steane (CSS) code translates into matroid theory and, utilizing cycle graphs, we exhibit a way to generate codes that meet this condition.
We present several results on quantum codes over general alphabets (that is, in which the fundamental units may have more than two states). In particular, we consider codes derived from finite symplectic geometry assumed to have additional global symmetries. From this standpoint, the analogs of Calderbank-Shor-Steane codes and of GF(4)-linear codes turn out to be special cases of the same construction. This allows us to construct families of quantum codes from certain codes over number fields; in particular, we get analogs of quadratic residue codes, including a single-error-correcting code encoding one letter in five, for any alphabet size. We also consider the problem of fault-tolerant computation through such codes, generalizing ideas of Gottesman (see Phys. Rev. A, vol.57, no.1, p127-37, 1998).
A secret-sharing scheme is a cryptographic protocol to distribute a secret state in an encoded form among a group of players such that only authorized subsets of the players can reconstruct the secret. Classically, efficient secret-sharing schemes have been shown to be induced by matroids. Furthermore, access structures of such schemes can be characterized by an excluded minor relation. No such relations are known for quantum secret-sharing schemes. In this paper we take the first steps toward a matroidal characterization of quantum-secret-sharing schemes. In addition to providing a new perspective on quantum-secret-sharing schemes, this characterization has important benefits. While previous work has shown how to construct quantum-secret-sharing schemes for general access structures, these schemes are not claimed to be efficient. In this context the present results prove to be useful; they enable us to construct efficient quantum-secret-sharing schemes for many general access structures. More precisely, we show that an identically self-dual matroid that is representable over a finite field induces a pure-state quantum-secret-sharing scheme with information rate 111.
Efficient representations of multipartite quantum states play a fundamental role in quantum information theory, providing both conceptual insight and practical tools for characterizing entanglement. Motivated by the axiomatic framework for graph states [Phys. Rev. A 85, 062313 (2012)] and its subsequent extension to hypergraph states [Phys. Rev. A 87, 022311 (2013)], we introduce an axiomatic construction of \emph{matroid states}, a new family of multipartite quantum states associated with matroids. Our constructions are based on a set of axioms analogous to those that define graph and hypergraph states, yielding a consistent quantum representation of arbitrary matroids. Two ways of constructing matroid states are proposed: the first is defined in terms of circuits, and the second in terms of independent sets. In both approaches, we establish the existence of universal global operators that satisfy desirable properties such as locality, symmetry, commutativity, and are associated with the combinatorial structure of matroids. Furthermore, we establish a hierarchy connecting graph, matroid, and hypergraph states within a unified framework. Additionally, we show how to obtain an arbitrary graph state by applying suitable families of matroid states, whose corresponding operators are the generators of the stabilizer subgroup of the graph state. These results identify matroid theory as a natural combinatorial language for the efficient description of multipartite quantum states and open new perspectives for the investigation of quantum entanglement and related combinatorial structures.
Recently, Ji et al. disproved the local-unitary--local Clifford (LU-LC) conjecture and showed that the local unitary (LU) and local Clifford (LC) equivalence classes of the stabilizer states are not always the same. Despite the fact that this settles the LU-LC conjecture, a sufficient condition for stabilizer states that violate the LU-LC conjecture is not known. In this paper, we investigate further the properties of stabilizer states with respect to local equivalence. Our first result shows that there exist infinitely many stabilizer states that violate the LU-LC conjecture. In particular, we show that for all numbers of qubits $n\ensuremath{\geqslant}28$, there exist distance-two stabilizer states which are counterexamples to the LU-LC conjecture. We prove that, for all odd $n\ensuremath{\geqslant}195$, there exist stabilizer states with distance greater than two that are LU equivalent but not LC equivalent. Two important classes of stabilizer states that are of great interest in quantum computation are the cluster states and stabilizer states of the surface codes. We show that, under some minimal restrictions, both these classes of states preclude any counterexamples. In this context, we also show that the associated surface codes do not have any encoded non-Clifford transversal gates. We characterize the Calderbank-Shor-Steane (CSS) surface-code states in terms of a class of minor closed binary matroids. In addition to making a connection to an important open problem in binary matroid theory, this characterization does in some cases provide an efficient test for CSS states that are not counterexamples.
In this paper we investigate the use of quantum information to share classical secrets. While every quantum secret sharing scheme is a quantum error-correcting code, the converse is not true. Motivated by this we sought to find quantum codes which can be converted to secret sharing schemes. If we are interested in sharing classical secrets using quantum information, then we show that a class of pure [[n,1,d]]q{[[n,1,d]]}_{q}[[n,1,d]]q​ Calderbank-Shor-Steane (CSS) codes can be converted to perfect secret sharing schemes. These secret sharing schemes are perfect in the sense that the unauthorized parties do not learn anything about the secret. Gottesman had given conditions to test whether a given subset is an authorized or unauthorized set; they enable us to determine the access structure of quantum secret sharing schemes. For the secret sharing schemes proposed in this paper the access structure can be characterized in terms of minimal codewords of the classical code underlying the CSS code. This characterization of the access structure for quantum secret sharing schemes is thought to be notable.