⚛️ quantum physics

Computational hardness of estimating quantum entropies via binary entropy bounds

This paper establishes the BQP-hardness of estimating quantum $\alpha$ -Rényi and $q$ -Tsallis entropies for all positive real orders (including infinity) by introducing new binary entropy inequalities that enable reductions to rank-2 variants, thereby proving these problems are BQP-complete when combined with existing quantum query algorithms.

Original authors: Yupan Liu

Published 2026-04-08

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Yupan Liu

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 a detective trying to solve a mystery about a secret code hidden inside a quantum machine. This code isn't just a string of numbers; it's a measure of confusion or disorder within the machine's state. In the world of physics, this "confusion" is called Entropy.

For a long time, scientists knew how hard it was to measure the "standard" confusion (called von Neumann entropy). But there are many other ways to measure confusion, like the Rényi and Tsallis entropies. Think of these as different lenses on a camera: one might zoom in on the rarest events, another on the most common ones. The big question was: Is it computationally impossible (hard) to figure out these specific types of confusion for quantum states?

This paper by Yupan Liu answers that question with a resounding "Yes, it is incredibly hard," but with a twist: it's hard even for the simplest possible quantum systems.

Here is the breakdown of the paper using everyday analogies:

1. The Mystery: Measuring Quantum "Confusion"

Imagine a quantum state as a bag of marbles.

If the bag has only one color of marble, there is no confusion. You know exactly what you'll pull out. (Zero Entropy).
If the bag has many colors mixed up, there is high confusion. (High Entropy).

The "standard" way to measure this is the von Neumann entropy. But physicists also use Rényi and Tsallis entropies. These are like asking:

"How confused are you if you only care about the rarest marble?" (Rényi)
"How confused are you if you weigh the marbles differently?" (Tsallis)

The paper asks: If I give you a quantum machine that prepares a bag of marbles, can you write a computer program to tell me if the "Rényi confusion" is high or low?

2. The Big Discovery: Even the Simplest Cases are Hard

Usually, when something is "hard" for a computer, it's because the problem is huge and complex (like sorting a million books).

However, this paper proves that even if the bag of marbles only has two colors (Rank-2), figuring out these specific entropies is as hard as the hardest problems a quantum computer can solve.

The Analogy:
Imagine trying to guess the outcome of a coin flip.

If the coin is fair (50/50), it's easy to describe.
If the coin is rigged, it's easy to describe.
But if the coin is rigged in a way that depends on a secret quantum calculation, guessing the "degree of rigging" is incredibly difficult.

The authors show that even for the simplest "two-color" quantum bags, calculating these specific entropy numbers is BQP-hard.

BQP stands for "Bounded-error Quantum Polynomial time." It's the class of problems a quantum computer can solve efficiently.
BQP-hard means: "If you could easily solve this entropy problem, you could solve any problem a quantum computer can solve." It's the "boss level" of difficulty.

3. The Secret Weapon: The "Binary Bridge"

How did they prove this? They didn't try to solve the whole bag of marbles at once. They built a bridge.

The Metaphor:
Imagine you want to measure the "messiness" of a complex room (the quantum state). Instead of measuring the whole room, you realize the room is made of just two specific items (a chair and a table).

The Bridge: They proved that the "messiness" of the whole room is mathematically linked to the "messiness" of just those two items.
The Known Hard Problem: They knew that measuring the relationship between those two items (specifically, how much they overlap) is already a known hard problem for quantum computers.
The Reduction: By showing that measuring the new "Rényi/Tsallis" messiness is just a different way of measuring that same hard relationship, they proved the new problem is also hard.

They used new mathematical inequalities (like a new set of rules for comparing apples and oranges) to build this bridge. Before this paper, we didn't have the right rules to connect these specific entropy types to the hard problems.

4. The Results: A Complete Map

The paper maps out exactly how hard these problems are for every possible setting:

For almost all settings: The problem is BQP-complete. This means it's the "perfect" hard problem for quantum computers: it's as hard as it gets, but a quantum computer can solve it if it tries hard enough.
For the "Order 0" setting: This is a special case where the entropy basically just counts how many colors are in the bag. The paper shows this is NQP-complete. This is a slightly different kind of hardness, related to problems where you just need to find one solution among many, rather than calculating a precise number.

