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.
An important problem in quantum information is to construct multiqubit unextendible product bases (UPBs). By using the unextendible orthogonal matrices, we construct a 7-qubit UPB of size 11. It solves an open problem in [Quantum Information Processing 19:185 (2020)]. Next, we graph-theoretically show that the UPB is locally indistinguishable in the bipartite systems of two qubits and five qubits, respectively. It turns out that the UPB corresponds to a complete graph with 11 vertices constructed by three sorts of nonisomorphic graphs. Taking the graphs as product vectors, we show that they are in three different orbits up to local unitary equivalence. Moreover, we also present the number of sorts of nonisomorphic graphs of complete graphs of some known UPBs and their orbits.
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 (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) are interesting mathematical objects arising in composite Hilbert spaces that have found various applications in quantum information theory, for instance in a construction of bound entangled states or Bell inequalities without quantum violation. They are closely related to another important notion, completely entangled subspaces (CESs), which are those that do not contain any fully separable pure state. Among CESs one finds a class of subspaces in which all vectors are not only entangled but genuinely entangled. Here we explore the connection between UPBs and such genuinely entangled subspaces (GESs) and provide classes of nonorthogonal UPBs that lead to GESs for any number of parties and local dimensions. We then show how these subspaces can be immediately utilized for a simple general construction of genuinely entangled states in any such multipartite scenario.