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:2402.06260 · Leibniz international proceedings in informatics

Vertex-Minor Universal Graphs for Generating Entangled Quantum Subsystems

Maxime Cautrès, Nathan Claudet, Mehdi Mhalla, Simon Perdrix, Valentin Savin, Stéphan Thomassé

Published Jan 1, 2024• 2 citations
arXivHTMLPDF

Abstract

We study the notion of $k$-stabilizer universal quantum state, that is, an $n$-qubit quantum state, such that it is possible to induce any stabilizer state on any $k$ qubits, by using only local operations and classical communications. These states generalize the notion of $k$-pairable states introduced by Bravyi et al., and can be studied from a combinatorial perspective using graph states and $k$-vertex-minor universal graphs. First, we demonstrate the existence of $k$-stabilizer universal graph states that are optimal in size with $n=Θ(k^2)$ qubits. We also provide parameters for which a random graph state on $Θ(k^2)$ qubits is $k$-stabilizer universal with high probability. Our second contribution consists of two explicit constructions of $k$-stabilizer universal graph states on $n = O(k^4)$ qubits. Both rely upon the incidence graph of the projective plane over a finite field $\mathbb{F}_q$. This provides a major improvement over the previously known explicit construction of $k$-pairable graph states with $n = O(2^{3k})$, bringing forth a new and potentially powerful family of multipartite quantum resources.

DOI
10.4230/lipics.icalp.2024.36

Related papers

Small k-pairable states

Nathan Claudet, Mehdi Mhalla, Simon Perdrix

A $k$-pairable $n$-qubit state is a resource state that allows Local Operations and Classical Communication (LOCC) protocols to generate EPR-pairs among any $k$-disjoint pairs of the $n$ qubits. Bravyi et al. introduced a family of $k$-pairable $n$-qubit states, where $n$ grows exponentially with $k$. Our primary contribution is to establish the existence of 'small' pairable quantum states. Specifically, we present a family of $k$-pairable $n$-qubit graph states, where $n$ is polynomial in $k$, namely $n=O(k^3\ln^3k)$. Our construction relies on probabilistic methods. Furthermore, we provide an upper bound on the pairability of any arbitrary quantum state based on the support of any local unitary transformation that has the shared state as a fixed point. This lower bound implies that the pairability of a graph state is at most half of the minimum degree up to local complementation of the underlying graph, i.e., $k(|G \rangle)\le \lceil δ_{loc}(G)/2\rceil$. We also investigate the related combinatorial problem of $k$-vertex-minor-universality: a graph $G$ is $k$-vertex-minor-universal if any graph on any $k$ of its vertices is a vertex-minor of $G$. When a graph is $2k$-vertex-minor-universal, the corresponding graph state is $k$-pairable. More precisely, one can create not only EPR-pairs but also any stabilizer state on any $2k$ qubits through local operations and classical communication. We establish the existence of $k$-vertex-minor-universal graphs of order $O(k^4 \ln k)$. Finally, we explore a natural extension of pairability in the presence of errors or malicious parties and show that vertex-minor-universality ensures a robust form of pairability.

arXiv:2309.09956•Sep 18, 2023•2 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

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

Asymptotic entanglement in circle stabilizer states and states forbidding arbitrary vertex-minors

Kenneth Goodenough, Marcelo Sales

