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 Physics A Mathematical and Theoretical

Unextendible product bases from tile structures in bipartite systems

Siwen You, Chen Wang, Fei Shi, Sihuang Hu, Yiwei Zhang

Published Jan 5, 2023• 2 citations
Publisher

Abstract

Abstract Unextendible product basis (UPB) is one of the most fundamental concepts in the field of quantum information theory, and its constructions attract much attention. Recently, Shi et al (2020 Phy. Rev. A 101 062329) constructed UPBs via a tile structure approach. They showed that a tile structure in an m × n grid with certain properties leads to explicit constructions of UPBs in C m ⊗ C n . The size of the UPB is m n − s + 1 if the tile structure contains exactly s tiles. In this paper, we deeply analyze the extent of the tile structure approach, by showing that a desired tile structure in an m × m grid contains at most ⌊ m 2 4 ⌋ + m tiles, and thus the smallest size of a UPB in C m ⊗ C m constructed by this approach is m 2 − ⌊ m 2 4 ⌋ − m + 1 . Such tile structures and UPBs are referred to as extremal tile structures and extremal UPBs. We provide algorithms both for constructing possible candidates of extremal tile structures and checking their validity. For applications, we connect the extremal UPBs to local irreducibility and bound entangled states with large ranks.

DOI
10.1088/1751-8121/acb099

Related papers

Tile structures for unextendible product bases

Fei Shi, Xiande Zhang, Lin Chen

We completely characterize the condition when a tile structure provides an unextendible product basis (UPB), and construct UPBs of different large sizes in $\mathbb{C}^m\otimes\mathbb{C}^n$ for any $n\geq m\geq 3$. This solves an open problem in [S. Halder et al., Phys. Rev. A 99, 062329 (2019)]. As an application, we show that our UPBs of size $(mn-4\lfloor\frac{m-1}{2}\rfloor)$ in $\mathbb{C}^m\otimes\mathbb{C}^n$ can be perfectly distinguished by local operations and classical communications assisted with a $\lceil\frac{m}{2}\rceil\otimes\lceil\frac{m}{2}\rceil$ maximally entangled state.

•Mar 9, 2020•1 citation

Unextendible product bases from tile structures and their local entanglement-assisted distinguishability

Fei Shi, Xiande Zhang, Lin Chen

We completely characterize the condition when a tile structure provides an unextendible product basis (UPB) and construct UPBs of different large sizes in ${\mathbb{C}}^{m}\ensuremath{\bigotimes}{\mathbb{C}}^{n}$. In particular, we show that there exists a UPB of size $(mn\ensuremath{-}4\ensuremath{\lfloor}\frac{m\ensuremath{-}1}{2}\ensuremath{\rfloor})$ in ${\mathbb{C}}^{m}\ensuremath{\bigotimes}{\mathbb{C}}^{n}$ for any $n\ensuremath{\ge}m\ensuremath{\ge}3$, which solves an open problem [S. Halder et al., Phys. Rev. A 99, 062329 (2019)]. As an application, we show that this class of UPBs can be perfectly distinguished by local operations and classical communications assisted with a $\ensuremath{\lceil}\frac{m}{2}\ensuremath{\rceil}\ensuremath{\bigotimes}\ensuremath{\lceil}\frac{m}{2}\ensuremath{\rceil}$ maximally entangled state.

arXiv:2003.03898•Physical Review A•Jun 22, 2020•24 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•0 citations

Unextendible and strongly uncompletable product bases

Xiao-Fan Zhen, Hui-Juan Zuo, Fei Shi +1 more

In 2003, DiVincenzo et al. put forward the question of whether there exists an unextendible product basis (UPB) that is an uncompletable product basis in every bipartition [DiVincenzo et al. Commun. Math. Phys. 238, 379–410 (2003)]. Recently, Shi et al. presented a UPB in tripartite systems that is also a strongly uncompletable product basis (SUCPB) in every bipartition [Shi et al. New J. Phys. 24, 113025 (2022)]. However, whether there exist UPBs that are SUCPBs in only one or two bipartitions remains unknown. We provide a sufficient condition for the existence of SUCPBs based on a quasi U-tile structure. We analyze all possible cases about the relationship between UPBs and SUCPBs in tripartite systems. In particular, we construct a UPB with smaller size d3 − 3d2 + 1 in Cd⊗Cd⊗Cd, which is an SUCPB in every bipartition and has a smaller cardinality than the existing one.

