For an incomplete set of mutually orthogonal product states in a multipartite Hilbert space, the normalized projector onto the orthogonal complement is positive under partial transposition, so it is either separable or bound entangled. DiVincenzo, Mor, Shor, Smolin and Terhal (Commun. Math. Phys. 238, 379 (2003)) proved that every uncompletable product basis can be augmented with further orthogonal product states until the complementary projector becomes bound entangled, and asked whether this augmentation is ever necessary: in particular, whether the complementary projector of a strongly uncompletable product basis that is not an unextendible product basis is always bound entangled. The same paper also leaves open the accompanying cut-wise question: whether the complementary bound entangled states of its specific multipartite constructions — the GenShifts bases and the seven-state pyramid construction 'Sept' — are separable across the relevant bipartite cuts, or bound entangled across them.

Background

In a multipartite Hilbert space H=H1⊗⋯⊗Hm\mathcal{H}=\mathcal{H}_1\otimes\cdots\otimes\mathcal{H}_m, a pure state is a product state if it factorizes as ∣a1⟩⊗⋯⊗∣am⟩|a_1\rangle\otimes\cdots\otimes|a_m\rangle. A set S={∣ψi⟩}i=1kS=\{|\psi_i\rangle\}_{i=1}^{k} of mutually orthogonal product states is called an (incomplete) product basis, or PB; its span is a proper subspace HS\mathcal{H}_S. The object of interest is the normalized projector onto the orthogonal complement, ρˉS=1D−k(I−∑i=1k∣ψi⟩⟨ψi∣),D=dim⁡H,\bar{\rho}_S=\frac{1}{D-k}\Big(I-\sum_{i=1}^{k}|\psi_i\rangle\langle\psi_i|\Big),\qquad D=\dim\mathcal{H}, which is always positive under partial transposition (PPT: the matrix obtained by transposing one party's factor remains positive semidefinite). By the Peres–Horodecki criterion separable states are PPT, and PPT entangled states exist (Horodecki 1997); since distillable entanglement between two parties requires a non-PPT state across their cut, PPT entangled states are bound entangled — entangled yet no pure entanglement can be extracted from them by local operations and classical communication (LOCC).

A PB is completable if it can be extended to a full orthogonal product basis of H\mathcal{H}; it is an uncompletable product basis (UCPB) otherwise, and strongly uncompletable (SUCPB) if it cannot be completed to a full product basis even in any locally extended Hilbert space Hext=⨂i(Hi⊕Hi′)\mathcal{H}_{\mathrm{ext}}=\bigotimes_i(\mathcal{H}_i\oplus\mathcal{H}_i') in which one or more local factors are enlarged. An unextendible product basis (UPB), introduced by Bennett, DiVincenzo, Mor, Shor, Smolin and Terhal (1999), is a PB whose orthogonal complement contains no product vector at all; its complementary projector ρˉ\bar{\rho} is PPT entangled and hence bound entangled, which was the first systematic construction of bound entangled states from purely combinatorial data. DiVincenzo, Mor, Shor, Smolin and Terhal (2003) organized the known relations into an implication network: a completable PB has separable ρˉS\bar{\rho}_S; a UPB is strongly uncompletable; strong uncompletability forbids perfect discrimination of the members by local operations and classical communication; and (their Lemma 3) for every UCPB SS there exists a possibly empty set of mutually orthogonal product states that can be added to SS so that the complementary projector of the augmented set becomes bound entangled. The question left open sits exactly at the one missing arrow of this network. Their running example in 3⊗43\otimes4, the set Pyr34, is uncompletable but not strongly uncompletable and has a separable — although not orthogonally product-decomposable — complement; adjoining one product state gives Pyr34+, a strongly uncompletable set that is not a UPB and whose complement is bound entangled.

In the multipartite setting the complement of a UPB is PPT across every bipartite cut of the parties and therefore bound entangled overall, but its cut-wise separability structure can vary. Because any PB in 2⊗n2\otimes n is completable (Theorem 4 of the 2003 paper), the complement of the minimal three-qubit 'Shifts' UPB is separable across every cut separating one qubit from the other two — the entanglement is 'delocalized' — while remaining entangled; the generalization GenShifts to 2k−12k-1 qubits and the seven-state pyramid construction 'Sept' in 3⊗3⊗33\otimes3\otimes3 are the constructions whose cut-wise structure the source paper could not determine. The same paper introduced the orthogonality graph (vertices are the product states, edges join orthogonal pairs, edge color records the party on which orthogonality holds) and used it to classify UPBs completely in 3⊗33\otimes3; the graph-theoretic classification beyond that case, and the entanglement resources needed to physically implement separable superoperators (operations whose Kraus elements are tensor products of local operators, a class strictly between LOCC and general quantum operations), are further open questions of the same paper that lie outside the objective of this task.

Problem Statement

Let SS be a set of mutually orthogonal product states on a multipartite Hilbert space that is strongly uncompletable — it cannot be completed to a full orthogonal product basis even after enlarging any of the local Hilbert spaces — but is not an unextendible product basis, so its orthogonal complement does contain product vectors. The central question, as posed by DiVincenzo, Mor, Shor, Smolin and Terhal (2003): is the normalized projector ρˉS\bar{\rho}_S onto the orthogonal complement of the span of SS always bound entangled (entangled and positive under partial transposition, hence undistillable), or does there exist such a strongly uncompletable, non-unextendible product basis whose complementary projector is separable, so that one must genuinely add further mutually orthogonal product states to SS — as Lemma 3 of that paper guarantees is possible — before the complementary projector becomes bound entangled? In other words, is strong uncompletability of a product basis by itself a sufficient condition for bound entanglement of the complementary state, or is it strictly weaker than unextendibility in this respect?

As part of the same objective of characterizing how uncompletability, globally and across bipartite cuts of the parties, is reflected in the entanglement of the complementary projector, the problem also asks, in the generality in which the source stated it: for the multipartite constructions of the same paper — the GenShifts bases on 2k−12k-1 qubits and the seven-state pyramid basis 'Sept' on C3⊗C3⊗C3\mathbb{C}^3\otimes\mathbb{C}^3\otimes\mathbb{C}^3 — whether their complementary bound entangled states are separable across bipartite cuts with two or more parties on each side (for ρˉSept\bar{\rho}_{\mathrm{Sept}}, across the bipartite cuts in general), or bound entangled across such cuts. This objective concerns the complementary projector of a single product basis and its cut-wise entanglement structure; which bipartite regroupings of a multipartite unextendible product basis yield uncompletable bipartite product bases, in particular when the grouped local dimensions exceed 2, is a further open question of the same paper that lies outside this objective, and its existence form has already been settled by other constructions.

References

  1. D. P. DiVincenzo, T. Mor, P. W. Shor, J. A. Smolin, B. M. Terhal (2003), 'Unextendible Product Bases, Uncompletable Product Bases and Bound Entanglement', Communications in Mathematical Physics 238, 379–410, DOI 10.1007/s00220-003-0877-6, https://doi.org/10.1007/s00220-003-0877-6 (arXiv:quant-ph/9908070, https://arxiv.org/abs/quant-ph/9908070).
  2. C. H. Bennett, D. P. DiVincenzo, T. Mor, P. W. Shor, J. A. Smolin, B. M. Terhal (1999), 'Unextendible Product Bases and Bound Entanglement', Physical Review Letters 82, 5385–5388, DOI 10.1103/PhysRevLett.82.5385, https://doi.org/10.1103/PhysRevLett.82.5385.
  3. P. Horodecki (1997), 'Separability criterion and inseparable mixed states with positive partial transposition', Physics Letters A 232, 333–339, DOI 10.1016/S0375-9601(97)00416-7, https://doi.org/10.1016/S0375-9601(97)00416-7.
  4. D. P. DiVincenzo, B. M. Terhal (2000), 'Product Bases in Quantum Information Theory', arXiv:quant-ph/0008055, https://arxiv.org/abs/quant-ph/0008055.
  5. S. Halder, R. Sengupta (2018), 'Construction of noisy bound entangled states and the range criterion', arXiv:1808.00294, https://arxiv.org/abs/1808.00294.
  6. P. Bej, S. Halder (2021), 'Unextendible product bases, bound entangled states, and the range criterion', Physics Letters A, DOI 10.1016/j.physleta.2020.126992, https://doi.org/10.1016/j.physleta.2020.126992 (arXiv:2005.02108, https://arxiv.org/abs/2005.02108).
  7. L. Chen, D. Z. Djokovic (2018), 'Multiqubit UPB: The method of formally orthogonal matrices', arXiv:1801.08677, https://arxiv.org/abs/1801.08677.
  8. A. Acín, M. L. Almeida, R. Augusiak, N. Brunner (2012), 'Guess your neighbour's input: no quantum advantage but an advantage for quantum theory', arXiv:1205.3076, https://arxiv.org/abs/1205.3076 (published as a chapter in 'Quantum Theory: Informational Foundations and Foils', Fundamental Theories of Physics, Springer, 2015, pp. 465–496, DOI 10.1007/978-94-017-7303-4_14, https://doi.org/10.1007/978-94-017-7303-4_14).
  9. M. Demianowicz, R. Augusiak (2018), 'From unextendible product bases to genuinely entangled subspaces', Physical Review A 98, 012313, DOI 10.1103/PhysRevA.98.012313, https://doi.org/10.1103/PhysRevA.98.012313 (arXiv:1712.08916, https://arxiv.org/abs/1712.08916).
  10. M. Demianowicz (2022), 'Negative result about the construction of genuinely entangled subspaces from unextendible product bases', Physical Review A 106, 012442, DOI 10.1103/PhysRevA.106.012442, https://doi.org/10.1103/PhysRevA.106.012442 (arXiv:2202.08356, https://arxiv.org/abs/2202.08356).
  11. M. Demianowicz (2026), 'Progress in the study of the (non)existence of genuinely unextendible product bases', International Journal of Theoretical Physics, DOI 10.1007/s11128-026-05072-w, https://doi.org/10.1007/s11128-026-05072-w (arXiv:2509.26135, https://arxiv.org/abs/2509.26135).
  12. F. Shi, M.-S. Li, X. Zhang, Q. Zhao (2022), 'Unextendible and uncompletable product bases in every bipartition', New Journal of Physics 24, 113025, DOI 10.1088/1367-2630/ac9e14, https://doi.org/10.1088/1367-2630/ac9e14 (arXiv:2207.04763, https://arxiv.org/abs/2207.04763).
  13. X.-F. Zhen, H.-J. Zuo, F. Shi, S.-M. Fei (2024), 'Unextendible and strongly uncompletable product bases', Journal of Mathematical Physics 65, 112201, DOI 10.1063/5.0195550, https://doi.org/10.1063/5.0195550 (arXiv:2411.18036, https://arxiv.org/abs/2411.18036).
  14. F. Shi, G. Bai, X. Zhang, Q. Zhao, L. Li (2026), 'A Minimum-Cardinality Genuinely Unextendible Product Basis in Three Qutrits', arXiv:2608.12785, https://arxiv.org/abs/2608.12785.
  15. M.-S. Li (2026), 'Genuinely Unextendible Product Bases from Maximum Distance Separable Codes', arXiv:2608.09504, https://arxiv.org/abs/2608.09504.