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:2607.15548 · Physical Review A

Quantum states supported by matroids

Xiaowei Huang, Fei Shi, Lijun Zhang, Lvzhou Li

quant-phSubmitted Jul 17, 2026• Announced Jul 20, 2026• 0 citations
arXivHTMLPDF

Abstract

In this work, we establish a structural correspondence between quantum states and matroid theory. This connection demonstrates that key properties of quantum states, including entanglement and measurement, can be characterized in purely combinatorial terms via matroids, despite the apparent conceptual distance between these two fields. Using this framework, we show that a matroid-supported state is genuinely entangled when its underlying matroid is connected. Moreover, a uniform superposition over all bases of a matroid is genuinely entangled if and only if the matroid is connected. We also demonstrate that a local measurement in the $Z$-basis on such a state yields another matroid-supported state, whose underlying matroid is a minor of the original one. Inspired by matroid duality, we further propose a notion of quantum state duality, uncovering a deep structural symmetry in state transformations.

Journal reference
Phys. Rev. A 113, 062452,2026
DOI
10.1103/mx1w-k8fg
Comments
This paper has been published in Physical Review A. Commements are welcome

Related papers

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

Correspondence between entangled states and entangled bases under local transformations

Florian Pimpel, Martin J. Renner, Armin Tavakoli

We investigate whether pure entangled states can be associated to a measurement basis in which all vectors are local unitary transformations of the original state. We prove that for bipartite states with a local dimension that is either 2, 4, or 8, every state corresponds to a basis. Via numerics, we strongly evidence the same conclusion for two qutrits and three qubits also. However, for some states of four qubits, we are unable to find a basis, leading us to conjecture that not all quantum states admit a corresponding measurement. Furthermore, we investigate whether there can exist a set of local unitaries that transform any state into a basis. While we show that such a state-independent construction cannot exist for general quantum states, we prove that it does exist for real-valued $n$-qubit states if and only if $n=2,3$, and that such constructions are impossible for any multipartite system of an odd local dimension. Our results suggest a rich relationship between entangled states and iso-entangled measurements with a strong dependence on both particle numbers and dimension.

arXiv:2301.13285•Physical Review A•Aug 25, 2023•11 citations

Quantum Matching Theory (with new complexity theoretic, combinatorial and topological insights on the nature of the Quantum Entanglement)

Gurvits, Leonid

Classical matching theory can be defined in terms of matrices with nonnegative entries. The notion of Positive operator, central in Quantum Theory, is a natural generalization of matrices with nonnegative entries. Based on this point of view, we introduce a definition of perfect Quantum (operator) matching . We show that the new notion inherits many "classical" properties, but not all of them . This new notion goes somewhere beyound matroids . For separable bipartite quantum states this new notion coinsides with the full rank property of the intersection of two corresponding geometric matroids . In the classical situation, permanents are naturally associated with perfects matchings. We introduce an analog of permanents for positive operators, called Quantum Permanent and show how this generalization of the permanent is related to the Quantum Entanglement. Besides many other things, Quantum Permanents provide new rational inequalities necessary for the separability of bipartite quantum states . Using Quantum Permanents, we give deterministic poly-time algorithm to solve Hidden Matroids Intersection Problem and indicate some "classical" complexity difficulties associated with the Quantum Entanglement. Finally, we prove that the weak membership problem for the convex set of separable bipartite density matrices is NP-HARD.

arXiv:quant-ph/0201022•Jan 7, 2002•28 citations

Quantum Matching Theory (with new complexity-theoretic, combinatorial and topical insights on the nature of the quantum entanglement)

Gurvits, L. (Leonid)

Classical matching theory can be defined in terms of matrices with nonnegative entries. The notion of Positive operator, central in Quantum Theory, is a natural generalization of matrices with non-negative entries. Based on this point of view, we introduce a definition of perfect Quantum (operator) matching. We show that the new notion inherits many 'classical' properties, but not all of them. This new notion goes somewhere beyound matroids. For separable bipartite quantum states this new notion coinsides with the full rank property of the intersection of two corresponding geometric matroids. In the classical situation, permanents are naturally associated with perfects matchings. We introduce an analog of permanents for positive operators, called Quantum Permanent and show how this generalization of the permanent is related to the Quantum Entanglement. Besides many other things, Quantum Permanents provide new rational inequalities necessary for the separability of bipartite quantum states. Using Quantum Permanents, we give deterministic poly-time algorithm to solve Hidden Matroids Intersection Problem and indicate some 'classical' complexity difficulties associated with the Quantum Entanglement. Finally, we prove that the weak membership problem for the convex set of separable bipartite density matrices is NP-HARD.

•Jan 1, 2002•0 citations

A Boolean Functions Theoretic Approach to Quantum Hypergraph States and Entanglement

Supriyo Dutta

The hypergraph states are pure multipartite quantum states corresponding to a hypergraph. It is an equal superposition of the states belonging to the computational basis. Given any hypergraph, we can construct a hypergraph state determined by a Boolean function. In contrast, we can find a hypergraph, corresponding to a Boolean function. This investigation develops a number of combinatorial structures concerned with the hypergraph states. For instance, the elements of the computational basis generate a lattice. The chains and antichains in this lattice assist us to find the equation of the Boolean function explicitly as well as to find a hypergraph. In addition, we investigate the entanglement property of the hypergraph states in terms of their combinatorial structures. We demonstrate several classes of hypergraphs, such that every cut of equal length on the corresponding hypergraph states has an equal amount of entanglement.

arXiv:1811.00308•Nov 1, 2018•6 citations

What are local complementations, really?

Kenneth Goodenough

