Unextendible product bases (UPBs) play a key role in the study of quantum entanglement and nonlocality. Here we provide an equivalent characterization of UPBs in graph-theoretic terms. Different from previous graph-theoretic investigations of UPBs, which focused mostly on the orthogonality relations between different product states, our characterization includes a graph-theoretic reformulation of the unextendibility condition. Building on this characterization, we develop a constructive method for building UPBs in low dimensions and shed light on the open question of whether there exist genuinely unextendible product bases (GUPBs), that is, multipartite product bases that are unextendible with respect to every possible bipartition. We derive a lower bound on the size of any candidate GUPB, significantly improving over the state of the art. Moreover, we show that every minimal GUPB saturating our bound must be associated to regular graphs and discuss a possible path towards the construction of a minimal GUPB in a tripartite system of minimal local dimension. Finally, we apply our characterization to the problem of distinguishing UPB states under local operations and classical communication, deriving a necessary condition for reliable discrimination in the asymptotic limit.
Unextendible product bases (UPBs) play a key role in the study of quantum entanglement and nonlocality. A famous open question is whether there exist genuinely unextendible product bases (GUPBs), namely multipartite product bases that are unextendible with respect to every possible bipartition. Here we shed light on this question by providing a characterization of UPBs and GUPBs in terms of orthogonality graphs. Building on this connection, we develop a method for constructing UPBs in low dimensions, and we derive a lower bound on the size of any GUPB, significantly improving over the state of the art. Moreover, we show that every minimal GUPB saturating our bound must be associated to regular graphs. Finally, we discuss a possible path towards the construction of a minimal GUPB in a tripartite system of minimal local dimension.
Unextendible product bases(UPBs) are central to the study of local distinguishability of orthogonal product states. While their connection to quantum nonlocality via Bell inequalities is well established, their link to quantum contextuality remains largely unexplored. We establish a graph theoretic connection between contextuality and UPBs. First, an equivalence between Klyachko-Can-Binicioğlu-Shumovsky (KCBS) vectors and the Pyramid UPB is shown and then by constructing a one parameter family of UPB vectors, a quantitative connection between `contextuality strength' and bound entanglement of states associated with the corresponding UPB is demonstrated. This equivalence is extended to generalized KCBS vectors and the GenPyramid UPB. A new class of minimal UPBs in
C3⊗Cn is constructed using Lovász-optimal orthogonal representations (LOORs) of cycle graphs and their complements which we term the GenContextual UPB. Any minimal UPB in this dimension is shown to be graph-equivalent to the GenContextual UPB. We briefly discuss the distinguishability properties of GenContextual UPB. In the reverse direction, we observe that the constituent vectors of the QuadRes UPB are LOORs of Paley graphs. The structural properties of these graphs make them suitable candidates for constructing noncontextuality inequalities, thereby establishing a bidirectional connection between quantum contextuality and UPBs.
Unextendible product bases (UPB) is an important concept and has extensive applications in various fields of quantum information theory. The construction of UPBs is closely related to combinatorics. Alon and Lovász (2001) first used a series of graph theoretic tools to characterize the necessary and sufficient conditions when the size of a UPB can attain the trivial lower bound. Later Feng (2006) brought the 1-factorization of graphs into the study of UPBs. In this paper, we further apply some graph theoretic tools to analyze the minimum size of a UPB under certain parameters and obtain a series of new results. Moreover, we have an almost complete characterization of all the potential sizes of UPBs in
C2⊗C2⊗Ck.
Unextendible product bases (UPBs) provide a versatile tool with various applications across different areas of quantum information theory. Their comprehensive characterization is thus of great importance and has been a subject of vital interest for over two decades now. An open question asks about the existence of UPBs, which are genuinely unextendible, i.e., they are not extendible even with biproduct vectors. In other words, the problem is to verify whether there exist genuinely entangled subspaces (GESs), subspaces composed solely of genuinely multiparty entangled states, complementary to UPBs. We solve this problem in the negative for many sizes of UPBs in different multipartite scenarios. In particular, in the all-important case of equal local dimensions, we show that there are always forbidden cardinalities for such UPBs, including the minimal ones corresponding to GESs of the maximal dimensions.
The existence of genuinely unextendible product bases (GUPBs), incomplete orthogonal sets of fully product states whose orthogonal complements contain no product vector across any bipartition, has remained an open problem. Here we construct GUPBs for any number
N≥3 of parties using classical maximum distance separable (MDS) codes. The MDS property imposes a rigidity on the induced product tiling across every bipartition; combined with Fourier mode deletion and a stopper state, this rigidity enforces genuine unextendibility. Consequently, the orthogonal complement of each GUPB is a genuinely entangled subspace whose normalized projector is invariant under partial transposition across every bipartition, yielding an explicit family of multipartite bound entangled states. We further construct GME witnesses that detect these states even though no fully decomposable witness can do so. Moreover, the resulting indistinguishability persists under arbitrary finite tensor powers and measurements separable across any bipartition. These results establish a direct connection between error-correcting codes and multipartite entanglement and provide an algebraic route to certifying genuinely multipartite bound entanglement.
In quantum information theory, the state space of a multipartite quantum system is modeled by a tensor product. In the tensor-product space $\C^{d_1}\otimes\cdots\otimes\C^{d_p}$, a nonzero vector is a \emph{product state} if it can be written as
∣φ1⟩⊗⋯⊗∣φp⟩ with $\ket{\varphi_j}\in\C^{d_j}\setminus\{0\}$. An \emph{unextendible product basis} (UPB) is a finite family of pairwise orthogonal product states such that no nonzero product state is orthogonal to all of them. UPBs play a key role in investigating quantum entanglement and nonlocal phenomena. Finding a smallest UPB is a natural extremal problem: it asks how few pairwise orthogonal product states suffice to prevent any further product state from being added. The general minimum-size problem for UPBs has been studied for over two decades since the seminal work of Alon and Lovász.
Let
fm(d1,…,dp) be the minimum cardinality of a UPB in the space, and let
fLB(d1,…,dp)=1+∑j=1p(dj−1) be the natural lower bound. Alon and Lovász determined exactly when
fm attains the lower bound
fLB, but the obstructed multipartite cases remained open in general.
We prove a stabilization theorem: for every non-all-qubit system with
p≥3, whenever the natural lower bound
fLB is unattainable, the true minimum is exactly
fLB+1. Precisely, if the number of even local dimensions
di is positive and even, and at least one local dimension is greater than two, then
fm(d1,…,dp)=fLB(d1,…,dp)+1. The proof is built on a unified graph-theoretic framework. Our result, together with earlier work, settles the minimum size problem for UPBs in all finite quantum systems.