⚛️ quantum physics

The complexity of semidefinite programs for testing $k$ -block-positivity

This paper extends previous work on $k$ -block-positivity testing by employing a symmetry reduction scheme based on rectangular Young diagrams to derive an explicit complexity formula linked to $\U(d)$ representation dimensions, thereby explaining the collapse of the semidefinite program hierarchy when $k=d$ .

Original authors: Qian Chen, Benoît Collins

Published 2026-03-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Qian Chen, Benoît Collins

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Quality Control" Problem

Imagine you are a quality control inspector at a factory that makes complex quantum machines (like entangled particles). Your job is to check if a specific machine part is "safe" or "positive."

In the quantum world, "safe" doesn't just mean it works; it means it works for different levels of complexity.

Level 1 (Separable): The machine is just two separate parts sitting next to each other. Easy to check.
Level $k$ (k-block-positive): The machine has parts that are slightly "glued" together (entangled), but only in a specific, limited way.
Level $d$ (Full Entanglement): The parts are glued together in every possible way.

The problem is: How do we test if a machine is safe at Level $k$ ?

The paper says the traditional way to do this is like trying to find a needle in a haystack by checking every single straw in the haystack. It's computationally impossible for large machines because the "haystack" (the number of possibilities) grows explosively.

The Solution: The "Rectangular Filter"

The authors (Qian Chen and Benoît Collins) found a clever shortcut. They realized you don't need to check the whole haystack. You only need to check a very specific, organized section of it.

Analogy 1: The Library of Shapes

Imagine the "haystack" is actually a giant library filled with books of different shapes.

The Old Way: To find the "safe" books, you had to walk through every single aisle, looking at every book shape (triangles, circles, weird squiggles). This takes forever.
The New Way: The authors discovered that if you only look at Rectangular Books, you get the exact same answer. If a Rectangular Book is safe, the whole library is safe. If it's not, the whole library is broken.

This is the core of their "Rectangular Scheme." Instead of checking millions of complex shapes (called Young diagrams in math), they proved you only need to check the ones that look like perfect rectangles. This shrinks the library from a massive warehouse down to a single, neat shelf.

Analogy 2: The Security Camera

Think of the quantum state as a room full of people.

The Old Method: You hire a security guard to watch every single person in the room individually. As the room gets bigger, you need more guards, more cameras, and more computers.
The New Method: The authors realized that because the people in the room follow strict rules of symmetry (they move in groups), you only need to watch the captains of the groups. If the captains are behaving, everyone is behaving.

By focusing only on these "captains" (which correspond to the rectangular shapes), they drastically reduced the number of cameras (computational resources) needed.

The "Magic Collapse" (When $k = d$ )

One of the most exciting findings in the paper is what happens when you try to test the maximum level of complexity (when $k$ equals the total size of the system, $d$ ).

The Analogy:
Imagine you are trying to find the lowest point in a mountain range.

Normal Case ( $k < d$ ): You have to hike up and down every valley and ridge to make sure you found the absolute lowest point. It's a long, hard journey.
The Collapse Case ( $k = d$ ): The authors show that if you are looking for the lowest point of the entire mountain range, you don't need to hike at all. You just look at the map. The answer is already obvious.

In math terms, they proved that when $k = d$ , the complex hierarchy of tests "collapses." The complicated computer program simplifies instantly into a basic calculation (just checking the lowest eigenvalue). It's like realizing you don't need a supercomputer to solve a puzzle that turns out to be a simple arithmetic problem.

Why Does This Matter?

Saving Time and Money: By proving we only need to check "Rectangular" shapes, they reduced the computational cost from something impossible (like calculating the number of atoms in the universe) to something manageable (like calculating the number of grains of sand on a beach).
Understanding Entanglement: This helps scientists better understand "bound entanglement" (quantum glue that is hard to break). It gives them a faster way to test if quantum states are useful for things like quantum cryptography or teleportation.
The Formula: They wrote down a specific formula (Theorem 1) that tells you exactly how much computer power you need. It's like a "fuel gauge" for quantum testing.

Summary in One Sentence

The authors figured out that to test complex quantum safety, you don't need to check every possible shape; you only need to check the "rectangular" ones, which makes the math much faster and explains why some tests become surprisingly simple when the system gets fully entangled.

1. Problem Statement

The central problem addressed is the computational complexity of testing $k$ -block-positivity for linear maps in quantum information theory.

Context: A linear map is $k$ -positive if its Choi operator is $k$ -block-positive. An operator $X$ is $k$ -block-positive if $\langle \psi | X | \psi \rangle \geq 0$ for all pure states $|\psi\rangle$ with Schmidt rank at most $k$ .
Challenge: Determining $k$ -block-positivity is generally NP-hard. The standard approach involves the extendibility hierarchy (a sequence of Semidefinite Programs or SDPs) which approximates the set of separable states (or Schmidt number $k$ states).
Specific Issues:
1. Computational Cost: The hierarchy requires solving SDPs indexed by all possible Young diagrams $\lambda$ with $N$ boxes and at most $k$ rows. As the hierarchy level $N$ increases, the number of Young diagrams grows rapidly, making the optimization computationally expensive.
2. Hierarchy Collapse: It is known that for $k=d$ (where $d$ is the local dimension), testing $d$ -block-positivity is trivial (equivalent to checking the minimal eigenvalue), implying the hierarchy should "collapse." However, a quantitative explanation for this collapse within the SDP framework was lacking.