A local complementation at a vertex $v$ of a graph $G$ replaces the induced neighborhood of $v$ with its complement. Local complementations are, at face value, peculiar operations. Yet they famously show up when describing the local Clifford equivalence among graph states, and, because of this, have become a fundamental notion in the study of graph states. Following Bouchet, we show here how local complementations on graphs are more naturally thought of in terms of switchings of (matroid) bases of stabilizer states. Bases and switchings reveal structural properties of stabilizer states that are harder to glean from the graph-theoretic description alone, such as vertex-minors and statistics of local Pauli measurements. Bases also simplify prior proofs about graphs up to local complementations, of which we give several examples. Bases are foundational in the study of (multi)matroids; as such this paper serves as a gentle introduction to the applications of multimatroids to quantum information theory.

arXiv:2611.08620•Nov 5, 2026•0 citations
In this work, we establish a structural correspondence between quantum states and matroid theory. This connection demonstrates that key properties of quantum states, including entanglement and measurement, can be characterized in purely combinatorial terms via matroids, despite the apparent conceptual distance between these two fields. Using this framework, we show that a matroid-supported state is genuinely entangled when its underlying matroid is connected. Moreover, a uniform superposition over all bases of a matroid is genuinely entangled if and only if the matroid is connected. We also demonstrate that a local measurement in the ZZZ-basis on such a state yields another matroid-supported state, whose underlying matroid is a minor of the original one. Inspired by matroid duality, we further propose a notion of quantum state duality, uncovering a deep structural symmetry in state transformations.
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.
We investigate whether pure entangled states can be associated to a measurement basis in which all vectors are local unitary transformations of the original state. We prove that for bipartite states with a local dimension that is either 2, 4, or 8, every state corresponds to a basis. Via numerics, we strongly evidence the same conclusion for two qutrits and three qubits also. However, for some states of four qubits, we are unable to find a basis, leading us to conjecture that not all quantum states admit a corresponding measurement. Furthermore, we investigate whether there can exist a set of local unitaries that transform any state into a basis. While we show that such a state-independent construction cannot exist for general quantum states, we prove that it does exist for real-valued nnn-qubit states if and only if n=2,3n=2,3n=2,3, and that such constructions are impossible for any multipartite system of an odd local dimension. Our results suggest a rich relationship between entangled states and iso-entangled measurements with a strong dependence on both particle numbers and dimension.
Classical matching theory can be defined in terms of matrices with nonnegative entries. The notion of Positive operator, central in Quantum Theory, is a natural generalization of matrices with nonnegative entries. Based on this point of view, we introduce a definition of perfect Quantum (operator) matching . We show that the new notion inherits many "classical" properties, but not all of them . This new notion goes somewhere beyound matroids . For separable bipartite quantum states this new notion coinsides with the full rank property of the intersection of two corresponding geometric matroids . In the classical situation, permanents are naturally associated with perfects matchings. We introduce an analog of permanents for positive operators, called Quantum Permanent and show how this generalization of the permanent is related to the Quantum Entanglement. Besides many other things, Quantum Permanents provide new rational inequalities necessary for the separability of bipartite quantum states . Using Quantum Permanents, we give deterministic poly-time algorithm to solve Hidden Matroids Intersection Problem and indicate some "classical" complexity difficulties associated with the Quantum Entanglement. Finally, we prove that the weak membership problem for the convex set of separable bipartite density matrices is NP-HARD.
Classical matching theory can be defined in terms of matrices with nonnegative entries. The notion of Positive operator, central in Quantum Theory, is a natural generalization of matrices with non-negative entries. Based on this point of view, we introduce a definition of perfect Quantum (operator) matching. We show that the new notion inherits many 'classical' properties, but not all of them. This new notion goes somewhere beyound matroids. For separable bipartite quantum states this new notion coinsides with the full rank property of the intersection of two corresponding geometric matroids. In the classical situation, permanents are naturally associated with perfects matchings. We introduce an analog of permanents for positive operators, called Quantum Permanent and show how this generalization of the permanent is related to the Quantum Entanglement. Besides many other things, Quantum Permanents provide new rational inequalities necessary for the separability of bipartite quantum states. Using Quantum Permanents, we give deterministic poly-time algorithm to solve Hidden Matroids Intersection Problem and indicate some 'classical' complexity difficulties associated with the Quantum Entanglement. Finally, we prove that the weak membership problem for the convex set of separable bipartite density matrices is NP-HARD.
The hypergraph states are pure multipartite quantum states corresponding to a hypergraph. It is an equal superposition of the states belonging to the computational basis. Given any hypergraph, we can construct a hypergraph state determined by a Boolean function. In contrast, we can find a hypergraph, corresponding to a Boolean function. This investigation develops a number of combinatorial structures concerned with the hypergraph states. For instance, the elements of the computational basis generate a lattice. The chains and antichains in this lattice assist us to find the equation of the Boolean function explicitly as well as to find a hypergraph. In addition, we investigate the entanglement property of the hypergraph states in terms of their combinatorial structures. We demonstrate several classes of hypergraphs, such that every cut of equal length on the corresponding hypergraph states has an equal amount of entanglement.
A local complementation at a vertex vvv of a graph GGG replaces the induced neighborhood of vvv with its complement. Local complementations are, at face value, peculiar operations. Yet they famously show up when describing the local Clifford equivalence among graph states, and, because of this, have become a fundamental notion in the study of graph states. Following Bouchet, we show here how local complementations on graphs are more naturally thought of in terms of switchings of (matroid) bases of stabilizer states. Bases and switchings reveal structural properties of stabilizer states that are harder to glean from the graph-theoretic description alone, such as vertex-minors and statistics of local Pauli measurements. Bases also simplify prior proofs about graphs up to local complementations, of which we give several examples. Bases are foundational in the study of (multi)matroids; as such this paper serves as a gentle introduction to the applications of multimatroids to quantum information theory.