Minimum Cardinalities of Multipartite Unextendible Product Bases

• URL: http://arxiv.org/abs/2609.05657v1
• Date: Fri, 04 Sep 2026 18:39:49 GMT
• Title: Minimum Cardinalities of Multipartite Unextendible Product Bases
• Abstract summary: In quantum information theory, the state space of a multipartite quantum system is modeled by a tensor product.<n>We prove a stabilization theorem for every non-all-qubit system with $pge3$.
• Score: 5.783726205321144
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In quantum information theory, the state space of a multipartite quantum system is modeled by a tensor product. In the tensor-product space $\mathbb C^{d_1}\otimes\cdots\otimes\mathbb C^{d_p}$, a nonzero vector is a \emph{product state} if it can be written as $\lvert \varphi_1\rangle\otimes\cdots\otimes\lvert \varphi_p\rangle$ with $\lvert \varphi_j\rangle\in\mathbb 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. For local dimensions $d_1,\ldots,d_p\ge2$, let $f_m(d_1,\ldots,d_p)$ be the minimum cardinality of a UPB 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 parity prevents the natural lower bound $f_{LB}$ from being attained, the true minimum is exactly $f_{LB}+1$. Equivalently, if the number of even local dimensions 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-cardinality problem for UPBs in all finite quantum systems.

Related papers

• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• No finite level of the NPA hierarchy is exact for the doubly-tilted CHSH functional near the critical tilt [0.0]
  We prove that for every NPA level $kge 2$ there are an explicit rational $g_k>0$ and an $s*_k>0$ with $c_k(s)ge 4-s+g_k s2$ on $(0,s*_k)$.<n>For $kge 3$ no quantum state and no smooth curve of quantum models can realize the gain direction, so the overshoot lives strictly in the non-quantum part of the NPA cone.
  arXiv  Detail & Related papers  (2026-07-15T12:22:23Z)
• Nonasymptotic bounds for quantum purity amplification [0.9969485010222057]
  In quantum purity amplification, one is given $n$ copies of a noisy quantum state $in mathbbCd times d$ and asked to prepare $k$ copies of its principal eigenstate $|v_drangle$.<n>Several prior works have derived information-theoretically optimal algorithms for this problem, but the they prove are only shown in the regime as the number of samples $n$ tends to infinity.
  arXiv  Detail & Related papers  (2026-05-26T16:39:24Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  Consider a Hermitian operator $A$ acting on a complex Hilbert space of $2n$.<n>We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian.<n>We show that whenever $A$ is $d$-local, textiti.e., $deg(A)le d$, we have the following discretization-type inequality.
  arXiv  Detail & Related papers  (2025-09-15T14:26:11Z)
• Symmetry reduction for testing $k$-block-positivity via extendibility [8.247261926186477]
  We exploit the unitary symmetry of the maximally entangled state to reduce the size of the corresponding semidefinite programs.<n>For example, for $k=2$, the SDP is reduced from one block of size $2N+1 dN+1$ to $lfloor fracN+12 rfloor$ blocks of size.
  arXiv  Detail & Related papers  (2025-05-28T08:26:34Z)
• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  We construct a dimension-independent k-partite disentangler (like) channel from bipartite unentangled input. We show that to capture NEXP, it suffices to have unentangled proofs of the form $| psi rangle = sqrta | sqrt1-a | psi_+ rangle where $| psi_+ rangle has non-negative amplitudes.
  arXiv  Detail & Related papers  (2024-02-23T12:22:03Z)
• Bounds on $k$-Uniform Quantum States [22.266687858571363]
  We provide new upper bounds on the parameter $k$ for the existence of $k$-uniform states in $(mathbbCd)otimes N$. Since a $k$-uniform state in $(mathbbCd)otimes N$ corresponds to a pure $(N,1,k+1)_d$ quantum error-correcting codes, we also give new upper bounds on the minimum distance $k+1$ of pure $(N,1,k+1))_d$ quantum error-correcting codes
  arXiv  Detail & Related papers  (2023-10-10T07:38:13Z)
• A universal framework for entanglement detection under group symmetry [1.384055225262046]
  We prove that all $(overlinepi_Aotimes pi_B)$-invariant quantum states are separable if and only if all extremal unital positive $(pi_A,pi_B)$-covariant maps are decomposable. $Phi(rho)=arho+brhoT+fracctextTr(rho)dtextId_d+ (1-a-b-c)textdiag(rho)
  arXiv  Detail & Related papers  (2023-01-10T08:43:41Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  We show a new way to relate functions on the hypergrid to their harmonic extensions over the polytorus. We show the supremum of a function $f$ over products of the cyclic group $exp(2pi i k/K)_k=1K$. We extend to new spaces a recent line of work citeEI22, CHP, VZ22 that gave similarly efficient methods for learning low-degrees on hypercubes and observables on qubits.
  arXiv  Detail & Related papers  (2023-01-04T04:15:40Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Monogamy of entanglement between cones [43.57338639836868]
  We show that monogamy is not only a feature of quantum theory, but that it characterizes the minimal tensor product of general pairs of convex cones.<n>Our proof makes use of a new characterization of products of simplices up to affine equivalence.
  arXiv  Detail & Related papers  (2022-06-23T16:23:59Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.