arXiv:2411.18036•Journal of Mathematical Physics•Nov 1, 2024•2 citations

Unextendible and uncompletable product bases in every bipartition

Fei Shi, Mao-Sheng Li, Xiande Zhang +1 more

Abstract Unextendible product basis is an important object in quantum information theory and features a broad spectrum of applications, ranging from quantum nonlocality to quantum cryptography. A generalized concept called uncompletable product basis also attracts much attention. In this paper, we find some unextendible product bases that are uncompletable product bases in every bipartition, which answers a 19 year-old open question proposed by DiVincenzo et al (2003 Commun. Math. Phys. 238 379–410). As a consequence, we connect such unextendible product bases to local hiding of information, positive-partial-transpose entangled states and genuinely entangled states. Furthermore, we give a sufficient condition for the existence of an unextendible product basis that is still unextendible in every bipartition, and the existence of such a UPB is another open question proposed by Demianowic et al (2018 Phys. Rev. A 98 012313). Our results advance the understanding of the geometry of unextendible product bases.

arXiv:2207.04763•New Journal of Physics•Nov 1, 2022•11 citations

Constructing the three-qudit unextendible product bases with strong nonlocality

Bichen Che, Zhao Dou, Xiu‐Bo Chen +3 more

Unextendible product bases (UPBs) are interesting members of a family of orthogonal product bases. Here, we investigate the construction of 3-qudit UPBs with strong nonlocality. First, a UPB set in C 3 ⊗ C 3 ⊗ C 3 of size 19 is presented based on the shift UPBs. By mapping the system to a Rubik’s cube, we provide a general method of constructing UPBs in Cd ⊗ Cd ⊗ Cd of size ( d – 1 )3 + 2d + 5, whose corresponding Rubik’s cube is composed of four parts. Second, for the more general case where the dimensions of parties are different, we extend the classical tile structure to the 3-qudit system and propose the tri-tile structure. By means of this structure, a C 4 ⊗ C 4 ⊗ C 5 system of size 38 is obtained based on a C 3 ⊗ C 3 ⊗ C 4 system of size 19. Then, we generalize this approach to the C d 1 ⊗ C d 2 ⊗ C d 3 system which also consists of four parts. Our research provides a positive answer to the open question raised in by Halder et al. [Phys. Rev. Lett. 122 040403 (2019)], indicating that there do exist UPBs that can exhibit strong quantum nonlocality without entanglement.

