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 Cd1⊗⋯⊗Cdp, a nonzero vector is a \emph{product state} if it can be written as ketφ1⊗⋯⊗ketφp with ketφj∈Cdj∖{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.
Related
- Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid Bases
- Characterizations and Complexity of Minimum Forward and Integer Cycle Bases
- A dot-product bound from separate growth-minimizing bases
- On the Minimum Possible Maximum Degree of Induced Subgraphs of Product Graphs
- The quantitative non-unique-product landscape at the global minimum: the Nielsen-Soelberg groups
BibTeX
@misc{wang2026minimum,
title = {{Minimum Cardinalities of Multipartite Unextendible Product Bases}},
author = {Chenhao Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.05657},
eprint = {2609.05657},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05657},
}
RIS
TY - UNPB
TI - Minimum Cardinalities of Multipartite Unextendible Product Bases
AU - Chenhao Wang
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2609.05657
UR - https://arxiv.org/abs/2609.05657
AB - 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⊗⋯⊗C^d_p, a nonzero vector is a \emph{product state} if it can be written as ketφ_1⊗⋯⊗ketφ_p with ketφ_j∈C^d_j∖{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 f_m(d_1,…,d_p) be the minimum cardinality of a UPB in the space, and let f_LB(d_1,…,d_p)=1+∑_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≥3, whenever the natural lower bound f_LB is unattainable, the true minimum is exactly f_LB+1. Precisely, if the number of even local dimensions d_i is positive and even, and at least one local dimension is greater than two, then f_m(d_1,…,d_p)=f_LB(d_1,…,d_p)+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.
ER -