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.
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.
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.
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.
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.
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.