2. Methodology

The authors extend their previous work [CCF25] by introducing a symmetry reduction scheme based on rectangular-shaped Young diagrams.

$k$ -Purification and Dualization: The problem is reformulated using $k$ -purification. The original operator $X$ is mapped to $X_k$ on an extended space involving auxiliary systems. A linear map $E$ is used to convert $\bar{U} \otimes U$ symmetry into $U^{\otimes k}$ symmetry, simplifying the analysis via Schur-Weyl duality.
Symmetry Reduction: The SDP variables are decomposed into blocks indexed by irreducible representations (Young diagrams) of the unitary group $U(k)$ and the symmetric group $S_N$ .
Rectangular Scheme Restriction: Instead of considering all Young diagrams $\lambda \vdash N+k-1$ with $\ell(\lambda) \leq k$ , the authors prove that it is sufficient to restrict the hierarchy to rectangular Young diagrams of the form $(n^k)$ (a rectangle with $k$ rows and $n$ columns).
Trace Constraint Relaxation: To facilitate the proof, the authors relax the trace constraint in the SDP from equality ( $\text{Tr}(\rho)=1$ ) to inequality ( $\text{Tr}(\rho) \leq 1$ ), allowing for a clearer analysis of the relationship between the SDP values and the true optimization problem.
Kraus Operator Representation: The feasible states are characterized using exchangeable Kraus operators. The size of the SDP variable is linked to the dimension of the space of these operators, which corresponds to the dimension of irreducible representations of $U(d)$ .

3. Key Contributions

A. Sufficiency of Rectangular Young Diagrams

The paper proves that testing $k$ -block-positivity does not require the full set of Young diagrams. It is sufficient to construct a hierarchical SDP sequence indexed only by rectangular diagrams $(n^k)$ for $n=1, 2, \dots$ .

Theorem 14: Establishes that if the SDP value $S_{(n^k)} \geq 0$ for some $n$ , the operator is $k$ -block-positive. If $S_{(n^k)} < 0$ for all $n$ , it is not. This drastically reduces the search space.

B. Explicit Complexity Formula

The authors derive an explicit formula for the computational complexity (size of the SDP variable) of the reduced scheme indexed by a rectangular diagram $(n^k)$ .

Theorem 1 (Main Result): The complexity $C(n^k)$ is given by:
$C(n^k) = d^k \binom{d+n-1}{k+n-1} \prod_{r=1}^k \frac{(d+n-r-1)!(k-r)!}{(k+n-r-1)!(d-r)!}$
This complexity scales as $O(n^{k(d-k)})$ after symmetry reduction, a significant improvement over the unreduced complexity $O((kd)^{N+1})$ .

C. Explanation of Hierarchy Collapse

The derived formula provides a rigorous explanation for the "collapse" of the hierarchy when $k=d$ .

Corollary 19: When $k=d$ , the complexity $C(n^d)$ becomes independent of $n$ .
Significance: This means that for $k=d$ , increasing the hierarchy level $N$ (or $n$ ) does not increase the computational resources required. The first level of the hierarchy (or a constant size) is sufficient, mathematically confirming that the problem reduces to a simple eigenvalue check.

D. Complexity Relation for Different $k$

The paper analyzes the asymptotic behavior of the complexity for different $k$ values as $n \to \infty$ (Corollary 20). It shows that testing $k$ -block-positivity and $k'$ -block-positivity have equivalent complexity (in Big-O notation) if $k + k' = d$ .

4. Results

Algorithmic Simplification: The proposed "rectangular scheme" reduces the number of SDP blocks to be solved from an exponential growth (all Young diagrams) to a linear sequence (rectangular diagrams only).
Quantitative Complexity: The paper provides the exact dimension of the matrix variables required for the SDP, linking it directly to the dimensions of irreducible representations of $U(d)$ .
Theoretical Unification: The work unifies the concepts of $k$ -block-positivity, Schur-Weyl duality, and SDP complexity, showing how representation theory dictates computational cost.
Validation of $k=d$ Case: The formula explicitly demonstrates why the hierarchy is redundant for $k=d$ , as the dimension of the relevant representation space becomes constant regardless of the hierarchy level.

5. Significance

Quantum Information Theory: This work provides a more efficient algorithmic framework for testing entanglement properties (specifically Schmidt number and $k$ -positivity), which are crucial for understanding bound entanglement and entanglement distillability.
Computational Efficiency: By restricting the search space to rectangular diagrams, the paper offers a practical path to solving high-level SDPs that were previously intractable due to the combinatorial explosion of Young diagrams.
Foundational Insight: The connection between the collapse of the SDP hierarchy and the dimension of irreducible representations offers deep theoretical insight into the structure of quantum states and symmetries.
Future Applications: The authors suggest these methods could be applied to other challenging problems, such as the 2-copy distillability conjecture, by providing a scalable way to approximate the set of separable states.

In summary, this paper transforms the theoretical understanding of $k$ -block-positivity testing from a brute-force hierarchy into a structured, symmetry-reduced optimization problem with a precisely quantified computational cost.