⚛️ quantum physics

Matrix Majorization in Large Samples with Varying Support Restrictions

This paper employs real-algebraic methods to establish sufficient and nearly necessary conditions for matrix majorization in large samples and catalytic regimes under varying support restrictions, characterizing these conditions through generalized multivariate divergences that extend Rényi divergences and have applications in quantum thermodynamics.

Original authors: Frits Verhagen, Marco Tomamichel, Erkka Haapasalo

Published 2026-07-27

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Frits Verhagen, Marco Tomamichel, Erkka Haapasalo

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

=== DRAFT ===
Imagine you are a chef trying to figure out if you can turn one recipe into another. You have a basket of ingredients (let's call them "states") and a set of rules for cooking (a "stochastic map"). In the world of information science, this is like asking: "Can I transform a messy, uncertain situation into a more organized one using only fair, random mixing?" This field is called majorization. It's the mathematical way of saying, "Is this pile of stuff 'bigger' or 'more powerful' than that pile?"

Now, imagine you have a magic helper called a catalyst. In chemistry, a catalyst speeds up a reaction without being used up. In this math world, a catalyst is a special extra ingredient you can borrow to help the transformation, as long as you return it exactly as you found it at the end. Scientists have long known how to compare these piles when every single ingredient in the basket is available everywhere (they all have the same "support"). But what happens if some ingredients are missing from certain spots? What if your "recipe" has holes in it? This is the tricky puzzle this paper tackles: figuring out the rules for transforming these "holey" recipes when you have a huge number of copies or a magic helper.

The Great Recipe Swap: When Ingredients Don't Match Up

In the world of quantum physics and statistics, scientists often deal with "experiments" that are really just lists of probabilities. Think of these lists as columns in a giant spreadsheet. Usually, researchers assumed that every column in the spreadsheet had numbers in the exact same rows—like a grid where every cell is filled. But in real life, and in complex quantum systems, some cells are empty. Some ingredients just aren't there.

The authors of this paper, Frits Verhagen, Marco Tomamichel, and Erkka Haapasalo, decided to stop pretending the grid was perfect. They asked: What are the rules for swapping these messy, "holey" recipes when we have a massive amount of them (large samples) or when we use a magic helper (catalysis)?

The "Holey" Grid Problem

Imagine you have two sets of dice rolls.

Set A has rolls that can land on 1, 2, or 3.
Set B has rolls that can only land on 1 or 2.

In the old rules, you couldn't easily compare these because the "support" (the places where numbers exist) was different. The authors realized that if you try to use the old math, you get stuck. They needed a new way to measure the "size" or "power" of these sets that accounts for the missing numbers.

They found that the answer lies in a family of mathematical tools called divergences. You can think of these as special rulers.

Some rulers measure the "average" difference between the recipes.
Some measure the "worst-case" difference.
Some measure how the recipes behave when you zoom in on specific parts of the grid.

The paper proves that to know if you can turn Recipe P into Recipe Q, you don't just need one ruler. You need to check a whole family of these rulers. If Recipe P scores higher than Recipe Q on every single one of these rulers, then the transformation is possible. However, for exact transformations, these conditions are sufficient and almost necessary, meaning they cover almost all cases but might have very specific edge cases where the rules are slightly different.

The Two Main Scenarios

The authors split their investigation into two main playgrounds:

The "Minimal Restrictions" Playground: Here, the only rule is that the recipes must share some common ground. They don't have to match perfectly, but they can't be completely disjoint (like one recipe only having apples and the other only having oranges with no overlap). In this scenario, the authors found that the "rulers" needed are a specific set of multivariate generalizations of the Rényi divergences. These are fancy formulas that look at how the probabilities interact across the whole grid.
The "Dominating Column" Playground: This is a special case where one specific column (let's call it the "Boss Column") has numbers wherever all the other columns have numbers. It's like having a master key that opens every door the other keys can open, plus a few more. This scenario is super important for quantum thermodynamics (the study of heat and energy in tiny quantum machines). Here, the "Boss Column" represents the thermal state of the universe (the heat bath). The authors found that in this case, the rules change slightly. You need to check not just the usual rulers, but also some "boundary" rulers that look specifically at the relationship between the "Boss" and the others.

The Magic of "Power Universals"

One of the coolest discoveries in the paper is about something called a power universal. Imagine you have a "super-recipe" that is so versatile, you can use it to transform any other recipe into any other recipe (as long as the rules allow). The authors figured out exactly what this "super-recipe" looks like.

It turns out, for a recipe to be this versatile, it must have a very specific structure regarding its "holes." For example, in the "Dominating Column" case, the "Boss Column" must strictly contain the others (it must have more numbers, not just the same ones), and the other columns must not be subsets of each other.

Crucially, the paper notes that for "approximate" transformations (where you allow a tiny bit of error), the starting recipe must be this "power universal" type. If your recipe doesn't meet these strict criteria, the math gets much harder, and the authors suggest you might need to build a custom "playground" (a new semiring) just for that specific recipe. This means the "exact map" provided by the paper applies perfectly to these versatile cases, but for other specific "holey" recipes, the conditions are slightly more complex to derive.

Why Should You Care?

You might be thinking, "Okay, but what does this have to do with my life?"

The paper points to a direct application in Quantum Thermodynamics. Imagine a tiny quantum computer or a nanomachine that needs to cool down or change its energy state. To do this, it interacts with a heat bath (the "Boss Column"). The rules the authors discovered tell us exactly when a quantum machine can change its state without violating the laws of thermodynamics, even if the machine isn't perfectly efficient (i.e., it has "holes" or missing energy states).

Previously, scientists had to make approximations to solve this, which sometimes led to errors. This paper provides a rigorous, near-exact map for the most common and versatile cases. It says, "If your quantum state looks like this (and meets the power universal criteria), and you want to turn it into that, here is the exact checklist of inequalities you must satisfy." For states that don't fit this perfect mold, the paper offers a strategy to build a custom set of rules.

The Bottom Line

The authors didn't just guess; they used a powerful branch of math called real algebraic geometry (specifically tools called Vergleichsstellensätze) to prove their findings. They showed that:

Exact Transformation: If you have a huge number of copies, you can transform P into Q if P scores strictly higher than Q on a specific set of divergence "rulers." These conditions are sufficient and almost necessary.
Approximate Transformation: If you are okay with a tiny bit of error (which is usually fine in the real world), the rules are slightly more flexible, but they strictly require the starting state to be a "power universal."
The Catalyst: Using a catalyst (borrowing a helper) is almost as powerful as having infinite copies, but not quite. The paper clarifies the exact difference between these two scenarios when the "holes" in the data are different.

In short, this paper takes a messy, real-world problem where data is incomplete and gives us a precise, mathematical toolkit to understand how information and energy can flow between systems. It's like finally getting the instruction manual for a complex machine that everyone was trying to figure out by trial and error, with a clear note on which specific machine models the manual covers perfectly and which ones need a custom appendix.

Technical Summary: Matrix Majorization in Large Samples with Varying Support Restrictions

Problem Statement
The paper addresses the problem of matrix majorization, a generalization of statistical experiment comparison. Given two finite statistical experiments $P = \{p^{(k)}\}_{k=1}^d$ and $Q = \{q^{(k)}\}_{k=1}^d$ (represented as matrices with columns $p^{(k)}$ and $q^{(k)}$ ), $P$ majorizes $Q$ ( $P \succeq Q$ ) if there exists a stochastic matrix $T$ such that $Q = TP$. The authors investigate two specific regimes:

Large-sample majorization: Whether $P^{\otimes n} \succeq Q^{\otimes n}$ for sufficiently large $n$ .
Catalytic majorization: Whether $P \otimes R \succeq Q \otimes R$ for some catalyst $R$ .

Previous work (specifically [14]) characterized these regimes under the strict assumption that all columns within a given matrix share a common support (i.e., $\text{supp}(p^{(1)}) = \dots = \text{supp}(p^{(d)})$ ). This paper removes that assumption, studying cases where columns have varying support structures. Specifically, it analyzes:

Minimal restrictions: The intersection of all supports is non-empty ( $\bigcap_k \text{supp}(p^{(k)}) \neq \emptyset$ ), but no column necessarily dominates another.
Dominating column: One column (typically the last) contains the support of all others ( $\text{supp}(p^{(k)}) \subseteq \text{supp}(p^{(d)})$ for $k < d$ ).

The authors note that relaxing support assumptions dramatically alters the set of relevant divergences required to characterize majorization, as limits of parameters and support restrictions do not commute.

Methodology
The authors employ real-algebraic methods, specifically the theory of preordered semirings and the Vergleichsstellensätze (comparison theorems) developed in [16, 17].

Semiring Construction: They define preordered semirings ( $S_d$ for minimal restrictions and $S_d^{d.c.}$ for the dominating column case) where elements are equivalence classes of matrices under row permutations and zero-padding. The operations are component-wise concatenation (addition) and Kronecker product (multiplication).
Order Characterization: Using the Vergleichsstellensatz (Theorem 2), they relate the asymptotic ordering of elements in the semiring to inequalities involving monotone homomorphisms and monotone derivations mapping the semiring to specific target semirings ( $\mathbb{R}_+$ , $\mathbb{R}_+^{op}$ , tropical reals, etc.).
Identification of Monotones: A significant portion of the work involves explicitly characterizing the set of non-degenerate monotone homomorphisms and derivations for these specific semirings. Unlike the common-support case, the varying support conditions introduce discontinuities and new boundary terms in the parameter space of the divergences.
Power Universals: They identify "power universal" elements (matrices that can asymptotically generate any other matrix in the semiring) within these specific support constraints, which is a prerequisite for applying the comparison theorems.

Key Contributions and Results

Minimal Restrictions Case (Section 3):
- The authors derive sufficient and almost necessary conditions for exact and asymptotic large-sample/catalytic majorization (Theorems 13 and 14).
- The conditions are expressed via inequalities involving a family of multivariate divergences $D_\alpha(P)$ .
- Crucially, they identify that when the support of the columns is not identical, new quantities arise corresponding to the boundaries of the parameter simplex $A_+$ . These involve restricting the vectors to the intersection of supports of subsets of columns (e.g., $D_\alpha(p^{(1)}|_{\text{supp } p^{(2)}} \| p^{(3)}|_{\text{supp } p^{(2)}})$ ).
- They show that if the strict inequalities hold, the matrix $P$ is automatically power universal.
Dominating Column Case (Section 4):
- For the case where $\text{supp}(p^{(k)}) \subseteq \text{supp}(p^{(d)})$ , the authors derive analogous conditions (Theorem 24).
- The set of relevant divergences changes: it includes standard multivariate divergences on the interior, but also specific one-parameter families of divergences (related to Rényi divergences between the dominating column and others) and max-divergences ( $D_\infty$ ).
- Dichotomies ( $d=2$ ): A significant simplification occurs for pairs $(p^{(1)}, p^{(2)})$ where $\text{supp}(p^{(1)}) \subseteq \text{supp}(p^{(2)})$ . The authors prove (Corollary 26, Theorem 27) that majorization is characterized entirely by the standard Rényi divergences $D_\alpha(p^{(1)} \| p^{(2)})$ for $\alpha \in [0, \infty]$ . This resolves the characterization for "dichotomies" with non-full support.
Optimal Rates:
- The paper provides a formula for the maximal achievable rate of transforming $P$ to $Q$ in the large-sample regime: $r(P \to Q) = \min_{D \in \mathcal{D}} \frac{D(P)}{D(Q)}$ , where $\mathcal{D}$ is the set of relevant monotone divergences (Corollary 29).
Application to Quantum Thermodynamics (Section 5.2):
- The results are applied to catalytic thermal majorization. For quantum states diagonal in the energy eigenbasis, thermal majorization reduces to matrix majorization where the second column is the Gibbs state (which dominates all other states).
- The authors provide a complete characterization of asymptotic catalytic thermal majorization for states of arbitrary rank (including non-full support), resolving technical convergence issues present in previous literature [7].
- They show that for a state $\rho$ not of full rank, the condition simplifies to $D_\alpha(\lambda_\rho \| \lambda_\beta) \geq D_\alpha(\lambda_\sigma \| \lambda_\beta)$ for all $\alpha \geq 0$ , where $\lambda$ represents the eigenvalue vectors.

Significance and Claims
The paper claims to fill a gap in the theory of statistical experiment comparison by removing the restrictive "common support" assumption found in prior work [14]. The authors emphasize that varying support conditions fundamentally change the set of necessary and sufficient conditions, introducing new divergences that arise from the non-commutativity of limits in the parameter space.

The work serves as a "proof of concept" for applying semiring methods to problems with complex support structures. A primary practical contribution is the rigorous resolution of the asymptotic catalytic thermal majorization problem for general-rank quantum states, offering a direct derivation without the embedding approximations used in earlier studies. The authors note that while their results provide sufficient conditions for exact majorization and necessary/sufficient conditions for asymptotic majorization, the requirement for the input matrix to be "power universal" in the asymptotic case remains a technical constraint that may require tailored semirings for specific support structures in future work.