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

Tile structures for unextendible product bases

Fei Shi, Xiande Zhang, Lin Chen

Published Mar 9, 2020• 1 citation
OpenAlex

Abstract

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.

Related papers

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

Unextendible product bases from tile structures in bipartite systems

Siwen You, Chen Wang, Fei Shi +2 more

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.

Journal of Physics A Mathematical and Theoretical•Jan 5, 2023•2 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

Strong nonlocal sets of UPB

Bichen Che, Zhao Dou, Min Lei +1 more

The unextendible product bases (UPBs) are interesting members from the family of orthogonal product states. In this paper, we investigate the construction of 3-qubit UPB with strong nonlocality of different sizes. First, a UPB set in ${{C}^{3}}\otimes {{C}^{3}}\otimes {{C}^{3}}$ of size 12 is presented based on the Shifts UPB, the structure of which is described by mapping the system to a $3\times 3\times 3$ Rubik's Cube. After observing the orthogonal graph of each qubit, we provide a general method of constructing UPB in ${{C}^{d}}\otimes {{C}^{d}}\otimes {{C}^{d}}$ of size ${{\left( d-1 \right)}^{3}}+3\left( d-2 \right)+1$. Second, for the more general case where the dimensions of qubits are different, we extend the tile structure to 3-qubit system and propose a Tri-tile structure for 3-qubit UPB. Then, by means of this structure, a ${{C}^{4}}\otimes {{C}^{4}}\otimes {{C}^{5}}$ system of size 30 is obtained based on a ${{C}^{3}}\otimes {{C}^{3}}\otimes {{C}^{4}}$ system. Similarly, we generalize this approach to ${{C}^{{{d}_{1}}}}\otimes {{C}^{{{d}_{2}}}}\otimes {{C}^{{{d}_{3}}}}$ system which has a similar composition to ${{C}^{d}}\otimes {{C}^{d}}\otimes {{C}^{d}}$. Our research provides a positive answer to the open questions raised in [Halder, et al., PRL, 122, 040403 (2019)], indicating that there do exist multi-qubit UPBs that can exhibit strong quantum nonlocality without entanglement.

arXiv:2106.08699•Jun 16, 2021•2 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

New results on unextendible product bases

Yiwei Zhang, Fei Shi, Xiande Zhang +2 more

Unextendible product bases (UPB) is an important concept and has extensive applications in various fields of quantum information theory. The construction of UPBs is closely related to combinatorics. Alon and Lovász (2001) first used a series of graph theoretic tools to characterize the necessary and sufficient conditions when the size of a UPB can attain the trivial lower bound. Later Feng (2006) brought the 1-factorization of graphs into the study of UPBs. In this paper, we further apply some graph theoretic tools to analyze the minimum size of a UPB under certain parameters and obtain a series of new results. Moreover, we have an almost complete characterization of all the potential sizes of UPBs in $\mathbb{C}^2\otimes\mathbb{C}^2\otimes\mathbb{C}^k$.

Scientia Sinica Mathematica•Aug 20, 2021•1 citation
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.
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.
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.
The unextendible product bases (UPBs) are interesting members from the family of orthogonal product states. In this paper, we investigate the construction of 3-qubit UPB with strong nonlocality of different sizes. First, a UPB set in C3⊗C3⊗C3{{C}^{3}}\otimes {{C}^{3}}\otimes {{C}^{3}}C3⊗C3⊗C3 of size 12 is presented based on the Shifts UPB, the structure of which is described by mapping the system to a 3×3×33\times 3\times 33×3×3 Rubik's Cube. After observing the orthogonal graph of each qubit, we provide a general method of constructing UPB in Cd⊗Cd⊗Cd{{C}^{d}}\otimes {{C}^{d}}\otimes {{C}^{d}}Cd⊗Cd⊗Cd of size (d−1)3+3(d−2)+1{{\left( d-1 \right)}^{3}}+3\left( d-2 \right)+1(d−1)3+3(d−2)+1. Second, for the more general case where the dimensions of qubits are different, we extend the tile structure to 3-qubit system and propose a Tri-tile structure for 3-qubit UPB. Then, by means of this structure, a C4⊗C4⊗C5{{C}^{4}}\otimes {{C}^{4}}\otimes {{C}^{5}}C4⊗C4⊗C5 system of size 30 is obtained based on a C3⊗C3⊗C4{{C}^{3}}\otimes {{C}^{3}}\otimes {{C}^{4}}C3⊗C3⊗C4 system. Similarly, we generalize this approach to Cd1⊗Cd2⊗Cd3{{C}^{{{d}_{1}}}}\otimes {{C}^{{{d}_{2}}}}\otimes {{C}^{{{d}_{3}}}}Cd1​⊗Cd2​⊗Cd3​ system which has a similar composition to Cd⊗Cd⊗Cd{{C}^{d}}\otimes {{C}^{d}}\otimes {{C}^{d}}Cd⊗Cd⊗Cd. Our research provides a positive answer to the open questions raised in [Halder, et al., PRL, 122, 040403 (2019)], indicating that there do exist multi-qubit UPBs that can exhibit strong quantum nonlocality without entanglement.
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.
Unextendible product bases (UPB) is an important concept and has extensive applications in various fields of quantum information theory. The construction of UPBs is closely related to combinatorics. Alon and Lovász (2001) first used a series of graph theoretic tools to characterize the necessary and sufficient conditions when the size of a UPB can attain the trivial lower bound. Later Feng (2006) brought the 1-factorization of graphs into the study of UPBs. In this paper, we further apply some graph theoretic tools to analyze the minimum size of a UPB under certain parameters and obtain a series of new results. Moreover, we have an almost complete characterization of all the potential sizes of UPBs in C2⊗C2⊗Ck\mathbb{C}^2\otimes\mathbb{C}^2\otimes\mathbb{C}^kC2⊗C2⊗Ck.