Generating Non-Decomposable Maps with Differentiable Semidefinite Programming

This paper introduces a differentiable semidefinite programming framework that systematically generates positive non-decomposable maps under flexible structural constraints, enabling the discovery of new numerical examples, parametrized families, and real maps while addressing open questions in quantum information theory.

The Gist

Imagine you are trying to find a very specific, rare type of key in a massive, dark warehouse. This key has a special property: it can unlock a door that other keys cannot, revealing a hidden secret (in this case, a type of "entanglement" in quantum physics that is usually invisible).

The paper you provided is about building a smart robot that can systematically search for these rare keys, rather than just hoping to stumble upon one by accident.

Here is a breakdown of the paper's ideas using everyday analogies:

1. The Problem: Finding the "Invisible" Keys

In the world of quantum physics, scientists use mathematical tools called maps to describe how information changes. Some of these maps are "decomposable," meaning they are built from standard, predictable parts. Others are non-decomposable.

• The Analogy: Think of "decomposable" maps as a standard house key. It works on many locks, but it can't open the special "PPT" (Positive Partial Transpose) locks.
• The Challenge: The "non-decomposable" maps are the special keys that can open those PPT locks. However, they are incredibly hard to find. For a long time, scientists only knew a handful of these keys, mostly by guessing or using very specific, rigid formulas. They lacked a general method to generate new ones, especially in complex, high-dimensional scenarios.

2. The Solution: A "Differentiable" Search Engine

The authors created a new framework to hunt for these keys. They combined two powerful tools:

1. Semidefinite Programming (SDP): Think of this as a super-strict quality inspector. It checks a candidate map and gives a "Pass" or "Fail" grade based on whether it is positive (safe) and non-decomposable (special).
2. Gradient-Based Optimization: This is the robot's brain. It tries to build a map, checks the grade, and then adjusts the map slightly to get a better grade.

The Innovation: Usually, the "quality inspector" (SDP) is a black box—you can't tell the robot how to fix the map based on the inspector's feedback. The authors made the inspector differentiable.

• The Metaphor: Imagine the quality inspector doesn't just say "Fail." Instead, they hand the robot a map with a red arrow pointing exactly where to tweak the design to make it pass. This allows the robot to learn and improve continuously, rather than guessing blindly.

3. How the Robot Works

The robot starts with a blank slate (a random matrix) and tries to shape it into a valid key. It has two main goals, enforced by a "loss function" (a scorecard):

• Goal A (Non-decomposability): The map must be "weird" enough to detect those invisible PPT states. The robot tries to make a specific test value negative.
• Goal B (Positivity): The map must still be a valid, safe mathematical object. The robot tries to keep another test value positive.

The robot balances these two competing goals, nudging the design until it finds a shape that satisfies both.

4. What They Found

Using this robot, the team achieved several things:

• New Keys: They generated many new examples of these rare maps in dimensions 2, 3, and 4.
• Masked Patterns: They tried putting "masks" on the robot's canvas (forcing certain parts of the map to be zero). This led to the discovery of a whole new family of these maps that follow a specific, elegant pattern.
• Real-World Maps: They managed to construct maps that use only real numbers (no complex imaginary numbers), which are often easier to work with in physics.
• Testing Theories: They used the robot to test famous open questions in physics, like the "PPT Square Conjecture." The robot tried to break the conjecture by finding a counter-example, but it failed to do so. This didn't prove the conjecture is true, but it added strong numerical evidence that it likely is.

5. The Bottom Line

The paper doesn't claim to have built a quantum computer or solved a medical problem. Instead, it provides a new, flexible toolkit for mathematicians and physicists.

Before this, finding these special maps was like looking for a needle in a haystack with a flashlight. Now, the authors have built a metal detector that can systematically scan the haystack, adjust its settings, and find new needles that were previously unknown. This helps scientists better understand the structure of quantum entanglement and test the limits of quantum theory.

Technical Summary

Technical Summary: Generating Non-Decomposable Maps with Differentiable Semidefinite Programming

Problem Statement

In quantum information theory, positive maps that are not completely positive are essential operational tools for detecting quantum entanglement. While completely positive maps describe physical quantum channels, general positive maps are required to identify entangled states that remain invisible to decomposable witnesses. Specifically, non-decomposable maps are crucial because they can detect bound entangled states with a positive partial transpose (PPT).

Despite their theoretical importance, the systematic construction of such maps remains a significant challenge. Explicit examples are scarce, particularly in higher dimensions, and existing methods often rely on generalizing known constructions rather than offering a broad, systematic generation framework. The primary difficulty lies in verifying positivity without complete positivity and ensuring non-decomposability, which are computationally demanding constraints.

Methodology

The authors introduce a numerical optimization framework based on differentiable semidefinite programming (SDP) to generate positive non-decomposable maps. The core innovation is the integration of SDP-based certificates directly into a gradient-based optimization loop, treating the verification of map properties as differentiable layers.

