REVIEW 1 major objections 4 minor 39 references
Automated Construction and Verification of Unextendible Product Bases
T0 review · 1 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read A partition of a finite hypercube into non-combinable tiles always induces an unextendible product basis of known size.
desk verdict Solid tile-to-UPB theorem with a believable SAT pipeline; the remaining work is making the Appendix B decompositions independently checkable. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the $O_N$-tile decomposition: a partition of the $N$-cube $C=Z_{d_1}\times\cdots\times Z_{d_N}$ into tiles $t_j=R_1^{(j)}\times\cdots\times R_N^{(j)}$ with the non-combinability condition that every proper sub-union of tiles (with between 2 and $s-1$ members) fails to be a Cartesian product. The construction assigns each tile a Fourier product basis of its supported subspace, removes the all-zero Fourier vector $|\eta_j\rangle$ from each tile, and appends the global stopper $|S\rangle$; the stopper overlaps a tile-wise Fourier product state only when all local Fourier frequencies are zero. The non-combinability condition forces any product state orthogonal to the c
What would settle it
Enumerate every subset $J$ of tiles in each Appendix B decomposition with $2\le |J|\le s-1$ and test whether $\bigcup_{j\in J} t_j$ is a Cartesian product $A\times B\times C$; if any such union exists, the corresponding claimed UPB size is not established by Theorem 1. As an independent check, the paper's exact verification algorithm, run on the supplied symbolic product states, would return False for any set that is not actually a UPB.
Extended reading notes
Core claim
The paper's central claim is Theorem 1 (tile-to-UPB): if $C=Z_{d_1}\times\cdots\times Z_{d_N}$ is a disjoint union of $s\ge 3$ Cartesian-product tiles $t_j$ such that no union of a proper subset of tiles with at least two members is itself a Cartesian product, then the set $U$ built from tile-wise Fourier product bases, deleting each tile's all-zero Fourier vector and adding the global stopper $|S\rangle=\bigotimes_i\sum_{r\in Z_{d_i}}|r\rangle$, is a UPB of cardinality $\prod_i d_i - s + 1$. Theorem 2 is the computational companion: a SAT search found $O_3$-tile decompositions of $Z_3^3$ with $s=5,\ldots,15$ tiles, producing UPBs of every size $13,\ldots,23$ in $\mathbb{C}^3\otimes\mathbb{C
Load-bearing premise
The claimed sizes 13–23 in $\mathbb{C}^3\otimes\mathbb{C}^3\otimes\mathbb{C}^3$ rest on the Appendix B tile lists being genuine $O_3$-tile decompositions; the paper depends on the SAT solver's output and its transcription into the appendix, without machine-checkable certificates for the non-combinability condition.
Editorial extensions
If this is right
- UPBs of every size between 13 and 23 exist in $\mathbb{C}^3\otimes\mathbb{C}^3\otimes\mathbb{C}^3$, including the previously known size 19; sizes 8–12 remain open.
- Every such UPB yields, via its orthogonal complement, a completely entangled subspace, and the normalized projector onto that complement gives a bound entangled state.
- Combined with the direct-sum lemma cited as [24], the small instances seed infinite families: for $d=2x+3y$ and $a\in A$, $b\in B$, a UPB of size $ax+by$ exists in $\mathbb{C}^3\otimes\mathbb{C}^3\otimes\mathbb{C}^d$.
- The verification algorithm is exact for arbitrary finite sets of multipartite product states, not only tile-induced sets, and its running time stays under a second on the benchmarked instances.
- Solving the same SAT formulation for other cubes would automatically produce UPBs of the corresponding sizes, making the pipeline a general tool for the prescribed-size UPB problem.
Reading between the lines
- The $O_N$-tile condition is sufficient but likely not necessary for a UPB: product bases built from other mechanisms may realize sizes that no tiling realizes, so a failed SAT search should not be read as non-existence of a UPB.
- Extending the same SAT pipeline to larger cubes (e.g. $Z_4^3$ or $Z_3^4$) could enumerate further attainable sizes, with the main bottleneck being the number of non-combinability clauses.
- The maximal-unsaturated-set enumeration in the verifier suggests a compact certificate format: a small family of MUSs proving that no $N$-tuple of unsaturated sets covers all indices.
- Because these UPBs have a highly structured form—Fourier product bases per tile plus one stopper—they may also serve as natural probes for local distinguishability and strong nonlocality, though the paper only gestures toward recursive applications.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript introduces a SAT-assisted method for constructing unextendible product bases (UPBs) from decompositions of the N-dimensional grid Z_{d1}×...×Z_{dN}. It defines O_N-tile decompositions and proves Theorem 1: any such decomposition with s tiles yields, via tile-wise Fourier product bases and a global stopper state, a UPB of cardinality ∏d_i − s + 1. It then encodes the search for O_3-tile decompositions of Z_3^3 as a SAT problem, implements an exact UPB verifier based on local orthogonality graphs and maximal unsaturated sets, and reports eleven explicit decompositions with s=5,...,15 tiles. Combining Theorem 1 with these lists, the paper claims UPBs of every size 13 through 23 in C^3⊗C^3⊗C^3, together with additional sizes in other tripartite and quadripartite systems. The data and code are deposited in Zenodo.
Significance. If the computational claims are correct, Theorem 1 is a clean and useful reduction: it converts a class of UPB existence problems into finite combinatorial tiling problems, and the SAT encoding is logically faithful to Definition 2. The proof of Theorem 1 is self-contained and rigorous, and the verification algorithm based on maximal unsaturated sets is a simple, exact tool. The reported new sizes 13–23 in C^3⊗C^3⊗C^3 would substantially improve the previously known set {7,19} for that system. The explicit appendix lists, the permanent data DOI, and the source code are concrete reproducibility assets. The main weakness is that the proof of Theorem 2 currently relies on external certificates for the O_3-tile condition, rather than on in-text machine-checkable verification of the Appendix B lists.
major comments (1)
- [§5.1, Theorem 2; Appendix B] The new cardinalities 13–23 in C^3⊗C^3⊗C^3 are obtained by applying Theorem 1 to the eleven O_3-tile decompositions listed in Appendix B. The O_N condition in Definition 2 requires, for each s, that the union of every proper subset J with 2≤|J|≤s−1 is not a Cartesian product. The appendix lists only the tile sets; the paper does not contain a machine-checkable verification of this condition for any of the eleven lists. The sentence 'the SAT encoding produces O_3-tile decompositions' asserts correctness, and the certificates are relegated to the external Zenodo archive. A single transcription or solver error in one list would silently destroy the corresponding claimed UPB size. Since this is the load-bearing computational step, please include in the paper (or in a supplementary file that is part of the reviewed manuscript) a certificate or a short verification script that checks Definitio
minor comments (4)
- [§2.3, Proof of Theorem 1] The phrase 'By Definition 2, |I|=1' is compressed. A reader must supply the argument that any other cardinality of I would already contradict Definition 2, and then that the complementary union of s−1 tiles yields the final contradiction. Consider spelling out this two-step reasoning explicitly.
- [§5.1, Table 2] The unmarked entries in Table 2 claim new UPB sizes in several tripartite and quadripartite systems, but only the C^3⊗C^3⊗C^3 decompositions are listed in Appendix B. The other unmarked entries are not proved in the text and are supported only by the external data archive. Please clarify which entries are theorems proved in the paper and which are data-supported claims verified in the Zenodo repository.
- [§3.2.3, Eq. (23)] The quantity N_B counts pairs (T,P) with T a nontrivial Cartesian product and P∈T, not the number of Cartesian products T. The text says this immediately before the formula, but the notation could be misread; a brief sentence restating the counting convention would help.
- [Appendix B] Each listed tile should be checked for admissibility (at least two proper coordinates) as part of the O_3 verification. This is implicit in Definition 2 but is not stated in the appendix; adding it to the verification certificate would make the check self-contained.
Circularity Check
No significant circularity: the tile-to-UPB theorem is self-contained, and the claimed UPB sizes follow from explicit O_3-tile decompositions via a proved implication rather than from fitted targets. Only a minor, non-load-bearing self-citation is present.
full rationale
The central derivation is Theorem 1: it proves that any O_N-tile decomposition induces a UPB of cardinality ∏d_i − s + 1 via tile-wise Fourier product bases and a stopper state. This is a genuine mathematical implication; the O_N-tile condition is defined independently and the proof does not assume the existence of the resulting UPB. The cardinality formula is a direct count, not a fitted relation. Theorem 2 then relies on the SAT search producing O_3-tile decompositions with s=5,…,15 tiles, listed in Appendix B; the cardinalities 13–23 are obtained as 27−s+1. This is a constructive search for decompositions, not a retrofitted prediction: each s is chosen to correspond to a desired cardinality, but the actual existence of the decomposition is the non-circular input. The only self-citation with overlapping authorship is Lemma 1, taken from the authors' prior work [33] and used in the optional verification algorithm in Section 4. That lemma is not used to prove Theorem 1 or Theorem 2; Theorem 2's proof cites Theorem 1 and the Appendix B decompositions, and the verifier is additionally benchmarked against the external QETLAB function. The paper's reliance on SAT solver output and Appendix B lists is a completeness/verification concern (the decompositions are not machine-checked inside the manuscript), but this is an issue of certifying computational results, not circularity. Consequently, the central claims are self-contained, and the only notable issue is a minor, non-load-bearing self-citation, reflected in the low score.
Assumptions & free parameters
assumptions (5)
- standard math Fourier vectors {Σ ω^{aℓ}|rℓ⟩} form an orthogonal basis of each local support (standard property of the discrete Fourier transform).
- domain assumption Alon-Lovász bound and its tightness criterion for UPB cardinalities (Theorem in Ref [23]).
- domain assumption Lemma 1 from Shi et al. [33]: a product-state set is a UPB iff local orthogonality graphs union to a complete graph and the vertex set is not covered by unsaturated sets.
- domain assumption Lemma 2 from Feng [24]: combining UPBs in appended local dimensions yields a UPB of summed size.
- domain assumption The SAT solver is sound and complete for the generated CNF formulas.
Cite this review
Pith. "Pith review of Automated Construction and Verification of Unextendible Product Bases." pith.science (2026). https://pith.science/paper/7L7KNTVR
@misc{pith2026260801438,
author = {Pith},
title = {Pith review of: Automated Construction and Verification of Unextendible Product Bases},
year = {2026},
howpublished = {\url{https://pith.science/paper/7L7KNTVR}},
note = {Machine review of arXiv:2608.01438}
}
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.
Figures
Reference graph
Works this paper leans on
-
[1]
Quantum entanglement.Re- views of Modern Physics, 81(2):865–942, 2009
Ryszard Horodecki, Pawe l Horodecki, Micha l Horodecki, and Karol Horodecki. Quantum entanglement.Re- views of Modern Physics, 81(2):865–942, 2009
work page 2009
-
[2]
Charles H Bennett, Gilles Brassard, Claude Cr´ epeau, Richard Jozsa, Asher Peres, and William K Wootters. Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels.Physical Review Letters, 70(13):1895, 1993
work page 1993
-
[3]
Quantum cryptography based on bell’s theorem.Physical Review Letters, 67(6):661, 1991
Artur K Ekert. Quantum cryptography based on bell’s theorem.Physical Review Letters, 67(6):661, 1991
work page 1991
-
[4]
Detecting quantum entanglement.Theoretical Computer Science, 287(1):313–335, 2002
Barbara M Terhal. Detecting quantum entanglement.Theoretical Computer Science, 287(1):313–335, 2002
work page 2002
-
[5]
Classical complexity and quantum entanglement.Journal of Computer and System Sciences, 69(3):448–484, 2004
Leonid Gurvits. Classical complexity and quantum entanglement.Journal of Computer and System Sciences, 69(3):448–484, 2004
2004
-
[6]
Sevag Gharibian. Strong np-hardness of the quantum separability problem.Quantum Information and Com- putation, 10(3):343–360, 2010
work page 2010
-
[7]
Quantum entanglement in neural network states.Physical Review X, 7(2):021021, 2017
Dong-Ling Deng, Xiaopeng Li, and S Das Sarma. Quantum entanglement in neural network states.Physical Review X, 7(2):021021, 2017
work page 2017
-
[8]
Separability-entanglement classifier via machine learning.Physical Review A, 98(1):012315, 2018
Sirui Lu, Shilin Huang, Keren Li, Jun Li, Jianxin Chen, Dawei Lu, Zhengfeng Ji, Yi Shen, Duanlu Zhou, and Bei Zeng. Separability-entanglement classifier via machine learning.Physical Review A, 98(1):012315, 2018
2018
Show all 39 references
-
[9]
Entanglement classification via neural network quantum states.New Journal of Physics, 22(4):045001, 2020
Cillian Harney, Stefano Pirandola, Alessandro Ferraro, and Mauro Paternostro. Entanglement classification via neural network quantum states.New Journal of Physics, 22(4):045001, 2020
2020
-
[10]
Unsupervised recognition of informative features via tensor network machine learning and quantum entanglement variations.Chinese Physics Letters, 39(10):100701, 2022
Sheng-Chen Bai, Yi-Cheng Tang, and Shi-Ju Ran. Unsupervised recognition of informative features via tensor network machine learning and quantum entanglement variations.Chinese Physics Letters, 39(10):100701, 2022
2022
-
[11]
Entanglement verification with deep semisupervised machine learning.Physical Review A, 108(2):022427, 2023
Lifeng Zhang, Zhihua Chen, and Shao-Ming Fei. Entanglement verification with deep semisupervised machine learning.Physical Review A, 108(2):022427, 2023
2023
-
[12]
Entanglement structure detection via computer vision.Physical Review A, 110(1):012448, 2024
Rui Li, Junling Du, Zheng Qin, Shikun Zhang, Chunxiao Du, Yang Zhou, and Zhisong Xiao. Entanglement structure detection via computer vision.Physical Review A, 110(1):012448, 2024
2024
-
[13]
Direct entan- glement detection of quantum systems using machine learning.npj Quantum Information, 11(1):29, 2025
Yulei Huang, Liangyu Che, Chao Wei, Feng Xu, Xinfang Nie, Jun Li, Dawei Lu, and Tao Xin. Direct entan- glement detection of quantum systems using machine learning.npj Quantum Information, 11(1):29, 2025
2025
-
[14]
Unextendible product bases and bound entanglement.Physical Review Letters, 82(26):5385, 1999
Charles H Bennett, David P DiVincenzo, Tal Mor, Peter W Shor, John A Smolin, and Barbara M Terhal. Unextendible product bases and bound entanglement.Physical Review Letters, 82(26):5385, 1999
1999
-
[15]
Unextendible product bases, uncompletable product bases and bound entanglement.Communications in Mathematical Physics, 238(3):379–410, 2003
David P DiVincenzo, Tal Mor, Peter W Shor, John A Smolin, and Barbara M Terhal. Unextendible product bases, uncompletable product bases and bound entanglement.Communications in Mathematical Physics, 238(3):379–410, 2003
2003
-
[16]
On the maximal dimension of a completely entangled subspace for finite level quantum systems.Proceedings Mathematical Sciences, 114(4):365–374, 2004
Kalyanapuram Rangachari Parthasarathy. On the maximal dimension of a completely entangled subspace for finite level quantum systems.Proceedings Mathematical Sciences, 114(4):365–374, 2004
2004
-
[17]
From unextendible product bases to genuinely entangled sub- spaces.Physical Review A, 98(1):012313, 2018
Maciej Demianowicz and Remigiusz Augusiak. From unextendible product bases to genuinely entangled sub- spaces.Physical Review A, 98(1):012313, 2018
2018
-
[18]
Completely entangled subspaces of entangle- ment depth k.Physical Review A, 110(1):012403, 2024
Maciej Demianowicz, Kajetan Vogtt, and Remigiusz Augusiak. Completely entangled subspaces of entangle- ment depth k.Physical Review A, 110(1):012403, 2024
2024
-
[19]
Mixed-state entanglement and distillation: Is there a “bound” entanglement in nature?Physical Review Letters, 80(24):5239, 1998
Micha l Horodecki, Pawe l Horodecki, and Ryszard Horodecki. Mixed-state entanglement and distillation: Is there a “bound” entanglement in nature?Physical Review Letters, 80(24):5239, 1998
1998
-
[20]
Quantum nonlocality without entanglement.Physical Review A, 59(2):1070, 1999
Charles H Bennett, David P DiVincenzo, Christopher A Fuchs, Tal Mor, Eric Rains, Peter W Shor, John A Smolin, and William K Wootters. Quantum nonlocality without entanglement.Physical Review A, 59(2):1070, 1999. 18
1999
-
[21]
Bell inequalities with no quantum violation and unextendable product bases.Physical Review Letters, 107(7):070401, 2011
Remigiusz Augusiak, J Stasi´ nska, C Hadley, JK Korbicz, Maciej Lewenstein, and Antonio Ac ´ ın. Bell inequalities with no quantum violation and unextendable product bases.Physical Review Letters, 107(7):070401, 2011
2011
-
[22]
Tight bell inequalities with no quantum violation from qubit unextendible product bases
Remigiusz Augusiak, Tobias Fritz, Marcin Kotowski, Micha l Kotowski, Marcin Paw lowski, Maciej Lewenstein, and Antonio Ac ´ ın. Tight bell inequalities with no quantum violation from qubit unextendible product bases. Physical Review A, 85(4):042113, 2012
2012
-
[23]
Unextendible product bases.Journal of Combinatorial Theory
Noga Alon and L´ aszl´ o Lov´ asz. Unextendible product bases.Journal of Combinatorial Theory. Series A, 95(1):169–179, 2001
2001
-
[24]
Unextendible product bases and 1-factorization of complete graphs.Discrete Applied Mathematics, 154(6):942–949, 2006
Keqin Feng. Unextendible product bases and 1-factorization of complete graphs.Discrete Applied Mathematics, 154(6):942–949, 2006
2006
-
[25]
The minimum size of unextendible product bases in the bipartite case (and some multipartite cases).Communications in Mathematical Physics, 333(1):351–365, 2015
Jianxin Chen and Nathaniel Johnston. The minimum size of unextendible product bases in the bipartite case (and some multipartite cases).Communications in Mathematical Physics, 333(1):351–365, 2015
2015
-
[26]
Genuinely entangled subspace with all-encompassing distillable entanglement across every bipartition.Physical Review A, 99:032335, 2019
Sristy Agrawal, Saronath Halder, and Manik Banik. Genuinely entangled subspace with all-encompassing distillable entanglement across every bipartition.Physical Review A, 99:032335, 2019
2019
-
[27]
Unextendible product bases from tile structures and their local entanglement-assisted distinguishability.Physical Review A, 101(6):062329, 2020
Fei Shi, Xiande Zhang, and Lin Chen. Unextendible product bases from tile structures and their local entanglement-assisted distinguishability.Physical Review A, 101(6):062329, 2020
2020
-
[28]
Unextendible product bases from tile structures in bipartite systems.Journal of Physics A: Mathematical and Theoretical, 56(1):015303, 2023
Siwen You, Chen Wang, Fei Shi, Sihuang Hu, and Yiwei Zhang. Unextendible product bases from tile structures in bipartite systems.Journal of Physics A: Mathematical and Theoretical, 56(1):015303, 2023
2023
-
[29]
Constructing the three-qudit unextendible product bases with strong nonlocality.Chinese Physics B, 31(6):060302, 2022
Bichen Che, Zhao Dou, Xiubo Chen, Yu Yang, Jian Li, and Yixian Yang. Constructing the three-qudit unextendible product bases with strong nonlocality.Chinese Physics B, 31(6):060302, 2022
2022
-
[30]
Strong quantum nonlocality and unextendibility without entanglement inn-partite systems with oddn.Quantum, 8:1349, 2024
Yiyun He, Fei Shi, and Xiande Zhang. Strong quantum nonlocality and unextendibility without entanglement inn-partite systems with oddn.Quantum, 8:1349, 2024
2024
-
[31]
Strongly nonlocal unextendible product bases do exist.Quantum, 6:619, 2022
Fei Shi, Mao-Sheng Li, Mengyao Hu, Lin Chen, Man-Hong Yung, Yan-Ling Wang, and Xiande Zhang. Strongly nonlocal unextendible product bases do exist.Quantum, 6:619, 2022
2022
-
[32]
The structure of qubit unextendible product bases.Journal of Physics A: Mathematical and Theoretical, 47(42):424034, 2014
Nathaniel Johnston. The structure of qubit unextendible product bases.Journal of Physics A: Mathematical and Theoretical, 47(42):424034, 2014
2014
-
[33]
Graph-theoretic characterization of unextendible product bases.Physical Review Research, 5(3):033144, 2023
Fei Shi, Ge Bai, Xiande Zhang, Qi Zhao, and Giulio Chiribella. Graph-theoretic characterization of unextendible product bases.Physical Review Research, 5(3):033144, 2023
2023
-
[34]
Unextendible and strongly uncompletable product bases.Journal of Mathematical Physics, 65(11):112201, 2024
Xiao-Fan Zhen, Hui-Juan Zuo, Fei Shi, and Shao-Ming Fei. Unextendible and strongly uncompletable product bases.Journal of Mathematical Physics, 65(11):112201, 2024
2024
-
[35]
Strong quantum nonlocality for unextendible product bases in heterogeneous systems.Journal of Physics A: Mathematical and Theoretical, 55(1):015305, 2022
Fei Shi, Mao-Sheng Li, Lin Chen, and Xiande Zhang. Strong quantum nonlocality for unextendible product bases in heterogeneous systems.Journal of Physics A: Mathematical and Theoretical, 55(1):015305, 2022
2022
-
[36]
The construction of multiqubit unextendible product bases, 2024
Caohan Cheng and Lin Chen. The construction of multiqubit unextendible product bases, 2024
2024
-
[37]
QETLAB: A MATLAB toolbox for quantum entanglement, version 1.0.https://qetlab
Nathaniel Johnston. QETLAB: A MATLAB toolbox for quantum entanglement, version 1.0.https://qetlab. com, Jan 2016
2016
-
[38]
The minimum size of qubit unextendible product bases
Nathaniel Johnston. The minimum size of qubit unextendible product bases. InProceedings of the 8th Confer- ence on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013), volume 8143 ofLecture Notes in Computer Science, pages 93–105. Springer, New York, 2013
2013
-
[39]
New results on unextendible product bases (in chinese).Scientia Sinica Mathematica, 51(10):1699–1714, 2021
Yiwei Zhang, Fei Shi, Xiande Zhang, Yiting Yang, and Gennian Ge. New results on unextendible product bases (in chinese).Scientia Sinica Mathematica, 51(10):1699–1714, 2021. 19
2021
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.