Chinese Physics B•Jan 12, 2022•3 citations
Abstract Unextendible product basis (UPB) is one of the most fundamental concepts in the field of quantum information theory, and its constructions attract much attention. Recently, Shi et al (2020 Phy. Rev. A 101 062329) constructed UPBs via a tile structure approach. They showed that a tile structure in an m × n grid with certain properties leads to explicit constructions of UPBs in C m ⊗ C n . The size of the UPB is m n − s + 1 if the tile structure contains exactly s tiles. In this paper, we deeply analyze the extent of the tile structure approach, by showing that a desired tile structure in an m × m grid contains at most ⌊ m 2 4 ⌋ + m tiles, and thus the smallest size of a UPB in C m ⊗ C m constructed by this approach is m 2 − ⌊ m 2 4 ⌋ − m + 1 . Such tile structures and UPBs are referred to as extremal tile structures and extremal UPBs. We provide algorithms both for constructing possible candidates of extremal tile structures and checking their validity. For applications, we connect the extremal UPBs to local irreducibility and bound entangled states with large ranks.
We completely characterize the condition when a tile structure provides an unextendible product basis (UPB), and construct UPBs of different large sizes in Cm⊗Cn\mathbb{C}^m\otimes\mathbb{C}^nCm⊗Cn for any n≥m≥3n\geq m\geq 3n≥m≥3. This solves an open problem in [S. Halder et al., Phys. Rev. A 99, 062329 (2019)]. As an application, we show that our UPBs of size (mn−4⌊m−12⌋)(mn-4\lfloor\frac{m-1}{2}\rfloor)(mn−4⌊2m−1​⌋) in Cm⊗Cn\mathbb{C}^m\otimes\mathbb{C}^nCm⊗Cn can be perfectly distinguished by local operations and classical communications assisted with a ⌈m2⌉⊗⌈m2⌉\lceil\frac{m}{2}\rceil\otimes\lceil\frac{m}{2}\rceil⌈2m​⌉⊗⌈2m​⌉ maximally entangled state.
We completely characterize the condition when a tile structure provides an unextendible product basis (UPB) and construct UPBs of different large sizes in ${\mathbb{C}}^{m}\ensuremath{\bigotimes}{\mathbb{C}}^{n}$. In particular, we show that there exists a UPB of size $(mn\ensuremath{-}4\ensuremath{\lfloor}\frac{m\ensuremath{-}1}{2}\ensuremath{\rfloor})$ in ${\mathbb{C}}^{m}\ensuremath{\bigotimes}{\mathbb{C}}^{n}$ for any $n\ensuremath{\ge}m\ensuremath{\ge}3$, which solves an open problem [S. Halder et al., Phys. Rev. A 99, 062329 (2019)]. As an application, we show that this class of UPBs can be perfectly distinguished by local operations and classical communications assisted with a $\ensuremath{\lceil}\frac{m}{2}\ensuremath{\rceil}\ensuremath{\bigotimes}\ensuremath{\lceil}\frac{m}{2}\ensuremath{\rceil}$ maximally entangled state.
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.
In 2003, DiVincenzo et al. put forward the question of whether there exists an unextendible product basis (UPB) that is an uncompletable product basis in every bipartition [DiVincenzo et al. Commun. Math. Phys. 238, 379–410 (2003)]. Recently, Shi et al. presented a UPB in tripartite systems that is also a strongly uncompletable product basis (SUCPB) in every bipartition [Shi et al. New J. Phys. 24, 113025 (2022)]. However, whether there exist UPBs that are SUCPBs in only one or two bipartitions remains unknown. We provide a sufficient condition for the existence of SUCPBs based on a quasi U-tile structure. We analyze all possible cases about the relationship between UPBs and SUCPBs in tripartite systems. In particular, we construct a UPB with smaller size d3 − 3d2 + 1 in Cd⊗Cd⊗Cd, which is an SUCPB in every bipartition and has a smaller cardinality than the existing one.
Abstract Unextendible product basis is an important object in quantum information theory and features a broad spectrum of applications, ranging from quantum nonlocality to quantum cryptography. A generalized concept called uncompletable product basis also attracts much attention. In this paper, we find some unextendible product bases that are uncompletable product bases in every bipartition, which answers a 19 year-old open question proposed by DiVincenzo et al (2003 Commun. Math. Phys. 238 379–410). As a consequence, we connect such unextendible product bases to local hiding of information, positive-partial-transpose entangled states and genuinely entangled states. Furthermore, we give a sufficient condition for the existence of an unextendible product basis that is still unextendible in every bipartition, and the existence of such a UPB is another open question proposed by Demianowic et al (2018 Phys. Rev. A 98 012313). Our results advance the understanding of the geometry of unextendible product bases.
Unextendible product bases (UPBs) are interesting members of a family of orthogonal product bases. Here, we investigate the construction of 3-qudit UPBs with strong nonlocality. First, a UPB set in C 3 ⊗ C 3 ⊗ C 3 of size 19 is presented based on the shift UPBs. By mapping the system to a Rubik’s cube, we provide a general method of constructing UPBs in Cd ⊗ Cd ⊗ Cd of size ( d – 1 )3 + 2d + 5, whose corresponding Rubik’s cube is composed of four parts. Second, for the more general case where the dimensions of parties are different, we extend the classical tile structure to the 3-qudit system and propose the tri-tile structure. By means of this structure, a C 4 ⊗ C 4 ⊗ C 5 system of size 38 is obtained based on a C 3 ⊗ C 3 ⊗ C 4 system of size 19. Then, we generalize this approach to the C d 1 ⊗ C d 2 ⊗ C d 3 system which also consists of four parts. Our research provides a positive answer to the open question raised in by Halder et al. [Phys. Rev. Lett. 122 040403 (2019)], indicating that there do exist UPBs that can exhibit strong quantum nonlocality without entanglement.