⚛️ quantum physics

Optimising the relative entropy under semidefinite constraints

This paper presents an efficient method for computing provable upper and lower bounds on the minimal relative entropy of quantum states under semidefinite constraints by utilizing a recent integral representation to generate a sequence of semidefinite programs with sublinear convergence and gap estimates, thereby enabling critical applications in quantum information theory such as QKD key rate estimation and channel capacity computation.

Original authors: Gereon Koßmann, René Schwonnek

Published 2026-02-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gereon Koßmann, René Schwonnek

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

Imagine you are trying to measure the "distance" between two complex, blurry shapes. In the world of quantum physics, these shapes are quantum states (like the condition of a particle), and the distance between them is called relative entropy. This distance tells us how different two quantum states are, which is crucial for things like making unbreakable codes (Quantum Key Distribution) or measuring how "entangled" particles are.

However, calculating this distance is like trying to measure the exact volume of a cloud using a ruler. The math involved is incredibly tricky because it requires a "matrix logarithm," a calculation that is smooth on paper but a nightmare for computers to solve directly. It's like trying to find the lowest point in a valley that has a foggy, shifting floor.

The Core Problem

The authors, Gereon Koßmann and René Schwonnek, tackled a specific challenge: How do we find the minimum distance between two quantum states when we have to follow strict rules (constraints)?

Current methods either:

Are too slow and use too much computer power.
Give an answer but can't prove if it's the best possible answer (the true minimum).
Only give a "best guess" without knowing how far off they might be.

The Solution: The "Fence and Ladder" Analogy

The authors developed a new method that acts like building a fence around the answer. Instead of trying to calculate the exact, messy curve of the quantum distance all at once, they break the problem down into manageable steps.

Think of the quantum distance as a hilly landscape that you need to cross.

The Old Way: Trying to jump across the whole valley in one go, hoping you land on the lowest point.
The New Way: Building a series of stepping stones (a grid) across the valley.

The authors use a clever mathematical trick (an integral representation) to turn the smooth, curvy landscape into a series of straight lines.

The Lower Fence (The Floor): They build a floor underneath the landscape using straight lines. Because the landscape is "convex" (it curves upward like a bowl), they know the true answer is at least as high as this floor.
The Upper Fence (The Ceiling): They build a ceiling above the landscape. They know the true answer is at most as low as this ceiling.

By adding more stepping stones (grid points) to their bridge, they can make the floor rise and the ceiling lower, squeezing the true answer into a tighter and tighter space.

Why This is a Big Deal

The paper claims three major victories with this method:

Provable Bounds: Unlike other methods that just give a number, this method gives you a range. It says, "The answer is definitely between 5.0 and 5.2." As you add more stepping stones, that gap shrinks.
Efficiency: Even though they are adding more stepping stones, the computer doesn't get overwhelmed. The "size" of the math problem stays manageable, meaning it runs fast on standard computers.
The "Gap" Estimate: At every step of the calculation, the computer can tell you exactly how close it is to the perfect answer. It's like a GPS that doesn't just say "You are here," but also says, "You are within 10 meters of your destination."

Real-World Application Mentioned

The paper specifically highlights Quantum Key Distribution (QKD).

The Scenario: Imagine Alice and Bob are trying to send a secret message using quantum particles, while a hacker (Eve) tries to listen in.
The Need: To prove the message is safe, they need to calculate exactly how much "secret randomness" they can extract from their measurements. This calculation is the "distance" problem the authors solved.
The Result: Their method allows Alice and Bob to calculate a guaranteed minimum for their secret key rate. This means they can mathematically prove, with high confidence, that their encryption is secure, even with real-world, imperfect devices.

The "Magic" Grid

The authors didn't just throw random stepping stones down. They found a specific, smart pattern for placing them.

They start with a few stones.
They check the error (the gap between the floor and ceiling).
If the gap is too big, they add more stones in the specific areas where the landscape is curving the most.
They proved mathematically that if you follow this pattern, the error shrinks predictably. You don't need a million stones to get a good answer; you just need the right stones.

Summary

In simple terms, this paper provides a smart, efficient, and guaranteed way to measure the difference between quantum states. It turns a messy, impossible-to-solve math problem into a series of clean, solvable puzzles. It gives scientists a tool to say, "We know the answer is at least this much," which is the gold standard for proving security in quantum cryptography.

Technical Summary: Optimising the Relative Entropy under Semidefinite Constraints

Problem Statement
The central problem addressed is the minimization of the quantum relative entropy $D(\rho\|\sigma) = \text{tr}[\rho(\log \rho - \log \sigma)]$ subject to semidefinite constraints. This optimization arises in various quantum information tasks, most notably in estimating secret key rates for Quantum Key Distribution (QKD) from real device measurement statistics. The mathematical formulation seeks to find:
$\inf D(\rho\|\sigma) \quad \text{s.t.} \quad h_i(\rho, \sigma) \ge 0, \quad \mu\sigma \le \rho \le \lambda\sigma, \quad \rho, \sigma \in \mathcal{S}(\mathcal{H})$
where $h_i$ are affine maps representing measurement constraints. While the problem is convex, it is highly non-linear due to the matrix logarithm, rendering standard convex optimization solvers ineffective for general instances. Existing methods often struggle with numerical stability, lack provable convergence guarantees, or are restricted to specific constraint types (e.g., equality constraints only).

