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
ON-tile decompositions and prove a tile-to-UPB theorem: every
ON-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,…,23 in
C3⊗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 existence of genuinely unextendible product bases (GUPBs), incomplete orthogonal sets of fully product states whose orthogonal complements contain no product vector across any bipartition, has remained an open problem. Here we construct GUPBs for any number
N≥3 of parties using classical maximum distance separable (MDS) codes. The MDS property imposes a rigidity on the induced product tiling across every bipartition; combined with Fourier mode deletion and a stopper state, this rigidity enforces genuine unextendibility. Consequently, the orthogonal complement of each GUPB is a genuinely entangled subspace whose normalized projector is invariant under partial transposition across every bipartition, yielding an explicit family of multipartite bound entangled states. We further construct GME witnesses that detect these states even though no fully decomposable witness can do so. Moreover, the resulting indistinguishability persists under arbitrary finite tensor powers and measurements separable across any bipartition. These results establish a direct connection between error-correcting codes and multipartite entanglement and provide an algebraic route to certifying genuinely multipartite bound entanglement.