The complexity of semidefinite programs for testing k k -block-positivity
Qian Chen, Benoît Collins · 2026
Read The complexity of semidefinite programs for testing k k -block-positivity by Qian Chen, Benoît Collins (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-19159.txt.
Introduction
Qian Chen and Benoît Collins price a test that tells whether a quantum state has a hidden split. The test uses semidefinite programs, a class of optimization tools, arranged in a ladder of ever sharper checks. The property under test, called k-block positivity, links to whether quantum states can be separated.
The pair use a symmetry cut based on rectangular Young diagrams to tame the cost. They tie the cost to the sizes of certain symmetry groups and give an exact formula for it. Their formula also shows why the ladder stops early in one special case, a neat closure.
Catalog record
| CREATOR | Qian Chen, Benoît Collins |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 101 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-19159
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The complexity of semidefinite programs for testing k k -block-positivity Qian Chen, Benoît Collins Abstract We extend [ 3 ] by analyzing the complexity of the k k -block-positivity testing algorithm. In this paper, we investigate a symmetry reduction scheme based on rectangular shaped Young diagrams. Connecting the complexity to the dimensions of irreducible representations of U ( d ) {\mathrm{U}}(d) , we derive an explicit formula for the complexity, which also clarifies why the semidefinite program hierarchy collapses in the k = d k=d case. Introduction A fundamental task in quantum information theory is to characterize linear maps. This involves determining not only whether a map is positive, but also its degree of positivity, that is, for which values of ‘ k ’ it is k -positive. The Choi operator of a k -positive map is k -block-positive, meaning that the operator yields nonnegative expectation value for all pure states with at most Schmidt rank k . It closely connects to the notions of bound entanglement and distillability of entanglement, e.g., the 2-copy distillability conjecture [ 5 ] . The set of k -block-positive operators is the dual of the set consisting of Schmidt number k states [ 10 , 9 , 7 , 6 ] . Examining whether a operator is k -block-positive or not is a very challenging task. We extend our work [ 3 ] by analyzing the complexity of the algorithm for testing k -block-positivity within the framework of semidefinite programs (SDPs). This algorithm converts the problem from testing k -block-positivity to testing 1 -block-positivity via k -purification, and then uses extendibility hierarchy to approximate its dual, the set of separable states. Subsequently, we adopt a scheme that reduces some of the complexity from choosing Young diagrams in [ 3 ] . The complexity associated with Young diagrams originates from the symmetry reduction under {\mathrm{U}}(k) -symmetry, which defines feasible states as positive semidefinite block matrices indexed by Young diagrams. As the extendibility hierarchy progresses to higher levels, the number of Young diagrams grows, thereby increasing the computational resources required for optimization, since the minimal value must be identified across all blocks. Thus, restricting the set of Young diagrams while maintaining the validity of the test will greatly simplify the algorithm. Eventually, we study the complexity of this algorithm within the framework of semidefinite programs. Regarding the required SDP variables as computational resources, we derive a formula characterizing the size of this resource, which also provides a quantitative explanation of the phenomenon whereby the extendibility hierarchy should collapse in the k=d case. We will show that establishing hierarchical SDPs on rectangular shape of Young diagrams is sufficient for testing k -block-positivity. Then we are led to the main result of this paper. Theorem 1 (The SDP complexity of rectangular scheme) . Setting N by N+k-1=kn with integer n . The SDP complexity of the reduced SDP indexed by a rectangular Young diagram (n^{k}) is \displaystyle{\cal C}_{(n^{k})}=d\frac{k(d+n-1)}{k+n-1}\prod_{r=1}^{k}\frac{(d+n-r-1)!(k-r)!}{(k+n-r-1)!(d-r)!}. (1) That is to say, the SDP complexity is O(n^{k(d-k)}) after symmetry reduction, compared with the unreduced one O((kd)^{N+1}) . The proof of Theorem 1 guides the structure of this paper as follows. • Step 0: Section 1 presents the basic notation for k -block-positivity, as well as related optimization problems for testing k -block-positivity. • Step 1: Section 2 introduces the involved SDPs. In Subsection 2.1 , we review the reduced SDPs indexed by Young diagrams, and present the questions about (a) economical scheme on Young diagrams and (b) hierarchy collapse if k=d . In Subsection 2.2 we change the trace constraint from equality to inequality, and prepare the construction displayed in Corollary 10 for the sequential analysis. • Step 2: Section 3 is dedicated to answer the question about economical scheme on Young diagrams, showing that testing k -block-positivity can rely on hierarchical SDPs indexed by rectangular shape Young diagrams, as stated in Proposition 14 . • Step 3: Section 4 aims to complete the proof of Theorem 1 . Subsection 4.1 provides the relation between the size of SDP variables (indexed by one Young diagram) and the dimension of the irreducible representation of {\mathrm{U}}(d) , as stated in Proposition 16 . We then derive the explicit formula in Theorem 1 , which is followed by two corollaries: one explains why the SDP hierarchy collapses if k=d , another shows the equivalent complexity for testing k - and k^{\prime} -block positivity if k+k^{\prime}=d . 1 Preliminary 1.1 Notation Let \mathbb{M}_{m\times n}(\mathbb{C}) denote the space of m\times n matrices over \mathbb{C} , and simply {\mathbb{M}}_{m}(\mathbb{C}) when m=n ; \mathrm{Herm}(\mathbb{C}^{d}) and \mathrm{Herm}(\mathbb{C}^{d})_{+} the subsets of \mathbb{M}_{d}(\mathbb{C}) of hermitian matrices and positive semidefinite matrices, respectively. Let \mathbb{C}^{d_{A}} and \mathbb{C}^{d_{B}} be the original spaces of Alice and Bob, respectively; in this paper, we set d=d_{A}=d_{B} by default. Let \mathbb{C}^{k} be the auxiliary spaces carrying k -purification (or referred to as k -extension). The space after k -purification is denoted by {\cal H}:=\mathbb{C}^{kd}\cong\mathbb{C}^{k}\otimes\mathbb{C}^{d} . We denote the permutation over {\cal H}^{\otimes N} by \Delta which is defined by \Delta:S_{N}\to\mathrm{Perm}^{k}\times\mathrm{Perm}^{d} where \mathrm{Perm}^{k}:S_{N}\to{\mathrm{U}}((\mathbb{C}^{k})^{\otimes N}) is the natural unitary representation of permutation prescribed by \mathrm{Perm}^{k}(\pi)\ket{i_{1}\ldots i_{N}}=\ket{i_{\pi^{-1}(1)}\ldots i_{\pi^{-1}(N)}} for \pi\in S_{N} , and likewise for \mathrm{Perm}^{d}:S_{N}\to{\mathrm{U}}((\mathbb{C}^{d})^{\otimes N}) . That is to say, \Delta(\pi) is defined by permuting auxiliary and original spaces with \mathrm{Perm}^{k}(\pi) and \mathrm{Perm}^{d}(\pi) respectively. We will often drop \mathrm{Perm}^{k} and \mathrm{Perm}^{d} so write \Delta(\pi)=\pi\otimes\pi when the context is clear. For Alice’s auxiliary system, we introduce linear map {\cal E}:\mathbb{C}^{k}\to\mathrm{Alt}^{k-1}\mathbb{C}^{k} where \mathrm{Alt}^{k-1}\mathbb{C}^{k} is the anti-symmetric subrepresentation of (\mathbb{C}^{k})^{\otimes(k-1)} . Denote by \ket{\phi_{k}}=\sum_{i=1}^{k}\ket{ii} the unnormalized k -dimensional maximally entangled state, and define \hat{\phi}_{k}=\ket{\phi_{k}}\otimes\mathds{1}_{d_{A}}\otimes\mathds{1}_{d_{B}} . Denote by \mathrm{sr}(\psi) the Schmidt rank of vector \ket{\psi} . We denote \lambda\vdash_{k}N if \lambda is a Young diagram of N boxes with at most k rows, i.e., \ell(\lambda)\leq k . Denote by \mathbb{Y}_{\lambda} the Specht module associated to Young diagram \lambda . Let \lambda^{-} denote the Young diagram obtained from \lambda with \ell(\lambda)=k by removing its first column, that is, if \lambda=(\lambda_{1},\ldots,\lambda_{k}) , then \lambda^{-}=(\lambda_{1}-1,\ldots,\lambda_{k}-1) . Denote by {\mathbb{U}}_{\lambda}^{k} and {\mathbb{U}}_{\lambda}^{d} the irreducible representations associated with the Young diagram \lambda for the unitary groups \mathrm{U}(k) and \mathrm{U}(d) , respectively. We write \mu\subseteq\lambda for Young diagrams such that \mu is contained in \lambda , i.e., \mu_{i}\leq\lambda_{i} for all i . We write \lambda\searrow\mu if Young diagram \lambda is obtained by appending exactly one box to \mu . 1.2 Optimization problems for testing k -block positivity This section provides a brief review of k -block-positivity and formulates two optimization problems for testing it. Recall that in a bipartite system \mathbb{C}^{d_{A}}\otimes\mathbb{C}^{d_{B}} , any bipartite pure state with Schmidt rank at most k can be written in the following form: \displaystyle\ket{\psi}=\sum_{i=1}^{k}\ket{x_{i}}\otimes\ket{y_{i}}\,,\>\text{ where for all $i$, }\ket{x_{i}}\in\mathbb{C}^{d_{A}},\>\ket{y_{i}}\in\mathbb{C}^{d_{B}}. (2) Denote by \mathrm{SR}_{k}(d_{A},d_{B}) the set consisting of pure states with Schmidt rank at most k . A hermitian operator X\in\mathrm{Herm}(\mathbb{C}^{d_{A}}\otimes\mathbb{C}^{d_{B}}) is said to be k -block-positive if X ’s expectation value is nonnegative for all pure states in \mathrm{SR}_{k}(d_{A},d_{B}) , \displaystyle\langle\psi|X|\psi\rangle\geq 0\,,\>\forall\ket{\psi}\in\mathrm{SR}_{k}(d_{A},d_{B}). (3) A mixed state \rho is said to have Schmidt number k if it lies in the convex hull of \mathrm{SR}_{k}(d_{A},d_{B}) [ 10 , 9 ] . Denote by \mathrm{SN}_{k}(d_{A},d_{B}) the set of Schmidt number k states. In particular, \mathrm{SN}_{1}(d_{A},d_{B}) is the set of separable states.