Minimum Cardinalities of Multipartite Unextendible Product Bases

Abstract:In quantum information theory, the state space of a multipartite quantum system is modeled by a tensor product. In the tensor-product space $\mathbb C^{d_1}\otimes\cdots\otimes\mathbb C^{d_p}$, a nonzero vector is a \emph{product state} if it can be written as $\lvert \varphi_1\rangle\otimes\cdots\otimes\lvert \varphi_p\rangle$ with $\lvert \varphi_j\rangle\in\mathbb 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. For local dimensions $d_1,\ldots,d_p\ge2$, let $f_m(d_1,\ldots,d_p)$ be the minimum cardinality of a UPB and let $f_{LB}(d_1,\ldots,d_p)=1+\sum_{j=1}^{p}(d_j-1)$ be the natural lower bound. Alon and Lovász determined exactly when $f_m$ attains the lower bound $f_{LB}$, but the obstructed multipartite cases remained open in general. We prove a stabilization theorem: for every non-all-qubit system with $p\ge3$, whenever parity prevents the natural lower bound $f_{LB}$ from being attained, the true minimum is exactly $f_{LB}+1$. Equivalently, if the number of even local dimensions is positive and even, and at least one local dimension is greater than two, then $f_m(d_1,\ldots,d_p)=f_{LB}(d_1,\ldots,d_p)+1$. The proof is built on a unified graph-theoretic framework. Our result, together with earlier work, settles the minimum-cardinality problem for UPBs in all finite quantum systems.

Quantum Physics (quant-ph); Combinatorics (math.CO)

arXiv:2609.05657 [quant-ph]

(or arXiv:2609.05657v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.05657 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.