⚛️ quantum physics

Semidefinite extension complexity of the separable set, with applications to approximate disentanglers

This paper establishes superpolynomial lower bounds on the semidefinite extension complexity of the set of separable quantum states for approximate optimization problems, demonstrating that any semidefinite program with uniform additive error $a$ requires size at least $d^{c_\theta\min\{a^{-1/3},d^\theta\}}$ and thereby improving upon previous quasipolynomial bounds.

Original authors: Sevag Gharibian, Carsten Hecht, Dorian Rudolph

Published 2026-09-09

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Sevag Gharibian, Carsten Hecht, Dorian Rudolph

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

In the quantum world, information is stored in particles that can exist in multiple states at once, a property known as superposition. When two such particles become linked, they form an entangled pair, behaving as a single unit regardless of the distance between them. This entanglement is the engine behind the most powerful theoretical quantum computers, allowing them to solve problems that would take classical machines an eternity. However, there is a specific type of quantum proof system, used to verify complex calculations, that relies on a different kind of resource: unentangled proofs. In this scenario, a verifier receives two separate pieces of information that are guaranteed to be independent of one another, like two strangers who have never met and share no secret connection. The central mystery in this field is whether a verifier who can only check these independent proofs is actually as powerful as one who can check entangled ones. If they are equally powerful, it would mean that the strange, non-local connections of entanglement do not provide a fundamental advantage for this specific type of verification.

To test this, researchers have long looked for a "disentangler," a theoretical machine that could take any quantum state, even one that is highly entangled, and transform it into a state that looks like two independent pieces. If such a machine existed and could be built with a manageable amount of resources, it would prove that the independent proof system is just as strong as the entangled one. The hope was that this machine could act as a bridge, allowing the simpler system to simulate the more complex one. For years, scientists wondered if this bridge could be built with a reasonable number of quantum bits, or if the task was so difficult that it would require an impossibly large machine.

A team of researchers has now provided a definitive answer to this question, proving that such a bridge cannot be built with a reasonable amount of resources. They demonstrated that any machine attempting to convert arbitrary quantum states into independent ones must use a number of input bits that grows superpolynomially with the size of the output. In practical terms, this means that as the quantum system gets slightly larger, the machine required to disentangle it becomes astronomically larger, quickly exceeding the capacity of any conceivable physical device. This finding effectively rules out the strategy of using a disentangler to prove that the independent proof system is equivalent to the entangled one. The researchers did not just suggest this; they constructed a rigorous mathematical proof showing that the size of such a machine is fundamentally limited by the laws of geometry and probability, not just by current engineering constraints.

The core of their discovery lies in the study of "separable states," which are the quantum states that can be described as simple combinations of independent parts. The researchers focused on the difficulty of distinguishing these separable states from all other possible quantum states using a specific type of mathematical optimization. They showed that any attempt to approximate the behavior of these separable states using a standard mathematical tool, known as a semidefinite program, requires a structure so vast that it becomes useless for large systems. To visualize this, imagine trying to describe the shape of a complex, high-dimensional object using a flat, two-dimensional map. The researchers proved that no matter how cleverly you draw that map, if you want it to be accurate enough to be useful, the map itself must be impossibly large.

By analyzing the relationship between the size of the machine and the accuracy of the transformation, the team found a strict trade-off. If the machine is allowed to make even a tiny error in its transformation, the size of the machine still grows at a rate that is far too fast to be practical. Specifically, they showed that for a system with a certain number of output bits, the input bits required for the disentangler must grow exponentially with a power of the output size, rather than just a simple multiple. This means that doubling the size of the output does not just double the size of the input machine; it multiplies the input size by a factor that increases dramatically. This result holds true even when the machine is allowed to be slightly inaccurate, a condition that is necessary for any real-world application.

The implications of this work extend beyond the specific question of proof systems. It establishes a fundamental limit on how much we can compress or simplify quantum information without losing its essential properties. The researchers also confirmed that their findings apply to a broader class of mathematical models, showing that the difficulty is not just a quirk of a specific algorithm but a deep property of the quantum world itself. They utilized a technique involving "pseudo-densities," which are mathematical constructs that behave like probability distributions but allow for certain negative values, to expose the hidden complexity of the problem. This approach allowed them to prove that any attempt to approximate the separable set with a simpler structure inevitably fails as the system scales up.

In the context of the broader scientific community, this result settles a long-standing debate about the power of unentangled proofs. While it does not prove that the two systems are different in every possible scenario, it proves that the specific strategy of using a disentangler to make them equivalent is impossible. This forces researchers to look for other ways to understand the relationship between entangled and unentangled quantum information. The work also highlights the immense complexity inherent in quantum systems, showing that even when we try to strip away the entanglement, the underlying structure remains stubbornly difficult to capture with simple tools.

