Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Combinatorial Theory Series A

Unextendible Product Bases

Noga Alon, László Lovász

Published Jul 1, 2001• 101 citations
Publisher
DOI
10.1006/jcta.2000.3122

Related papers

Unextendible Product Bases, Uncompletable Product Bases and Bound Entanglement

David Peter Divincenzo, Tal Mor, Peter W. Shor +2 more

arXiv:quant-ph/9908070•Communications in Mathematical Physics•Jul 1, 2003•379 citations

Unextendible product bases and the construction of inseparable states

A. O. Pittenger

arXiv:quant-ph/0208028•Linear Algebra and its Applications•Nov 11, 2002•37 citations

Characterizing unextendible product bases in qutrit-ququad system

Ying‐Hui Yang, Fei Gao, Guang‐Bao Xu +3 more

Unextendible product bases (UPBs) play an important role in quantum information theory. However, very little is known about UPBs in Hilbert space of local dimension more than three. In this paper, we study the UPBs in qutrit-ququad system and find that there only exist six, seven and eight-state UPBs. We completely characterize the six-state and seven-state UPBs. For eight-state UPBs, seven classes of UPBs are found. As auxiliary results, we study the distinguishability of qutrit-ququad UPBs by separable measurements, and find that there exists a UPB that cannot be distinguished.

Scientific Reports•Jul 14, 2015•33 citations

Graph-theoretic quantum contextuality and unextendible product bases

Gurvir Singh, Arvind

Unextendible product bases(UPBs) are central to the study of local distinguishability of orthogonal product states. While their connection to quantum nonlocality via Bell inequalities is well established, their link to quantum contextuality remains largely unexplored. We establish a graph theoretic connection between contextuality and UPBs. First, an equivalence between Klyachko-Can-Binicioğlu-Shumovsky (KCBS) vectors and the Pyramid UPB is shown and then by constructing a one parameter family of UPB vectors, a quantitative connection between `contextuality strength' and bound entanglement of states associated with the corresponding UPB is demonstrated. This equivalence is extended to generalized KCBS vectors and the GenPyramid UPB. A new class of minimal UPBs in $\mathbb{C}^3 \otimes \mathbb{C}^n$ is constructed using Lovász-optimal orthogonal representations (LOORs) of cycle graphs and their complements which we term the GenContextual UPB. Any minimal UPB in this dimension is shown to be graph-equivalent to the GenContextual UPB. We briefly discuss the distinguishability properties of GenContextual UPB. In the reverse direction, we observe that the constituent vectors of the QuadRes UPB are LOORs of Paley graphs. The structural properties of these graphs make them suitable candidates for constructing noncontextuality inequalities, thereby establishing a bidirectional connection between quantum contextuality and UPBs.

arXiv:2510.26719•Physical Review A•Apr 20, 2026•0 citations

Nonseparability

Bernard d’Espagnat

Springer eBooks•Jan 1, 1983•0 citations

Automated Construction and Verification of Unextendible Product Bases

Zicheng Han, Wanchen Zhang, Fei Shi +1 more

Unextendible product bases (UPBs) are important structures in quantum information theory, with applications to completely entangled subspaces, bound entanglement, and local indistinguishability. Since many properties and applications of UPBs are closely related to their cardinalities, one of the central problems in the study of UPBs is to determine whether UPBs of prescribed sizes exist in a given multipartite system. In this paper, we introduce a SAT-assisted framework based on decompositions of the \(N\)-dimensional hypercube. We define \(O_N\)-tile decompositions and prove a tile-to-UPB theorem: every \(O_N\)-tile decomposition induces a UPB through a construction based on tile-wise Fourier product bases and a global stopper state. We then encode the search for such decompositions as a Boolean satisfiability (SAT) problem and use SAT solvers to generate explicit instances. In terms of verification, we also implement a UPB verification algorithm based on local orthogonality graphs and unsaturated subspaces. The algorithm can be used to determine whether an arbitrary finite set of product states forms a UPB. Using this framework, we obtain UPBs of several sizes in some tripartite and quadripartite systems, including sizes \(13,14,\ldots,23\) in \(\mathbb C^3\otimes\mathbb C^3\otimes\mathbb C^3\). Moreover, the small-dimensional instances obtained here can serve as seed UPBs for recursive constructions, leading to further examples in larger multipartite systems.

quant-pharXiv:2608.01438•Aug 4, 2026•1 citation
Unextendible product bases (UPBs) play an important role in quantum information theory. However, very little is known about UPBs in Hilbert space of local dimension more than three. In this paper, we study the UPBs in qutrit-ququad system and find that there only exist six, seven and eight-state UPBs. We completely characterize the six-state and seven-state UPBs. For eight-state UPBs, seven classes of UPBs are found. As auxiliary results, we study the distinguishability of qutrit-ququad UPBs by separable measurements, and find that there exists a UPB that cannot be distinguished.
Unextendible product bases(UPBs) are central to the study of local distinguishability of orthogonal product states. While their connection to quantum nonlocality via Bell inequalities is well established, their link to quantum contextuality remains largely unexplored. We establish a graph theoretic connection between contextuality and UPBs. First, an equivalence between Klyachko-Can-Binicioğlu-Shumovsky (KCBS) vectors and the Pyramid UPB is shown and then by constructing a one parameter family of UPB vectors, a quantitative connection between `contextuality strength' and bound entanglement of states associated with the corresponding UPB is demonstrated. This equivalence is extended to generalized KCBS vectors and the GenPyramid UPB. A new class of minimal UPBs in C3⊗Cn\mathbb{C}^3 \otimes \mathbb{C}^nC3⊗Cn is constructed using Lovász-optimal orthogonal representations (LOORs) of cycle graphs and their complements which we term the GenContextual UPB. Any minimal UPB in this dimension is shown to be graph-equivalent to the GenContextual UPB. We briefly discuss the distinguishability properties of GenContextual UPB. In the reverse direction, we observe that the constituent vectors of the QuadRes UPB are LOORs of Paley graphs. The structural properties of these graphs make them suitable candidates for constructing noncontextuality inequalities, thereby establishing a bidirectional connection between quantum contextuality and UPBs.
Unextendible product bases (UPBs) are important structures in quantum information theory, with applications to completely entangled subspaces, bound entanglement, and local indistinguishability. Since many properties and applications of UPBs are closely related to their cardinalities, one of the central problems in the study of UPBs is to determine whether UPBs of prescribed sizes exist in a given multipartite system. In this paper, we introduce a SAT-assisted framework based on decompositions of the NNN-dimensional hypercube. We define ONO_NON​-tile decompositions and prove a tile-to-UPB theorem: every ONO_NON​-tile decomposition induces a UPB through a construction based on tile-wise Fourier product bases and a global stopper state. We then encode the search for such decompositions as a Boolean satisfiability (SAT) problem and use SAT solvers to generate explicit instances. In terms of verification, we also implement a UPB verification algorithm based on local orthogonality graphs and unsaturated subspaces. The algorithm can be used to determine whether an arbitrary finite set of product states forms a UPB. Using this framework, we obtain UPBs of several sizes in some tripartite and quadripartite systems, including sizes 13,14,…,2313,14,\ldots,2313,14,…,23 in C3⊗C3⊗C3\mathbb C^3\otimes\mathbb C^3\otimes\mathbb C^3C3⊗C3⊗C3. Moreover, the small-dimensional instances obtained here can serve as seed UPBs for recursive constructions, leading to further examples in larger multipartite systems.