⚛️ quantum physics

Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond

This paper presents a polynomial-time algorithm that efficiently recovers all elements of an arbitrary conic variety lying within a generic linear subspace, thereby solving several NP-hard problems in quantum entanglement and tensor decompositions for typical instances.

Original authors: Nathaniel Johnston, Benjamin Lovitz, Aravindan Vijayaraghavan

Published 2026-09-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nathaniel Johnston, Benjamin Lovitz, Aravindan Vijayaraghavan

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 vast landscape of modern mathematics and computer science, researchers often grapple with the problem of finding hidden patterns within complex structures. Imagine a space filled with points, where some points follow a specific, rigid rule while others do not. The challenge is to look at a random collection of points and determine if any of them obey that rule, or to find exactly which ones do. This is not just an abstract puzzle; it lies at the heart of understanding how information is stored and processed in quantum systems, where the state of a particle can be entangled with another in ways that defy classical intuition. It also underpins the ability to break down massive, multi-dimensional data sets into their simplest, most fundamental components, a task crucial for machine learning and signal processing. For decades, the general version of this problem was considered nearly impossible to solve efficiently for all possible cases, with the worst scenarios requiring so much time that even the fastest supercomputers would fail.

A team of researchers has now developed a new method that bypasses this difficulty for the vast majority of real-world situations. They focused on a specific type of mathematical object called a variety, which is simply a shape defined by a set of polynomial equations. Within this shape, they looked for points that also lie inside a specific linear subspace, a flat slice of the larger space. While finding these intersections is known to be extremely hard in the worst-case scenario, the researchers proved that for "typical" or generic inputs, their algorithm works with surprising speed and certainty. Their approach does not rely on guessing or approximation; instead, it uses a rigorous mathematical framework to either find every single point that fits the criteria or to prove with absolute certainty that no such points exist. This distinction is vital: the method does not just find a solution; it verifies that the solution is the only one possible, a guarantee that was previously out of reach for such broad classes of problems.

The power of this discovery becomes clear when applied to quantum information theory. In this field, scientists study "entangled subspaces," which are collections of quantum states that are deeply linked and cannot be separated into independent parts. Determining whether a given collection of states is truly entangled has been a notoriously difficult computational problem, known to be intractable in the worst cases. The new algorithm, however, can efficiently certify that a subspace is entangled or, if it contains a few separable states, it can find and identify exactly those states. This capability extends to various forms of entanglement, including those involving multiple particles or complex groupings, providing a reliable tool for designing quantum error-correcting codes and verifying the security of quantum communication protocols. The researchers showed that for subspaces of a certain size, which covers a wide range of practical dimensions, their method succeeds almost every time, offering a polynomial-time solution where none existed before.

Beyond quantum mechanics, the work offers a fresh perspective on decomposing complex data structures, such as tensors, which are multi-dimensional arrays used to represent high-order relationships in data. A common challenge is to break a complicated tensor down into a sum of simpler, rank-one components. While this task is generally hard, the researchers demonstrated that for generic instances, their algorithm can not only recover the unique decomposition but also prove that no other decomposition is possible. This is a significant improvement over previous methods, which often required stricter assumptions about the data or failed to provide a certificate of uniqueness. The new technique applies to a much broader class of problems than just standard tensor decomposition, including "block" decompositions used in signal processing and machine learning. By treating these diverse problems under a single, unified mathematical umbrella, the researchers have created a versatile toolkit that can handle a wide array of low-rank decomposition challenges with efficiency and mathematical rigor.

The core of their achievement lies in a clever combination of algebraic geometry and linear algebra. They constructed an algorithm that first checks if the intersection of the shape and the subspace is empty, providing a definitive certificate if it is. If the intersection is not empty, the method lifts the problem into a higher-dimensional space where it can be solved using a technique known as simultaneous diagonalization. This process allows the algorithm to isolate the specific points of interest and confirm their uniqueness. The researchers were careful to address a flaw in a previous, similar method proposed by other scientists, correcting a critical error in the underlying logic that had gone unnoticed. By doing so, they not only fixed a specific issue but also established a more robust and general theory that holds true for a much wider variety of mathematical shapes and conditions.

This work represents a shift from hoping that a problem is easy to proving that it is easy for the cases that matter most. The researchers did not claim to solve the problem for every single possible input, acknowledging that some pathological cases remain difficult. Instead, they provided a strong guarantee that for any randomly chosen, typical instance within a wide range of dimensions, the algorithm will succeed. This distinction is crucial for practical applications, as real-world data rarely falls into the worst-case categories that make these problems intractable. By focusing on the generic behavior of these systems, the team has opened the door to efficient solutions for problems that were previously thought to be computationally prohibitive, offering new hope for advancements in quantum computing, data analysis, and the broader field of algorithmic mathematics.

Technical Summary: Computing Linear Sections of Varieties

Problem Statement
The paper addresses the algorithmic problem of finding elements in the intersection of an arbitrary conic variety $X \subseteq \mathbb{F}^n$ (where $\mathbb{F}$ is $\mathbb{R}$ or $\mathbb{C}$ ) and a given linear subspace $U \subseteq \mathbb{F}^n$ . The variety $X$ is defined as the common zero set of a collection of homogeneous polynomials of degree $d$ , and the subspace $U$ is specified by a basis $\{u_1, \dots, u_R\}$ .

The core problem (Problem 1) asks: Given $U$ and the defining polynomials of $X$ , can one either certify that $U \cap X = \{0\}$ or find a non-zero point $v \in U \cap X$ ?

This problem is known to be NP-hard in the worst case, even for the specific case where $X$ is the variety of rank-1 matrices (determinantal varieties). The authors note that this hardness applies to central problems in quantum information theory (e.g., determining if a subspace is entangled) and tensor decompositions.