Key Components:

1. Choi Matrix Parametrization: The search space is defined by a parametrized Choi matrix $C$, which establishes a one-to-one correspondence with linear maps via the Choi–Jamiołkowski isomorphism. The matrix entries are treated as trainable variables.
2. Differentiable SDP Layers: The framework employs two distinct SDP formulations embedded within the optimization loop:
   • Non-decomposability Certificate ($\zeta_1$): An SDP (Eq. 17) that minimizes $\text{Tr}(\sigma C)$ over PPT states $\sigma$. If the optimal value $\zeta_1(C) < 0$, the map is certified as non-decomposable.
   • Positivity Certificate ($\zeta_k$): An SDP (Eq. 18) based on the $k$-symmetric extension method with PPT constraints. This tests positivity over the set of $k$-symmetrically extendable states. Since this set contains all separable states, a non-negative result ($\zeta_k(C) \ge 0$) certifies the map is positive (though the converse is not guaranteed, meaning the method searches a subset of all positive maps).
3. Loss Function: The optimization minimizes a composite loss function (Eq. 21):
   $$L(C) = \text{ReLU}(\epsilon + \zeta_1(C)) + \gamma \text{ReLU}(-\zeta_k(C))$$
   The first term drives $\zeta_1$ to negative values (ensuring non-decomposability), while the second term enforces $\zeta_k > 0$ (ensuring positivity). Hyperparameters $\epsilon$ and $\gamma$ control the strictness of these constraints.
4. Flexibility: The framework supports additional structural constraints, such as trace preservation (enforced via explicit parametrization of the Choi matrix), reality constraints (real-valued matrices), and heuristic masks to reduce the search space and reveal analytically tractable structures.

Key Contributions

1. Differentiable Optimization Framework: The paper presents a novel method that combines SDP certificates with gradient-based training (using Adam optimizer) to systematically search for positive non-decomposable maps across various input and output dimensions.
2. Generation of New Examples: The method successfully generates previously unknown numerical examples of positive non-decomposable maps in dimensions $d, d' \in \{2, 3, 4\}$.
3. Identification of Parametrized Families: By applying heuristic masks to the Choi matrix, the authors identified a new parametrized family of maps (Eq. 22) with specific zero-entry patterns, offering a structured approach to constructing such maps.
4. Construction of Real Maps: The framework was adapted to construct real non-decomposable maps (matrices with real entries) for dimensions $m=4$ and $m=5$ in the context of $C^2 \otimes C^m$, addressing questions regarding the mutual exclusivity of real block-positive operators and decomposability.
5. Exploration of Open Questions: The authors demonstrated the framework's adaptability to explore open problems in quantum information, specifically:
   • Eigenvalue Bounds: Investigating violations of a proposed bound for 2-positive trace-preserving maps.
   • PPT Square Conjecture: Numerically testing the conjecture that the composition of a positive map and a PPT map is always decomposable.

Results

• Success Rates: The algorithm achieved high success rates (up to 100%) in symmetric dimensions ($d=d'$), particularly for $d=3$ and $d=4$. Success rates were lower for asymmetric dimensions, a behavior the authors attribute to the relaxation properties of the $k$-symmetric extension on the smaller subsystem.
• New Map Families: The masked optimization revealed a family of maps defined by parameters $a, b, c$ and complex numbers $w, z$, providing a concrete analytical structure for further study.
• Real Non-Decomposable Maps: The authors explicitly constructed real non-decomposable maps for $m=4$ and $m=5$, recovering known existence results within a unified optimization framework.
• PPT Square Conjecture: In the tested regimes (specifically $T_1: B(C^2) \to B(C^4)$ and $T_2: B(C^4) \to B(C^2)$), the optimization did not find any counterexamples; all composed maps were found to be decomposable, providing numerical support for the conjecture.
• Eigenvalue Bound: The framework successfully identified both decomposable and non-decomposable maps that violate the proposed eigenvalue bound for 2-positive trace-preserving maps.

Significance and Claims

The paper claims that its primary significance lies in providing a flexible and systematic numerical tool for exploring the landscape of positive maps, a domain traditionally reliant on ad-hoc analytical constructions. By embedding SDP certificates into a differentiable loop, the method allows for the incorporation of specific structural constraints (like masks or reality conditions) that would be difficult to handle analytically.

The authors emphasize that while the positivity certification relies on $k$-symmetrically extendable states (a sufficient but generally stronger condition than strict positivity), the framework successfully identifies valid maps and reveals new structural families. They position this work not as a definitive proof of conjectures, but as a powerful exploratory tool that provides numerical evidence and new examples for open questions in entanglement theory, such as the PPT square conjecture and eigenvalue bounds. The framework is presented as a step toward bridging the gap between theoretical existence proofs and constructive, systematic generation of quantum maps.