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

Matroid isomorphism games

Daniel Corey, Simon Schmidt, Marcel Wack

We define and study a collection of matroid isomorphism games corresponding to various axiomatic characterizations of matroids. These are nonlocal games played between two cooperative players. Each game is played on two matroids, and the matroids are isomorphic if and only if the game has a perfect classical winning strategy. We define notions of quantum isomorphism in terms of perfect quantum commuting strategies, and we find a pair of nonisomorphic matroids that are quantum isomorphic. We also give a purely algebraic characterization of quantum isomorphic matroids. Finally, we use this notion of quantum isomorphism to describe a new type of quantum automorphism group of a matroid and derive a sufficient condition for a matroid to have nonclassical quantum automorphism.

arXiv:2507.06225•Jul 8, 2025•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•9 citations

A De Bruijn Graph Formulation of Quantum Entanglement

Arturo Tozzi

Quantum entanglement is commonly characterized through global state descriptions on tensor product spaces, correlation measures or algebraic constructions, while local consistency constraints play no explicit structural role. We formulate entanglement as a combinatorial structure of overlapping local descriptions, drawing on De Bruijn graphs, where nodes represent overlapping contexts and paths encode globally coherent assemblies. We construct a graph whose nodes represent reduced quantum states on subsystems of fixed size and whose edges encode admissible extensions consistent with quantum mechanical compatibility conditions. Global many body states correspond to paths on this graph, while entanglement is reinterpreted as a property of graph connectivity and path multiplicity, rather than as a standalone numerical quantity. This formalism allows a separation between constraints imposed purely by local quantum consistency and additional structure introduced by dynamics, symmetries or boundary conditions, also clarifying how large-scale structural features may arise from local compatibility alone. Our graph-based formulation provides several advantages over conventional approaches. Supporting a unified treatment of static entanglement structure and dynamical evolution, it incorporates finite order locality and memory effects. Entanglement growth can be interpreted as path proliferation, while decoherence and noise correspond to the removal of admissible transitions. Our approach leads to testable hypotheses concerning the scaling of admissible state extensions, the robustness of entangled structures under local perturbations and the emergence of effective geometry from overlap constraints. Potential future directions include applications to many body reconstruction problems and comparative analysis of different classes of quantum states within a single combinatorial language.

•Jan 5, 2026•0 citations

Almost all graphs are vertex-minor universal

Ruben Ascoli, Bryce Frederickson, Sarah Frederickson +2 more

Answering a question of Claudet, we prove that the uniformly random graph $G\sim \mathbb G(n, 1/2)$ is $Ω(\sqrt n)$-vertex-minor universal with high probability. That is, for some constant $α\approx 0.911$, any graph on any $α\sqrt n$ specified vertices of $G$ can be obtained as a vertex-minor of $G$. This has direct implications for quantum communications networks: an $n$-vertex $k$-vertex-minor universal graph corresponds to an $n$-qubit $k$-stabilizer universal graph state, which has the property that one can induce any stabilizer state on any $k$ qubits using only local operations and classical communications. We further employ our methods in two other contexts. We obtain a bipartite pivot-minor version of our main result, and we use it to derive a universality statement for minors in random binary matroids. We also introduce the vertex-minor Ramsey number $R_{\mathrm{vm}}(k)$ to be the smallest value $n$ such that every $n$-vertex graph contains an independent set of size $k$ as a vertex-minor. Supported by our main result, we conjecture that $R_{\mathrm{vm}}(k)$ is polynomial in $k$. We prove $Ω(k^2) \leq R_{\mathrm{vm}}(k) \leq 2^k - 1$.

quant-pharXiv:2602.09049•Feb 10, 2026

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•4 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 define and study a collection of matroid isomorphism games corresponding to various axiomatic characterizations of matroids. These are nonlocal games played between two cooperative players. Each game is played on two matroids, and the matroids are isomorphic if and only if the game has a perfect classical winning strategy. We define notions of quantum isomorphism in terms of perfect quantum commuting strategies, and we find a pair of nonisomorphic matroids that are quantum isomorphic. We also give a purely algebraic characterization of quantum isomorphic matroids. Finally, we use this notion of quantum isomorphism to describe a new type of quantum automorphism group of a matroid and derive a sufficient condition for a matroid to have nonclassical quantum automorphism.
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.
Quantum entanglement is commonly characterized through global state descriptions on tensor product spaces, correlation measures or algebraic constructions, while local consistency constraints play no explicit structural role. We formulate entanglement as a combinatorial structure of overlapping local descriptions, drawing on De Bruijn graphs, where nodes represent overlapping contexts and paths encode globally coherent assemblies. We construct a graph whose nodes represent reduced quantum states on subsystems of fixed size and whose edges encode admissible extensions consistent with quantum mechanical compatibility conditions. Global many body states correspond to paths on this graph, while entanglement is reinterpreted as a property of graph connectivity and path multiplicity, rather than as a standalone numerical quantity. This formalism allows a separation between constraints imposed purely by local quantum consistency and additional structure introduced by dynamics, symmetries or boundary conditions, also clarifying how large-scale structural features may arise from local compatibility alone. Our graph-based formulation provides several advantages over conventional approaches. Supporting a unified treatment of static entanglement structure and dynamical evolution, it incorporates finite order locality and memory effects. Entanglement growth can be interpreted as path proliferation, while decoherence and noise correspond to the removal of admissible transitions. Our approach leads to testable hypotheses concerning the scaling of admissible state extensions, the robustness of entangled structures under local perturbations and the emergence of effective geometry from overlap constraints. Potential future directions include applications to many body reconstruction problems and comparative analysis of different classes of quantum states within a single combinatorial language.
Answering a question of Claudet, we prove that the uniformly random graph G∼G(n,1/2)G\sim \mathbb G(n, 1/2)G∼G(n,1/2) is Ω(n)Ω(\sqrt n)Ω(n​)-vertex-minor universal with high probability. That is, for some constant α≈0.911α\approx 0.911α≈0.911, any graph on any αnα\sqrt nαn​ specified vertices of GGG can be obtained as a vertex-minor of GGG. This has direct implications for quantum communications networks: an nnn-vertex kkk-vertex-minor universal graph corresponds to an nnn-qubit kkk-stabilizer universal graph state, which has the property that one can induce any stabilizer state on any kkk qubits using only local operations and classical communications. We further employ our methods in two other contexts. We obtain a bipartite pivot-minor version of our main result, and we use it to derive a universality statement for minors in random binary matroids. We also introduce the vertex-minor Ramsey number Rvm(k)R_{\mathrm{vm}}(k)Rvm​(k) to be the smallest value nnn such that every nnn-vertex graph contains an independent set of size kkk as a vertex-minor. Supported by our main result, we conjecture that Rvm(k)R_{\mathrm{vm}}(k)Rvm​(k) is polynomial in kkk. We prove Ω(k2)≤Rvm(k)≤2k−1Ω(k^2) \leq R_{\mathrm{vm}}(k) \leq 2^k - 1Ω(k2)≤Rvm​(k)≤2k−1.
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.