The paper concludes by noting that while their results are a strong barrier to one specific approach, they do not close the door on the entire question of whether the two proof systems are equal. Other methods might still exist, but the path through the disentangler is now known to be blocked by an insurmountable wall of complexity. The researchers' work stands as a precise, quantitative map of this barrier, showing exactly how high the wall is and why it cannot be climbed. Their findings are supported by formal computer-checked proofs, ensuring that the logic holds up under the most rigorous scrutiny. This level of certainty gives the scientific community a solid foundation to build upon, knowing that the limits they have found are real and not just artifacts of a particular calculation.

Ultimately, this research paints a picture of a quantum world where the resources required to manipulate information are not just large, but exponentially large when certain conditions are met. It suggests that the power of entanglement is not something that can be easily simulated or replaced by independent parts without paying a prohibitive cost. For those studying the limits of computation, this is a crucial piece of the puzzle, defining the boundaries of what is possible and what remains forever out of reach for machines that rely on independent proofs. The work does not just answer a question; it redefines the landscape of the problem, showing that the terrain is far more rugged than previously imagined.

Technical Summary: Semidefinite Extension Complexity of the Separable Set

1. Problem Statement

The paper addresses the computational complexity of approximating the maximum acceptance probability of a two-outcome measurement operator $Q$ over the set of separable states, denoted as $\text{Sep}(d:d)$ . This optimization problem, defined as $h_{\text{Sep}}(Q) = \max_{\sigma \in \text{Sep}(d:d)} \text{Tr}(Q\sigma)$ , is central to the complexity class $\text{QMA}(2)$ (Quantum Merlin-Arthur with two unentangled proofs).

The specific focus is on the semidefinite extension complexity of the separable set within the framework established by Harrow, Natarajan, and Wu (HNW). The authors investigate the minimum size $r$ of a semidefinite program (SDP) required to approximate $h_{\text{Sep}}$ under the following constraints:

Common Feasible Region: All measurement operators $Q$ share a single SDP feasible region $\mathcal{P}$ (a spectrahedron of $r \times r$ PSD matrices).
Objective-Independent Embedding: There exists a fixed map $\iota$ embedding pure product states into $\mathcal{P}$ such that the SDP objective $\Phi_Q$ reproduces the acceptance probability $\text{Tr}(Q\tau)$ for every product state $\tau$ , regardless of $Q$ .
Approximation: The SDP must approximate $h_{\text{Sep}}$ within a specified additive error $a$ or relative gap $\varrho$ .

The paper also applies these lower bounds to approximate disentanglers, quantum channels $\Lambda: \mathcal{L}(\mathbb{C}^D) \to \mathcal{L}(\mathbb{C}^d \otimes \mathbb{C}^d)$ that map arbitrary inputs to states close to separable states and cover all separable states. The goal is to determine the minimum input dimension $D$ required for such channels.

2. Methodology

The authors employ a combination of pattern-matrix lower bounds, pseudo-density techniques, and spectrahedral geometry.

2.1 The HNW Framework and PSD Rank

The core technique relies on the Lee–Raghavendra–Steurer (LRS) theorem, which relates the size of an SDP formulation to the PSD rank of a specific non-negative matrix (the "slack matrix").

Slack Matrix Construction: The authors construct a matrix $M$ where rows correspond to "witnesses" (block-positive operators $W_T$ ) and columns correspond to "states" (product states $\sigma_S$ ). The entries are $M(T, S) = \text{Tr}(W_T \sigma_S)$ .
Factorization: An SDP of size $r$ with a common feasible region implies a PSD factorization of this matrix of size $r+1$ . Thus, a lower bound on the PSD rank of $M$ yields a lower bound on the SDP size.

2.2 The Knapsack Pattern Matrix

Unlike previous work (HNW) which utilized a QMA(2) protocol based on graph 3-colorability, this paper constructs a matrix based on the central knapsack polynomial:
$f_m(x) = \frac{1}{m^2} \left[ \left( \sum_{i=1}^m x_i - \frac{m}{2} \right)^2 - \frac{1}{4} \right]$
where $m$ is an odd integer. On the Boolean hypercube $\{0,1\}^m$ , $f_m(x) \geq 0$ . However, Grigoriev's pseudo-expectation functional $\mathcal{G}_m$ assigns a negative value to $f_m$ (specifically $-1/4m^2$ ) by treating the non-existent Hamming weight layer $m/2$ as valid.

2.3 Amplification via Chebyshev Polynomials

To handle larger approximation errors (constant or inverse-polynomial) compared to HNW's exponentially small error regime, the authors apply a Chebyshev-Hadamard amplification:

They apply a polynomial transformation $P_\ell(u) = (1 + T_\ell(2u-1))/2$ to the matrix entries.
This transformation preserves the non-negativity of entries in the range $[0,1]$ but amplifies the negative pseudo-expectation value at the "formal" negative point by a factor of $\ell^2$ .
Crucially, the authors use the identity $P_\ell(u) = u Q_\ell(u)^2$ to bound the increase in PSD rank, showing that the rank cost grows only linearly with the degree of the polynomial, allowing the argument to scale with larger error parameters.

