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

Small k-pairable states

Nathan Claudet, Mehdi Mhalla, Simon Perdrix

Published Sep 18, 2023• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2309.09956

Related papers

Vertex-Minor Universal Graphs for Generating Entangled Quantum Subsystems

Maxime Cautrès, Nathan Claudet, Mehdi Mhalla +3 more

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.

arXiv:2402.06260•Leibniz international proceedings in informatics•Jan 1, 2024•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

Local Equivalences of Graph States

Nathan Claudet

Graph states form a large family of quantum states that are in one-to-one correspondence with mathematical graphs. Graph states are used in many applications, such as measurement-based quantum computation, as multipartite entangled resources. It is thus crucial to understand when two such states have the same entanglement, i.e. when they can be transformed into each other using only local operations. In this case, we say that the graph states are LU-equivalent (local unitary). If the local operations are restricted to the so-called Clifford group, we say that the graph states are LC-equivalent (local Clifford). Interestingly, a simple graph rule called local complementation fully captures LC-equivalence, in the sense that two graph states are LC-equivalent if and only if the underlying graphs are related by a sequence of local complementations. While it was once conjectured that two LU-equivalent graph states are always LC-equivalent, counterexamples do exist and local complementation fails to fully capture the entanglement of graph states. We introduce in this thesis a generalization of local complementation that does fully capture LU-equivalence. Using this characterization, we prove the existence of an infinite strict hierarchy of local equivalences between LC- and LU-equivalence. This also leads to the design of a quasi-polynomial algorithm for deciding whether two graph states are LU-equivalent, and to a proof that two LU-equivalent graph states are LC-equivalent if they are defined on at most 19 qubits. Furthermore, we study graph states that are universal in the sense that any smaller graph state, defined on any small enough set of qubits, can be induced using only local operations. We provide bounds and an optimal, probabilistic construction.

quant-pharXiv:2511.22271•Nov 28, 2025•0 citations

Universal Nested Quantum Switch

Jorge Miguel-Ramiro, Maria Flors Mor-Ruiz, Wolfgang Dür

The quantum switch is a basic network primitive that allows one to connect multiple nodes in a quantum network via a central node. We show that the same functionality can be achieved with a different geometry that does not rely on a powerful and large central unit, but instead utilizes evenly distributed resources. This approach is resilient against node failures. We provide a nested construction with logarithmically many qubits per node and a total of $O(n\log n)$ Bell pairs, in contrast to other distributed approaches based on pre-shared entanglement that scale as $O(n^2)$. The construction achieves fully flexible pairwise connectivity, where the shared resource state can be locally transformed into $n/2$ arbitrarily distributed Bell states. We also present a graph state variant with just one qubit per node, which allows one to generate $O(n/\log^2 n)$ Bell pairs.

quant-pharXiv:2603.00236•npj Quantum Information•Mar 3, 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

The Structure of Circle Graph States

Frederik Hahn, Rose McCarty, Hendrik Poulsen Nautrup +1 more

Circle graph states are a structurally important family of graph states. The family's entanglement is a priori high enough to allow for universal measurement-based quantum computation (MBQC); however, MBQC on circle graph states is actually efficiently classically simulable. In this work, we paint a detailed picture of the local equivalence of circle graph states. First, we consider the class of all graph states that are local unitary (LU)-equivalent to circle graph states. In graph-theoretical terms, this LU-equivalence class is the set of all graphs reachable from the family of circle graphs by applying $r$-local complementations. We prove that the only graph states that are LU-equivalent to circle graph states are circle graph states themselves: circle graphs are closed under $r$-local complementation. Second, we show that bipartite circle graph states, i.e., 2-colorable circle graph states, are in one-to-one correspondence with planar code states, on which MBQC is known to be efficiently classically simulable. Leveraging this correspondence, we present alternative, simple proofs that (1) if a planar code state is LU-equivalent to a stabilizer state, they are in fact local Clifford (LC)-equivalent to it and that (2) MBQC on all circle graph states is efficiently classically simulable. Third and finally, we demonstrate that the problem of counting the number of graph states LU-equivalent to a given graph state is $\#\mathsf{P}$-hard.

quant-pharXiv:2603.08847•Mar 11, 2026•0 citations
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.
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.
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.
Graph states form a large family of quantum states that are in one-to-one correspondence with mathematical graphs. Graph states are used in many applications, such as measurement-based quantum computation, as multipartite entangled resources. It is thus crucial to understand when two such states have the same entanglement, i.e. when they can be transformed into each other using only local operations. In this case, we say that the graph states are LU-equivalent (local unitary). If the local operations are restricted to the so-called Clifford group, we say that the graph states are LC-equivalent (local Clifford). Interestingly, a simple graph rule called local complementation fully captures LC-equivalence, in the sense that two graph states are LC-equivalent if and only if the underlying graphs are related by a sequence of local complementations. While it was once conjectured that two LU-equivalent graph states are always LC-equivalent, counterexamples do exist and local complementation fails to fully capture the entanglement of graph states. We introduce in this thesis a generalization of local complementation that does fully capture LU-equivalence. Using this characterization, we prove the existence of an infinite strict hierarchy of local equivalences between LC- and LU-equivalence. This also leads to the design of a quasi-polynomial algorithm for deciding whether two graph states are LU-equivalent, and to a proof that two LU-equivalent graph states are LC-equivalent if they are defined on at most 19 qubits. Furthermore, we study graph states that are universal in the sense that any smaller graph state, defined on any small enough set of qubits, can be induced using only local operations. We provide bounds and an optimal, probabilistic construction.
The quantum switch is a basic network primitive that allows one to connect multiple nodes in a quantum network via a central node. We show that the same functionality can be achieved with a different geometry that does not rely on a powerful and large central unit, but instead utilizes evenly distributed resources. This approach is resilient against node failures. We provide a nested construction with logarithmically many qubits per node and a total of O(nlog⁡n)O(n\log n)O(nlogn) Bell pairs, in contrast to other distributed approaches based on pre-shared entanglement that scale as O(n2)O(n^2)O(n2). The construction achieves fully flexible pairwise connectivity, where the shared resource state can be locally transformed into n/2n/2n/2 arbitrarily distributed Bell states. We also present a graph state variant with just one qubit per node, which allows one to generate O(n/log⁡2n)O(n/\log^2 n)O(n/log2n) Bell pairs.
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.
Circle graph states are a structurally important family of graph states. The family's entanglement is a priori high enough to allow for universal measurement-based quantum computation (MBQC); however, MBQC on circle graph states is actually efficiently classically simulable. In this work, we paint a detailed picture of the local equivalence of circle graph states. First, we consider the class of all graph states that are local unitary (LU)-equivalent to circle graph states. In graph-theoretical terms, this LU-equivalence class is the set of all graphs reachable from the family of circle graphs by applying rrr-local complementations. We prove that the only graph states that are LU-equivalent to circle graph states are circle graph states themselves: circle graphs are closed under rrr-local complementation. Second, we show that bipartite circle graph states, i.e., 2-colorable circle graph states, are in one-to-one correspondence with planar code states, on which MBQC is known to be efficiently classically simulable. Leveraging this correspondence, we present alternative, simple proofs that (1) if a planar code state is LU-equivalent to a stabilizer state, they are in fact local Clifford (LC)-equivalent to it and that (2) MBQC on all circle graph states is efficiently classically simulable. Third and finally, we demonstrate that the problem of counting the number of graph states LU-equivalent to a given graph state is #P\#\mathsf{P}#P-hard.