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

arXiv:2608.01438

Automated Construction and Verification of Unextendible Product Bases

Zicheng Han, Wanchen Zhang, Fei Shi, Xiande Zhang

quant-phSubmitted Aug 2, 2026• Announced Aug 4, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
19 pages,2 figures

Related papers

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

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

Systematic construction of multiqubit unextendible product bases

Caohan Cheng, Lin Chen

The construction of multiqubit unextendible product bases (UPBs) has been a long-standing problem. We give a systematic construction of multiqubit UPBs by studying their unextendible orthogonal matrices (UOMs) with graph-theoretic methods. Row decompositions of small UOMs produce the main intervals. Com- pletion graphs settle the remaining small UPB sizes, except for one size obtained from a good column structure. Nonexistence of the other UPB sizes follows from counts of fibres and row pairs. The computer is used only for a few finite UOM checks, whose exact tests are stated in the certificate appendix. These arguments determine the complete multiqubit UPB size spectrum in every dimension.

quant-pharXiv:2609.14788•Sep 15, 2026•0 citations

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

Negative result about the construction of genuinely entangled subspaces from unextendible product bases

Maciej Demianowicz

Unextendible product bases (UPBs) provide a versatile tool with various applications across different areas of quantum information theory. Their comprehensive characterization is thus of great importance and has been a subject of vital interest for over two decades now. An open question asks about the existence of UPBs, which are genuinely unextendible, i.e., they are not extendible even with biproduct vectors. In other words, the problem is to verify whether there exist genuinely entangled subspaces (GESs), subspaces composed solely of genuinely multiparty entangled states, complementary to UPBs. We solve this problem in the negative for many sizes of UPBs in different multipartite scenarios. In particular, in the all-important case of equal local dimensions, we show that there are always forbidden cardinalities for such UPBs, including the minimal ones corresponding to GESs of the maximal dimensions.

arXiv:2202.08356•Physical Review A•Jul 29, 2022•6 citations

Minimum Cardinalities of Multipartite Unextendible Product Bases

Chenhao Wang

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}\otimes\cdots\otimes\C^{d_p}$, a nonzero vector is a \emph{product state} if it can be written as $\ket{\varphi_1}\otimes\cdots\otimes\ket{\varphi_p}$ with $\ket{\varphi_j}\in\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. Let $f_m(d_1,\ldots,d_p)$ be the minimum cardinality of a UPB in the space, 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 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,\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 size problem for UPBs in all finite quantum systems.

quant-pharXiv:2609.05657•Sep 8, 2026•0 citations
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.
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.
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.
The construction of multiqubit unextendible product bases (UPBs) has been a long-standing problem. We give a systematic construction of multiqubit UPBs by studying their unextendible orthogonal matrices (UOMs) with graph-theoretic methods. Row decompositions of small UOMs produce the main intervals. Com- pletion graphs settle the remaining small UPB sizes, except for one size obtained from a good column structure. Nonexistence of the other UPB sizes follows from counts of fibres and row pairs. The computer is used only for a few finite UOM checks, whose exact tests are stated in the certificate appendix. These arguments determine the complete multiqubit UPB size spectrum in every dimension.
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) provide a versatile tool with various applications across different areas of quantum information theory. Their comprehensive characterization is thus of great importance and has been a subject of vital interest for over two decades now. An open question asks about the existence of UPBs, which are genuinely unextendible, i.e., they are not extendible even with biproduct vectors. In other words, the problem is to verify whether there exist genuinely entangled subspaces (GESs), subspaces composed solely of genuinely multiparty entangled states, complementary to UPBs. We solve this problem in the negative for many sizes of UPBs in different multipartite scenarios. In particular, in the all-important case of equal local dimensions, we show that there are always forbidden cardinalities for such UPBs, including the minimal ones corresponding to GESs of the maximal dimensions.
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}\otimes\cdots\otimes\C^{d_p}$, a nonzero vector is a \emph{product state} if it can be written as ∣φ1⟩⊗⋯⊗∣φp⟩\ket{\varphi_1}\otimes\cdots\otimes\ket{\varphi_p}∣φ1​⟩⊗⋯⊗∣φp​⟩ with $\ket{\varphi_j}\in\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. Let fm(d1,…,dp)f_m(d_1,\ldots,d_p)fm​(d1​,…,dp​) be the minimum cardinality of a UPB in the space, and let fLB(d1,…,dp)=1+∑j=1p(dj−1)f_{LB}(d_1,\ldots,d_p)=1+\sum_{j=1}^{p}(d_j-1)fLB​(d1​,…,dp​)=1+∑j=1p​(dj​−1) be the natural lower bound. Alon and Lovász determined exactly when fmf_mfm​ attains the lower bound fLBf_{LB}fLB​, but the obstructed multipartite cases remained open in general. We prove a stabilization theorem: for every non-all-qubit system with p≥3p\ge3p≥3, whenever the natural lower bound fLBf_{LB}fLB​ is unattainable, the true minimum is exactly fLB+1f_{LB}+1fLB​+1. Precisely, if the number of even local dimensions did_idi​ is positive and even, and at least one local dimension is greater than two, then fm(d1,…,dp)=fLB(d1,…,dp)+1f_m(d_1,\ldots,d_p)=f_{LB}(d_1,\ldots,d_p)+1fm​(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.