Methodology
The authors propose a method based on a recently introduced integral representation of the quantum relative entropy (Frenkel, 2023; Jenčová, 2015). For states satisfying $\mu\sigma \le \rho \le \lambda\sigma$ , the relative entropy is expressed as:
$D(\rho\|\sigma) = \int_{\mu}^{\lambda} \frac{ds}{s} \text{tr}_+[\sigma s - \rho] + \log \lambda + 1 - \lambda$
where $\text{tr}_+[A]$ denotes the trace of the positive part of $A$ . The core technical innovation is the discretization of this integral to transform the non-linear problem into a sequence of Semidefinite Programs (SDPs).

Discretization and SDP Formulation: The integral is approximated over a grid $t = (t_1, \dots, t_r)$ . By utilizing the property that $\text{tr}_+[A]$ can be formulated as an SDP (specifically, $\text{tr}_+[A] = \sup_{0 \le P \le 1} \text{tr}[PA]$ ), the authors derive a lower bound on the relative entropy. This results in a minimization problem over auxiliary variables $\mu_k$ subject to linear matrix inequalities.
Upper and Lower Bounds: The method provides both lower bounds ( $c_l(t)$ $c_{l} (t)$ ) and upper bounds ( $c_u(t)$ $c_{u} (t)$ ) on the optimal value.
- Lower Bound: Derived via convex interpolation (secant lines) of the integrand, formulated as an SDP.
- Upper Bound: Derived via convex interpolation from above, also formulated as an SDP.
Gap Estimation: The difference $\Delta(t) = c_u(t) - c_l(t)$ serves as a rigorous gap estimate to the optimum at any iteration stage.
Grid Refinement: The authors establish a recursive grid construction strategy (Corollary 1) that ensures sublinear convergence. The grid points are chosen such that the error decreases as $O(\sqrt{\lambda/\epsilon})$ , where $\epsilon$ is the target accuracy.

Key Contributions

Provable Bounds: The work provides a sequence of SDPs that yield rigorous, provable upper and lower bounds for the relative entropy minimization problem.
Convergence Guarantees: The paper proves sublinear convergence of the discretization scheme. Specifically, it demonstrates that the number of grid points required to achieve an error $\epsilon$ scales as $O(\sqrt{\lambda/\epsilon})$ .
Gap Quantification: Unlike many existing numerical heuristics, this method allows for the explicit calculation of the gap to the optimum at every step, enabling termination criteria based on desired precision.
Generalization to f-Divergences: The methodology is generalized to arbitrary $f$ -divergences, not just the Umegaki relative entropy, by leveraging the convexity properties of the function $g(s) = \text{tr}_+[\sigma s - \rho]$ .
Resource Efficiency: The approach maintains efficiency in terms of SDP matrix dimensions, avoiding the $d^2 \times d^2$ scaling required by methods that directly compute matrix logarithms.

Results
The authors validate their method through numerical benchmarks:

QKD Key Rates: Applied to entanglement-based QKD scenarios, the method successfully computes extractable randomness (key rates) for local dimensions up to 8 (3 qubits per party). The results are achieved in seconds on a standard personal computer.
Convergence Behavior: Numerical experiments confirm the predicted sublinear convergence rate. The error decreases as the number of grid points increases, consistent with the theoretical bounds derived in Corollary 1.
Comparative Performance: When compared to state-of-the-art methods (specifically [12] and [14]):
- The method achieves precision comparable to [12] for small instances but is strictly outperformed in precision by the specialized solver [14] for relative entropy programming.
- In terms of runtime, the proposed method shows a clear improvement over [12] but remains slower than [14].
- A distinct advantage is the ability to provide both upper and lower bounds and quantify the gap, whereas [12] provides only upper bounds and [14] is restricted to specific cones and lacks the integral representation flexibility for certain device-independent scenarios.

Significance and Claims
The paper claims that its primary significance lies in providing a practical, resource-efficient tool that bridges the gap between executable numerical tools and theoretical bounds. By converting the difficult non-linear optimization into a sequence of SDPs with provable convergence, the method enables reliable security proofs for QKD and other quantum information tasks where rigorous lower bounds on extractable randomness are essential.

The authors emphasize that while their method may not be the fastest in terms of raw runtime compared to specialized solvers like [14], its ability to handle general affine constraints (inequalities) and provide rigorous gap estimates makes it uniquely suited for applications requiring certified bounds, such as device-independent QKD and the estimation of channel capacities. The work also opens the door to numerically applicable algorithms for bounding the relative entropy of channels, an open problem in resource theories.