Stabilizer states play a central role in quantum information theory, and understanding their entanglement has motivated a large body of work. A well-studied question in particular is when a stabilizer state $|ψ\rangle$ can be transformed into another stabilizer state $|φ\rangle$ using only single-qubit Clifford operations and Pauli measurements. If this is possible, we say that $|φ\rangle$ is a vertex-minor of $|ψ\rangle$. Assuming Geelen's weak structural conjecture on vertex-minors, we establish the following general statement. For any fixed stabilizer state $|φ\rangle$, the entanglement in stabilizer states $|ψ\rangle$ that do not contain $|φ\rangle$ as a vertex-minor is asymptotically constrained. More concretely, we show that the distance of any sufficiently rank-connected $|ψ\rangle$ not containing $|φ\rangle$ as a vertex-minor grows as $O(\log n)$, and prove similar results for the so-called locally accessible information, a quantity that captures the amount of information that can be learned through single-qubit Pauli measurements. Our results rely on (i) connecting the above two entanglement measures to rank functions of multimatroids, (ii) connecting the rank functions of circle stabilizer states to rank functions on $4$-regular multigraphs, which asymptotically constrains the entanglement of circle stabilizer states, and (iii) using Geelen's weak structural conjecture on vertex-minors to `lift' the previous result to sufficiently connected states in proper vertex-minor-closed families of stabilizer states. Our results establish a connection between asymptotic stabilizer entanglement and forbidden vertex-minors, with direct implications for the entanglement that can be generated in quantum devices.

quant-pharXiv:2608.21526•Aug 25, 2026•0 citations

On Non-Existence of Absolutely Maximally Entangled Canonical Graph States in Even Local Dimensions

Jakub Wójcik, Owidiusz Makuta, Wojciech Bruzda +1 more

We demonstrate that absolutely maximally entangled (AME) states consisting of $N=4n$ qudits with $n\in\{1,2,3,\ldots\}$, each of even local dimension $d$, cannot be realized as canonical graph states over the ring $\mathbb{Z}_d$. This result imposes strong constraints on AME states in composite local dimensions and characterizes the limitations of graph-state constructions for highly entangled multipartite quantum systems. Furthermore, for $d\equiv 2\pmod 4$ this obstruction, combined with the prime-power decomposition of stabilizer states, excludes all pure stabilizer AME states (including four quhexes), while clarifying the distinction between canonical $\mathbb{Z}_{d}$ graph states and stabilizer constructions over prime-power factors. We also discuss a composite construction of mixed $k$-uniform states. For $(N,d)=(4,6)$, the construction yields a rank-two mixed $2$-uniform stabilizer state of purity $1/2$, which is optimal among normalized stabilizer projectors.

quant-pharXiv:2603.18193•Mar 20, 2026•0 citations

General stabilizer approach for constructing highly entangled graph states

Zahra Raissi, Adam Burchardt, Barnes, E. (Edwin)

Highly entangled multipartite states such as k-uniform (k-UNI) and absolutely maximally entangled (AME) states serve as critical resources in quantum networking and other quantum information applications. However, there does not yet exist a complete classification of such states, and much remains unknown about their entanglement structure. Here we substantially broaden the class of known k-UNI and AME states by introducing a method for explicitly constructing such states that combines classical error correcting codes and qudit graph states. This method in fact constitutes a general recipe for obtaining multipartitite entangled states from classical codes. Furthermore, we show that at least for a large subset of the class of k-UNI states that we present, the states are inequivalent under stochastic local operations and classical communication. This subset is defined by an iterative procedure for constructing a hierarchy of k-UNI graph states.

•Dec 19, 2022•12 citations
We study the notion of kkk-stabilizer universal quantum state, that is, an nnn-qubit quantum state, such that it is possible to induce any stabilizer state on any kkk qubits, by using only local operations and classical communications. These states generalize the notion of kkk-pairable states introduced by Bravyi et al., and can be studied from a combinatorial perspective using graph states and kkk-vertex-minor universal graphs. First, we demonstrate the existence of kkk-stabilizer universal graph states that are optimal in size with n=Θ(k2)n=Θ(k^2)n=Θ(k2) qubits. We also provide parameters for which a random graph state on Θ(k2)Θ(k^2)Θ(k2) qubits is kkk-stabilizer universal with high probability. Our second contribution consists of two explicit constructions of kkk-stabilizer universal graph states on n=O(k4)n = O(k^4)n=O(k4) qubits. Both rely upon the incidence graph of the projective plane over a finite field Fq\mathbb{F}_qFq​. This provides a major improvement over the previously known explicit construction of kkk-pairable graph states with n=O(23k)n = O(2^{3k})n=O(23k), bringing forth a new and potentially powerful family of multipartite quantum resources.
A kkk-pairable nnn-qubit state is a resource state that allows Local Operations and Classical Communication (LOCC) protocols to generate EPR-pairs among any kkk-disjoint pairs of the nnn qubits. Bravyi et al. introduced a family of kkk-pairable nnn-qubit states, where nnn grows exponentially with kkk. Our primary contribution is to establish the existence of 'small' pairable quantum states. Specifically, we present a family of kkk-pairable nnn-qubit graph states, where nnn is polynomial in kkk, namely n=O(k3ln⁡3k)n=O(k^3\ln^3k)n=O(k3ln3k). Our construction relies on probabilistic methods. Furthermore, we provide an upper bound on the pairability of any arbitrary quantum state based on the support of any local unitary transformation that has the shared state as a fixed point. This lower bound implies that the pairability of a graph state is at most half of the minimum degree up to local complementation of the underlying graph, i.e., k(∣G⟩)≤⌈δloc(G)/2⌉k(|G \rangle)\le \lceil δ_{loc}(G)/2\rceilk(∣G⟩)≤⌈δloc​(G)/2⌉. We also investigate the related combinatorial problem of kkk-vertex-minor-universality: a graph GGG is kkk-vertex-minor-universal if any graph on any kkk of its vertices is a vertex-minor of GGG. When a graph is 2k2k2k-vertex-minor-universal, the corresponding graph state is kkk-pairable. More precisely, one can create not only EPR-pairs but also any stabilizer state on any 2k2k2k qubits through local operations and classical communication. We establish the existence of kkk-vertex-minor-universal graphs of order O(k4ln⁡k)O(k^4 \ln k)O(k4lnk). Finally, we explore a natural extension of pairability in the presence of errors or malicious parties and show that vertex-minor-universality ensures a robust form of pairability.
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.
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.
Stabilizer states play a central role in quantum information theory, and understanding their entanglement has motivated a large body of work. A well-studied question in particular is when a stabilizer state ∣ψ⟩|ψ\rangle∣ψ⟩ can be transformed into another stabilizer state ∣φ⟩|φ\rangle∣φ⟩ using only single-qubit Clifford operations and Pauli measurements. If this is possible, we say that ∣φ⟩|φ\rangle∣φ⟩ is a vertex-minor of ∣ψ⟩|ψ\rangle∣ψ⟩. Assuming Geelen's weak structural conjecture on vertex-minors, we establish the following general statement. For any fixed stabilizer state ∣φ⟩|φ\rangle∣φ⟩, the entanglement in stabilizer states ∣ψ⟩|ψ\rangle∣ψ⟩ that do not contain ∣φ⟩|φ\rangle∣φ⟩ as a vertex-minor is asymptotically constrained. More concretely, we show that the distance of any sufficiently rank-connected ∣ψ⟩|ψ\rangle∣ψ⟩ not containing ∣φ⟩|φ\rangle∣φ⟩ as a vertex-minor grows as O(log⁡n)O(\log n)O(logn), and prove similar results for the so-called locally accessible information, a quantity that captures the amount of information that can be learned through single-qubit Pauli measurements. Our results rely on (i) connecting the above two entanglement measures to rank functions of multimatroids, (ii) connecting the rank functions of circle stabilizer states to rank functions on 444-regular multigraphs, which asymptotically constrains the entanglement of circle stabilizer states, and (iii) using Geelen's weak structural conjecture on vertex-minors to `lift' the previous result to sufficiently connected states in proper vertex-minor-closed families of stabilizer states. Our results establish a connection between asymptotic stabilizer entanglement and forbidden vertex-minors, with direct implications for the entanglement that can be generated in quantum devices.
We demonstrate that absolutely maximally entangled (AME) states consisting of N=4nN=4nN=4n qudits with n∈{1,2,3,…}n\in\{1,2,3,\ldots\}n∈{1,2,3,…}, each of even local dimension ddd, cannot be realized as canonical graph states over the ring Zd\mathbb{Z}_dZd​. This result imposes strong constraints on AME states in composite local dimensions and characterizes the limitations of graph-state constructions for highly entangled multipartite quantum systems. Furthermore, for d≡2(mod4)d\equiv 2\pmod 4d≡2(mod4) this obstruction, combined with the prime-power decomposition of stabilizer states, excludes all pure stabilizer AME states (including four quhexes), while clarifying the distinction between canonical Zd\mathbb{Z}_{d}Zd​ graph states and stabilizer constructions over prime-power factors. We also discuss a composite construction of mixed kkk-uniform states. For (N,d)=(4,6)(N,d)=(4,6)(N,d)=(4,6), the construction yields a rank-two mixed 222-uniform stabilizer state of purity 1/21/21/2, which is optimal among normalized stabilizer projectors.
Highly entangled multipartite states such as k-uniform (k-UNI) and absolutely maximally entangled (AME) states serve as critical resources in quantum networking and other quantum information applications. However, there does not yet exist a complete classification of such states, and much remains unknown about their entanglement structure. Here we substantially broaden the class of known k-UNI and AME states by introducing a method for explicitly constructing such states that combines classical error correcting codes and qudit graph states. This method in fact constitutes a general recipe for obtaining multipartitite entangled states from classical codes. Furthermore, we show that at least for a large subset of the class of k-UNI states that we present, the states are inequivalent under stochastic local operations and classical communication. This subset is defined by an iterative procedure for constructing a hierarchy of k-UNI graph states.