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.
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.
The construction of multiqubit unextendible product bases (UPBs) has been a long-standing problem. We give a systematic construction of multiqubit UPBs by studying their unextendible orthogonal matrices (UOMs) with graph-theoretic methods. Row decompositions of small UOMs produce the main intervals. Com- pletion graphs settle the remaining small UPB sizes, except for one size obtained from a good column structure. Nonexistence of the other UPB sizes follows from counts of fibres and row pairs. The computer is used only for a few finite UOM checks, whose exact tests are stated in the certificate appendix. These arguments determine the complete multiqubit UPB size spectrum in every dimension.
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.
It has remained an open question whether a genuinely unextendible product basis (GUPB) exists. We resolve this problem by constructing an explicit three-qutrit GUPB of cardinality fourteen in the smallest tripartite Hilbert space in which a GUPB can exist. Together with the nonexistence of three-qutrit GUPBs of cardinality less than fourteen, our construction proves that fourteen is the minimum cardinality. A padding procedure further extends the construction to all tripartite systems whose local dimensions are at least three. As applications, the normalized projector onto the thirteen-dimensional orthogonal complement of the three-qutrit GUPB is positive under partial transposition and bound entangled across every bipartition, while the GUPB exhibits strong quantum nonlocality without entanglement.