5. Why Does This Matter?

You might ask, "Who cares about measuring confusion in a two-color bag?"

Security: Quantum cryptography (unhackable communication) relies on these entropy measures to prove that a secret key is truly random. If we didn't know these problems were hard, we might think a system is secure when it's actually weak.
Physics: These entropies help us understand how particles interact in extreme conditions (like black holes or superconductors). Knowing the computational limits helps physicists understand the fundamental limits of nature.
Computer Science: It tells us exactly what quantum computers are good at. It draws a line in the sand: "Here is what we can do efficiently, and here is where we hit a wall."

Summary

Think of this paper as a master key that unlocks the difficulty of measuring quantum confusion.

Before: We knew the "standard" confusion was hard to measure. We guessed the others might be too, but we couldn't prove it.
Now: We know that every type of Rényi and Tsallis confusion is just as hard as the hardest quantum problems, even for the simplest systems.
The Method: They built a clever mathematical bridge connecting these new measurements to a known hard problem, using a "two-item" shortcut.

In short: Measuring quantum disorder is a quantum superpower, and you need a full quantum computer to do it efficiently.

1. Problem Statement

The paper addresses the computational complexity of estimating quantum entropies for a quantum state $\rho$ prepared by a quantum circuit. Specifically, it investigates the Quantum $\alpha$ -Rényi Entropy Approximation ( $\text{RényiQEA}_\alpha$ ) and Quantum $q$ -Tsallis Entropy Approximation ( $\text{TsallisQEA}_q$ ) promise problems.

Definitions:
- Rényi Entropy: $S^R_\alpha(\rho) = \frac{\ln \text{Tr}(\rho^\alpha)}{1-\alpha}$
- Tsallis Entropy: $S^T_q(\rho) = \frac{1-\text{Tr}(\rho^q)}{q-1}$
- Both converge to the von Neumann entropy as the order approaches 1.
The Promise Problem: Given a quantum circuit preparing $\rho$ , decide if the entropy is at least $\tau_Y$ (Yes) or at most $\tau_N$ (No), where the gap $\tau_Y - \tau_N$ is a positive constant.
The Gap: While it was known that low-rank versions of these problems are in BQP (solvable efficiently by quantum computers), the hardness (BQP-hardness) was only established for:
- The von Neumann entropy ( $\alpha=1, q=1$ ).
- The Tsallis entropy for $1 \le q \le 2$ (under Turing reductions).
- The Rényi entropy hardness was unknown for general orders $\alpha \neq 1$ .

The central question is: Are these estimation problems BQP-hard for all positive orders $\alpha$ and $q$ ?

2. Methodology

The author introduces a novel proof technique that diverges from previous approaches relying on quantum Jensen-type divergences (which are restrictive regarding the order parameters).

A. Reduction to Rank-2 States

The core strategy reduces the general estimation problem to the Rank-2 case. The paper focuses on states of the form:
$\rho = \frac{1}{2}(|\psi_0\rangle\langle\psi_0| + |\psi_1\rangle\langle\psi_1|)$
where $|\psi_0\rangle$ and $|\psi_1\rangle$ are pure states prepared by quantum circuits.

B. Mapping to Binary Entropies

A crucial observation is that the quantum entropy of a rank-2 state $\rho$ is directly related to a binary entropy function of the overlap $x = \frac{1 - |\langle\psi_0|\psi_1\rangle|^2}{2}$ .

For Tsallis: $S^T_q(\rho) = H^T_q(x)$
For Rényi: $S^R_\alpha(\rho) = H^R_\alpha(x)$

C. Hardness Source

The paper leverages the known BQP-hardness of estimating the pure-state infidelity $1 - |\langle\psi_0|\psi_1\rangle|^2$ (or equivalently, the quantity $x$ ). If one can estimate the binary entropy $H(x)$ with constant precision, one can estimate $x$ , and thus solve the hard infidelity problem.

D. New Inequalities (The Technical Core)

To extend the hardness from the known hard case (Order 2) to all other orders, the author derives new inequalities relating binary entropies of different orders.