Methodology
The authors propose Algorithm 1, a polynomial-time algorithm designed to solve this problem for "typical" or generic instances. The algorithm relies on two main mathematical pillars:

Hilbert's Nullstellensatz: Specifically, a degree- $d$ certificate derived from the projective Nullstellensatz to check if the intersection is trivial.
Simultaneous Diagonalization: A "lifted" version of the simultaneous diagonalization algorithm (often associated with Jennrich's algorithm or Harshman's algorithm) applied to the space of degree- $d$ polynomials.

Algorithmic Steps:

Input: A basis for the subspace $U$ and a set of homogeneous degree- $d$ polynomials $\{f_1, \dots, f_p\}$ defining $X$ .
Construction: The algorithm computes a basis $\{P_1, \dots, P_s\}$ for the linear subspace $S_d(U) \cap I_d^\perp$ , where $S_d(U)$ is the $d$ -th symmetric power of $U$ , and $I_d^\perp$ is the orthogonal complement of the ideal generated by the defining polynomials in the space of degree- $d$ polynomials.
Trivial Intersection Check: If $S_d(U) \cap I_d^\perp = \{0\}$ , the algorithm certifies that $U \cap X = \{0\}$ .
Recovery: If the intersection is non-trivial, the algorithm treats the basis elements as a tensor and runs the simultaneous diagonalization algorithm.
- If the diagonalization yields a decomposition of the form $\{z_i \otimes v_i^{\otimes d}\}$ where $v_i$ are linearly independent, the algorithm outputs $\{v_1, \dots, v_s\}$ as the unique elements of $U \cap X$ (up to scalar multiples).
- If the diagonalization fails to produce such a structure, the algorithm outputs "Fail."

Key Contributions and Theoretical Guarantees
The primary contribution is a genericity guarantee (Theorem 2) proving that Algorithm 1 succeeds with high probability for generic subspaces of a certain dimension, despite the worst-case NP-hardness.

Main Theorem (Theorem 2): Let $X$ be an irreducible variety cut out by $p = \delta \binom{n+d-1}{d}$ linearly independent homogeneous polynomials of degree $d$ , and assume $X$ is non-degenerate of order $d-1$ . If $U$ is a generic subspace of dimension $R \leq \frac{\delta}{d!}(n+d-1)$ spanned by $s$ generic elements of $X$ and $R-s$ generic elements of the ambient space, then:
1. $U \cap X$ contains exactly $s$ elements (up to scalar multiples).
2. Algorithm 1 recovers these $s$ elements in $n^{O(d)}$ time and certifies their uniqueness.
3. If $s=0$ , the algorithm certifies $U \cap X = \{0\}$ in $n^{O(d)}$ time.
Correction of Prior Work: The authors identify a critical error in a crucial lemma (Lemma 2.3) of the seminal work by De Lathauwer, Cardoso, and Castaing [DL06] regarding the FOOBI algorithm. They provide a counterexample and a corrected proof technique that establishes genericity guarantees for a much broader class of varieties, not just rank-1 matrices.

Results and Applications
The paper derives several corollaries applying the main theorem to specific domains:

Quantum Entanglement:
- Entangled Subspaces: The algorithm determines if a generic subspace $U$ is $r$ -entangled (contains no rank- $r$ matrices) or finds the planted separable states. This applies to $r$ -entanglement, complete entanglement (no product states), and genuine entanglement (no biseparable states).
- Efficiency: While worst-case determination is NP-hard, the algorithm solves these problems in polynomial time for subspaces with dimension up to a constant fraction of the total dimension (e.g., $R \approx \frac{1}{4}(n_1-1)(n_2-1)$ for rank-1 matrices).
Low-Rank Decompositions:
- Uniqueness and Recovery: The paper establishes uniqueness and efficient recovery for $(X, W)$ -decompositions of the form $T = \sum_{i=1}^R v_i \otimes w_i$ , where $v_i \in X$ .
- Tensor Decompositions: For standard tensor decompositions (where $X$ is the variety of rank-1 matrices), the algorithm recovers unique decompositions for ranks up to $R \approx \frac{1}{4}(n_1-1)(n_2-1)$ in the case of 3rd-order tensors. This improves upon previous genericity bounds (which were typically limited to $R \leq n$ for $n \times n \times n$ tensors).
- Higher Order Tensors: The results extend to non-symmetric tensors of arbitrary order $m$ , providing guarantees for ranks up to $O(n^{\lfloor m/2 \rfloor})$ . This is a significant improvement for even-order non-symmetric tensors, where such guarantees were previously unknown.
- Block Decompositions: The framework applies to $r$ -aided decompositions (block decompositions), providing polynomial-time guarantees for recovering these structures.

Significance
The paper claims significance by bridging algebraic geometry and algorithmic complexity to solve a class of problems previously considered intractable in the worst case. By shifting the focus to generic instances, the authors demonstrate that:

Efficiency: Polynomial-time algorithms exist for recovering intersections and decompositions that are NP-hard in the worst case.
Generality: The method is not limited to tensors or matrices but applies to any irreducible conic variety satisfying mild non-degeneracy conditions.
Correctness: The work rectifies the theoretical foundation of the FOOBI algorithm and related tensor decomposition methods, providing rigorous genericity guarantees where previous proofs were flawed.
Uniqueness: The algorithm does not just find a solution; it provides a certificate that the found decomposition is unique (up to trivial scaling and permutation), a property crucial for applications in latent variable model estimation and signal processing.

Technical Summary: Computing Linear Sections of Varieties

More like this