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:2609.14788

Systematic construction of multiqubit unextendible product bases

Caohan Cheng, Lin Chen

quant-phSubmitted Sep 13, 2026• Announced Sep 15, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Related papers

The construction and local distinguishability of multiqubit unextendible product bases

Yize Sun, Lin Chen

An important problem in quantum information is to construct multiqubit unextendible product bases (UPBs). By using the unextendible orthogonal matrices, we construct a 7-qubit UPB of size 11. It solves an open problem in [Quantum Information Processing 19:185 (2020)]. Next, we graph-theoretically show that the UPB is locally indistinguishable in the bipartite systems of two qubits and five qubits, respectively. It turns out that the UPB corresponds to a complete graph with 11 vertices constructed by three sorts of nonisomorphic graphs. Taking the graphs as product vectors, we show that they are in three different orbits up to local unitary equivalence. Moreover, we also present the number of sorts of nonisomorphic graphs of complete graphs of some known UPBs and their orbits.

arXiv:2102.11553•Feb 23, 2021•1 citation

Multiqubit UPB: the method of formally orthogonal matrices

Lin Chen, Dragomir Ž. Djoković

Abstract We use formal matrices whose entries we view as vector variables taking unit vector values in one-qubit Hilbert spaces of a multiqubit quantum system. We construct many unextendible product bases (UPBs) of new sizes in such systems and provide a new construction of UPBs of n qubits of cardinality n + 1 when . We also give a new method of constructing multiqubit entangled states with all partial transposes positive.

arXiv:1801.08677•Journal of Physics A Mathematical and Theoretical•May 16, 2018•12 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

The construction of multiqubit unextendible product bases

Caohan Cheng, Lin Chen

The unextendible orthogonal matrices (UPBs) can be used for various problems in quantum information. We provide an algorithm to check if two UPBs are non-equivalent to each other. We give a method to construct UPBs and we apply this method to find all $5$-qubit UPBs of size eight. We apply the algorithm to check if the $5$-qubit UPBs of size eight are non-equivalent to each other. Based on all the $5$-qubit UPBs of size eight, we propose a theorem for constructing a new UPB non-equivalent to a given one.

arXiv:2402.11785•Feb 19, 2024•0 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

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
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.
An important problem in quantum information is to construct multiqubit unextendible product bases (UPBs). By using the unextendible orthogonal matrices, we construct a 7-qubit UPB of size 11. It solves an open problem in [Quantum Information Processing 19:185 (2020)]. Next, we graph-theoretically show that the UPB is locally indistinguishable in the bipartite systems of two qubits and five qubits, respectively. It turns out that the UPB corresponds to a complete graph with 11 vertices constructed by three sorts of nonisomorphic graphs. Taking the graphs as product vectors, we show that they are in three different orbits up to local unitary equivalence. Moreover, we also present the number of sorts of nonisomorphic graphs of complete graphs of some known UPBs and their orbits.
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 orthogonal matrices (UPBs) can be used for various problems in quantum information. We provide an algorithm to check if two UPBs are non-equivalent to each other. We give a method to construct UPBs and we apply this method to find all 555-qubit UPBs of size eight. We apply the algorithm to check if the 555-qubit UPBs of size eight are non-equivalent to each other. Based on all the 555-qubit UPBs of size eight, we propose a theorem for constructing a new UPB non-equivalent to a given one.
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.
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.