Key Insight: The binary entropy of order 2, $H_2(x)$ , is proportional to $x$ (specifically $4x(1-x)$ ).
Strategy: Prove that for any target order $\alpha$ (or $q$ ), the entropy $H_\alpha(x)$ is bounded above and below by constant multiples of $H_2(x)$ (or powers thereof) within the relevant range of $x$ .
Result: These inequalities allow a Karp reduction (many-one reduction) from the Order-2 problem to the Order- $\alpha$ problem. If Order-2 is hard, and Order- $\alpha$ is "sandwiched" by Order-2, then Order- $\alpha$ is also hard.

3. Key Contributions

A. New Inequalities for Binary Entropies

The paper establishes tight bounds relating $\alpha$ -Rényi and $q$ -Tsallis binary entropies to the 2nd-order binary entropy.

Rényi ( $\alpha$ ):
- For $0 < \alpha < 2$ : $H^R_\alpha(x) \le C_1 \cdot (H^R_2(x))^{\alpha/2}$ .
- For $\alpha \ge 2$ : $C_2 \cdot H^R_2(x) \le H^R_\alpha(x)$ .
Tsallis ( $q$ ):
- The bounds depend on the range of $q$ . Notably, for $2 < q \le 3$ , the monotonicity of the normalized Tsallis entropy changes, requiring a distinct case analysis.
- For $q > 3$ , the bounds involve different constants derived from the behavior of generalized binomial coefficients.

B. Complexity Class Characterization

The paper provides a complete classification of the computational hardness for these problems:

BQP-Hardness for Rank-2 States:
- Theorem: $\text{Rank2RényiQEA}_\alpha$ is BQP-hard for all $\alpha > 0$ (including $\alpha = \infty$ ).
- Theorem: $\text{Rank2TsallisQEA}_q$ is BQP-hard for all $q > 0$ .
- This holds even with a constant additive error gap.
BQP-Completeness for Low-Rank States:
- Combining the new hardness results with existing quantum query algorithms (which show these problems are in BQP for polynomial rank), the paper concludes:
  - $\text{LowRankRényiQEA}_\alpha$ is BQP-complete for all $\alpha > 0$ .
  - $\text{LowRankTsallisQEA}_q$ is BQP-complete for all $q > 0$ (specifically $q \le 1$ for low-rank, and $q > 1$ for general rank).
Order-0 Case (NQP-Completeness):
- For $\alpha=0$ and $q=0$ , the entropies relate to the rank of the state.
- The paper proves that estimating these order-0 entropies for rank-2 states is NQP-complete (equivalent to $\text{coC}_{=}\text{P}$ ). This is distinct from BQP, as the promise gap can be arbitrarily small.

4. Results Summary

Entropy Type	Order Range	Rank Constraint	Complexity Class
Rényi	$\alpha > 0, \alpha=\infty$	Rank-2	BQP-hard
Rényi	$\alpha > 0, \alpha=\infty$	Polynomial Rank	BQP-complete
Rényi	$\alpha = 0$	Rank-2	NQP-complete
Tsallis	$q > 0$	Rank-2	BQP-hard
Tsallis	$0 < q \le 1$	Polynomial Rank	BQP-complete
Tsallis	$q > 1$	General Rank	BQP-complete
Tsallis	$q = 0$	Rank-2	NQP-complete

5. Significance

Resolution of Open Problems: The paper fully resolves the question of whether estimating Rényi and Tsallis entropies captures the full power of quantum computation (BQP) for all orders. It confirms that even the simplest non-trivial case (rank-2 states) is sufficient to encode BQP-hardness.
Methodological Advancement: The approach using binary entropy inequalities is more flexible than previous methods based on Jensen divergences. It allows for a unified treatment of all orders, including cases where joint convexity (a property required by previous methods) fails.
Separation of Complexity Classes: It clarifies the boundary between BQP and NQP in the context of entropy estimation, showing that while positive orders are BQP-complete, the order-0 case (rank estimation) jumps to NQP-complete.
Foundational for Quantum Algorithms: By establishing the hardness of these problems, the paper sets a theoretical limit on what can be efficiently approximated. It implies that any efficient quantum algorithm for these tasks must rely on specific structural constraints (like low rank) or accept approximation errors that scale with the rank.

In conclusion, this work provides a comprehensive complexity-theoretic landscape for quantum entropy estimation, proving that the difficulty of these problems is intrinsic to the quantum nature of the states (specifically the difficulty of estimating state overlaps) rather than just the specific order of the entropy function.