2.4 Construction of Witnesses and States

Proposition 4.1 explicitly constructs:

Product States: $\sigma_S$ encoding subsets $S \subseteq [N]$ using a specific superposition of basis vectors.
Block-Positive Witnesses: $W_T$ constructed from diagonal projectors and a penalty term involving the swap operator $F$ . These witnesses are designed to be non-negative on product states but can be negative on entangled states, with a norm bound of $O(m)$ independent of the ambient dimension.

3. Key Contributions and Results

3.1 Lower Bounds for SDP Formulations

The paper establishes a new lower bound on the size $r$ of SDP formulations approximating $h_{\text{Sep}}$ .

Theorem 5.4: For any fixed $0 < \theta < 2/7$ , there exist constants $c_\theta, a_\theta > 0$ such that for sufficiently large $d$ and approximation error $a \leq a_\theta$ , any SDP approximating $h_{\text{Sep}}$ to additive error $a$ has size:
$r \geq d^{c_\theta \min\{a^{-1/3}, d^\theta\}}$
Comparison with HNW: HNW proved a lower bound of $d^{\log d / \text{polylog} \log d}$ for error $O(1/d^2)$ . The new bound applies to constant errors and improves the HNW bound to exponential in a power of $d$ (specifically $d^{\Omega(d^\theta)}$ ) when the error is sufficiently small ( $a \leq d^{-3\theta}$ ).
Geometric Interpretation: Corollary 5.6 extends this to spectrahedral shadows, proving that any convex set of states containing $\text{Sep}(d:d)$ and lying within trace distance $a$ of it requires a spectrahedral lift of size at least $d^{c_\theta \min\{(2a)^{-1/3}, d^\theta\}}$ . This provides a quantitative counterpart to Fawzi's theorem that the separable set has no exact semidefinite representation.

3.2 Lower Bounds for Approximate Disentanglers

The authors apply the SDP lower bounds to the input dimension $D$ of approximate disentanglers.

Theorem 1.1: For an $(\varepsilon, \delta)$ -approximate disentangler with total error $a = \varepsilon + \delta$ , the input dimension $D$ satisfies:
$\log D \geq c M_a \log(2 + R_a)$
where $M_a$ and $R_a$ are functions of $d$ and $a$ derived from the SDP bounds.
Corollary 1.2 (Quantitative Growth):
- If $a \leq n^{-c}$ (inverse polynomial in the number of qubits $n = \log d$ ), then $\log D = \Omega(n^{1+c/3})$ . This forces a superlinear number of input qubits.
- If $a$ is of order $(\log d)^{18/7} / d^{6/7}$ , then $\log D = \Omega(d^{2/7} / (\log d)^{6/7})$ .
Implication for QMA(2): These results rule out the disentangler strategy for proving $\text{QMA} = \text{QMA}(2)$ when the promise gap is superpolynomially small ( $n^{-\omega(1)}$ ), as such a strategy would require a superpolynomial number of input qubits.

3.3 Bosonic Separability

Corollary 5.7 extends the lower bounds to the two-particle bosonic separable body (states of the form $|\psi\rangle\langle\psi|^{\otimes 2}$ ), showing the same complexity bounds apply.

4. Significance and Claims

The paper claims the following significance:

SDP-Specific Lower Bounds: The work provides the first unconditional information-theoretic lower bounds for general SDP extended formulations of $h_{\text{Sep}}$ that approximate the separable set within constant or inverse-polynomial trace distance. While concurrent work by Bostanci et al. [BGH+26] establishes stronger lower bounds for approximate disentanglers via a quantum oracle separation (superseding the disentangler bounds in Theorem 1.1), their reduction does not apply to general SDP formulations. Thus, the SDP-specific lower bounds (Theorem 5.4 and Corollary 5.5) remain the primary contribution of this work in the context of semidefinite complexity.
Quantitative Improvement: The bounds significantly improve upon the HNW results, moving from quasipolynomial to exponential lower bounds in $d$ for constant or inverse-polynomial errors.
Refutation of Disentangler Strategy: The results demonstrate that the disentangler approach cannot simulate $\text{QMA}(2)$ using a channel with polynomially many input qubits if the channel error is sufficiently small relative to the promise gap, specifically within the regime where the SDP bounds apply.
Methodological Advancement: The work introduces a refined application of the LRS theorem using the knapsack polynomial and Chebyshev amplification, allowing for tighter control over the error parameters and PSD rank costs compared to previous protocol-based constructions.

The authors acknowledge concurrent work by Bostanci et al. [BGH+26] which uses a quantum oracle separation to prove stronger lower bounds for disentanglers ( $\log D = \Omega(\sqrt{d})$ for constant error). However, the authors note that the Bostanci et al. reduction does not apply to general SDP formulations, leaving the SDP-specific lower bounds (Theorem 5.4 and Corollary 5.5) as the primary contribution of this work. The results are supported by formal Lean proofs.