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• 8 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•12 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•4 citations

Distributing Graph States Across Quantum Networks

Alexander Fischer, Don Towsley

Graph states form an important class of multipartite entangled quantum states. We propose a new approach for distributing graph states across a quantum network. We consider a quantum network consisting of nodes—quantum computers within which local operations are free—and EPR pairs shared between nodes that can continually be generated. We prove upper bounds for our approach on the number of EPR pairs consumed, completion time, and amount of classical communication required, all of which are equal to or better than that of prior work [10]. We also reduce the problem of minimizing the completion time to distribute a graph state using our approach to a network flow problem having polynomial time complexity.

arXiv:2009.10888•IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2021•42 citations

Complexity of Graph State Preparation

Mehdi Mhalla, Simon Perdrix

The graph state formalism is a useful abstraction of entanglement. It is used in some multipartite purification schemes and it adequately represents universal resources for measurement-only quantum computation. We focus in this paper on the complexity of graph state preparation. We consider the number of ancillary qubits, the size of the primitive operators, and the duration of preparation. For each lexicographic order over these parameters we give upper and lower bounds for the complexity of graph state preparation. The first part motivates our work and introduces basic notions and notations for the study of graph states. Then we study some graph properties of graph states, characterizing their minimal degree by local unitary transformations, we propose an algorithm to reduce the degree of a graph state, and show the relationship with Sutner sigma-game. These properties are used in the last part, where algorithms and lower bounds for each lexicographic order over the considered parameters are presented.

arXiv:quant-ph/0412071•Dec 9, 2004•20 citations

The Minimum Size of Qubit Unextendible Product Bases

Nathaniel Johnston

We investigate the problem of constructing unextendible product bases in the qubit case - that is, when each local dimension equals 2. The cardinality of the smallest unextendible product basis is known in all qubit cases except when the number of parties is a multiple of 4 greater than 4 itself. We construct small unextendible product bases in all of the remaining open cases, and we use graph theory techniques to produce a computer-assisted proof that our constructions are indeed the smallest possible.

arXiv:1302.1604•Leibniz international proceedings in informatics•Jan 1, 2013•21 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.
Graph states form an important class of multipartite entangled quantum states. We propose a new approach for distributing graph states across a quantum network. We consider a quantum network consisting of nodes—quantum computers within which local operations are free—and EPR pairs shared between nodes that can continually be generated. We prove upper bounds for our approach on the number of EPR pairs consumed, completion time, and amount of classical communication required, all of which are equal to or better than that of prior work [10]. We also reduce the problem of minimizing the completion time to distribute a graph state using our approach to a network flow problem having polynomial time complexity.
The graph state formalism is a useful abstraction of entanglement. It is used in some multipartite purification schemes and it adequately represents universal resources for measurement-only quantum computation. We focus in this paper on the complexity of graph state preparation. We consider the number of ancillary qubits, the size of the primitive operators, and the duration of preparation. For each lexicographic order over these parameters we give upper and lower bounds for the complexity of graph state preparation. The first part motivates our work and introduces basic notions and notations for the study of graph states. Then we study some graph properties of graph states, characterizing their minimal degree by local unitary transformations, we propose an algorithm to reduce the degree of a graph state, and show the relationship with Sutner sigma-game. These properties are used in the last part, where algorithms and lower bounds for each lexicographic order over the considered parameters are presented.
We investigate the problem of constructing unextendible product bases in the qubit case - that is, when each local dimension equals 2. The cardinality of the smallest unextendible product basis is known in all qubit cases except when the number of parties is a multiple of 4 greater than 4 itself. We construct small unextendible product bases in all of the remaining open cases, and we use graph theory techniques to produce a computer-assisted proof that our constructions are indeed the smallest possible.