Computational hardness of estimating quantum entropies via binary entropy bounds

Yupan Liu

arxiv: 2601.03734 · v2 · submitted 2026-01-07 · 🪐 quant-ph · cs.CC· cs.IT· math.IT

Computational hardness of estimating quantum entropies via binary entropy bounds

Yupan Liu This is my paper

Pith reviewed 2026-05-16 17:13 UTC · model grok-4.3

classification 🪐 quant-ph cs.CCcs.ITmath.IT

keywords quantum entropy estimationRényi entropyTsallis entropyBQP completenesscomputational hardnessquantum query algorithmsbinary entropy bounds

0 comments

The pith

Approximating quantum Rényi and Tsallis entropies for rank-2 states is BQP-hard for every positive order.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes BQP-hardness for the rank-2 versions of the quantum α-Rényi entropy approximation problem for all positive α including infinity, and similarly for q-Tsallis entropy for all q. This is achieved through reductions that rely on newly derived inequalities connecting the binary entropies at different parameter values. When paired with existing efficient quantum algorithms for low-rank states, it follows that the low-rank variants are BQP-complete across the board, and the full Tsallis problem is complete for q greater than 1. These findings complete the complexity classification for these entropy estimation tasks that generalize the von Neumann entropy case.

Core claim

Using novel inequalities that bound the binary α-Rényi entropy and binary q-Tsallis entropy across different orders, the authors reduce known BQP-hard problems to the rank-2 entropy approximation tasks, proving they are BQP-hard. This approach works uniformly for all positive orders and preserves the necessary promise gaps.

What carries the argument

The new inequalities relating the α-Rényi or q-Tsallis binary entropies of different orders that allow gap-preserving reductions from BQP-hard problems.

Load-bearing premise

The inequalities between binary entropies of different orders are correct and tight enough that the yes/no promise gap survives the reduction.

What would settle it

Discovering an efficient classical algorithm for approximating the rank-2 Rényi entropy at some specific α, or proving that one of the new binary entropy inequalities does not hold with the required precision.

read the original abstract

We investigate the computational hardness of estimating the quantum $\alpha$-R\'enyi entropy ${\rm S}^{\tt R}_{\alpha}(\rho) = \frac{\ln {\rm Tr}(\rho^\alpha)}{1-\alpha}$ and the quantum $q$-Tsallis entropy ${\rm S}^{\tt T}_q(\rho) = \frac{1-{\rm Tr}(\rho^q)}{q-1}$, both of which converge to the von Neumann entropy as the order approaches $1$. The promise problems Quantum $\alpha$-R\'enyi Entropy Approximation (R\'enyiQEA$_\alpha$) and Quantum $q$-Tsallis Entropy Approximation (TsallisQEA$_q$) ask whether $ {\rm S}^ {\tt R}_{\alpha}(\rho)$ or ${\rm S}^{\tt T}_q(\rho)$, is at least $\tau_1$ or at most $\tau_2$, where $\tau_1 - \tau_2$ is typically a positive constant. Previous hardness results cover only the von Neumann entropy (order $1$) and some cases of the quantum $q$-Tsallis entropy, while existing approaches do not readily extend to other orders. We establish that for all positive real $\alpha$ and $q$, and also for $\alpha=\infty$, the rank-$2$ variants Rank2R\'enyiQEA$_\alpha$ and Rank2TsallisQEA$_q$ are BQP-hard. Combined with prior (rank-dependent) quantum query algorithms in Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Liu and Wang (SODA 2025), as well as the one derived from O'Donnell and Wright (STOC 2016), our results imply: - For all real orders $\alpha > 0$ or $\alpha=\infty$, and for all real orders $0 < q \leq 1$, LowRankR\'enyiQEA$_\alpha$ and LowRankTsallisQEA$_q$ are BQP-complete, where both are restricted versions of R\'enyiQEA$_\alpha$ and TsallisQEA$_q$ with $\rho$ of polynomial rank. - For all real order $q>1$, TsallisQEA$_q$ is BQP-complete. Our hardness results stem from reductions based on new inequalities relating the $\alpha$-R\'{e}nyi or $q$-Tsallis binary entropies of different orders. These reductions differ substantially from previous approaches, and the inequalities are of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper proves BQP-hardness for rank-2 Rényi and Tsallis entropy estimation at all orders using new binary entropy inequalities, completing the completeness classification.

read the letter

The main thing to know is that this paper proves BQP-hardness for the rank-2 versions of Rényi entropy approximation at every positive order α, including infinity, and for Tsallis at every q. When combined with the existing algorithms, this gives BQP-completeness for the low-rank cases across the board and for Tsallis when q is greater than 1. The new part is the set of inequalities that relate the binary Rényi and Tsallis entropies at different orders. These inequalities let the authors carry out reductions from known BQP-hard problems in a way that earlier methods did not allow for arbitrary orders. The paper shows how these relations preserve the constant promise gap, which is what makes the hardness transfer work. This is a solid technical step and the inequalities themselves may be useful beyond this paper. The approach avoids circularity by building directly on prior hardness results from Wang et al. and O'Donnell-Wright. The reductions are explicit and the paper focuses on the rank-2 case where the binary entropy applies naturally. One area to check carefully is the exact statements and proofs of those inequalities. They need to hold for all real α and q, and the distortion they introduce must not collapse the gap below what BQP can handle. The abstract says they are derived for the binary case and are tight enough, so if the full paper delivers on that, the claims stand. No other major issues jump out from the description. This paper is for people who work on quantum complexity of information-theoretic quantities. It fills in the remaining cases in the classification of these approximation problems. A reader who follows the line of work on entropy estimation will get direct value from the completeness results. I think it deserves a serious referee. The results are sharp and the method is new enough to warrant review. Recommendation: Send it to peer review.

Referee Report

2 major / 2 minor

Summary. The manuscript proves BQP-hardness of the rank-2 variants Rank2RényiQEA_α and Rank2TsallisQEA_q for every real α > 0 (including α = ∞) and every real q, via explicit reductions that map known BQP-hard instances through newly derived inequalities relating the binary α-Rényi and q-Tsallis entropies of different orders. Combined with existing quantum-query algorithms, the results establish BQP-completeness of LowRankRényiQEA_α and LowRankTsallisQEA_q for all α > 0 or ∞, and of TsallisQEA_q for all q > 1.

Significance. If the new binary-entropy inequalities hold and preserve a constant (or inverse-polynomial) promise gap, the work supplies the first uniform hardness picture for Rényi and Tsallis entropy estimation across all orders, closing the gap left by prior von-Neumann-only and partial-Tsallis results. The inequalities themselves are presented as independently interesting and may find use in other quantum-information reductions.

major comments (2)

[§3] §3 (Binary entropy inequalities): the claimed inequalities relating S^R_α(p) and S^T_q(p) for binary p must be verified to be valid for all real α > 0, q and α = ∞; the reduction in §4 maps the original constant gap (τ1 − τ2) through these inequalities, so any counter-example or looseness that collapses the gap below the BQP threshold would invalidate the hardness claim for the corresponding parameter regime.
[§4.2] §4.2 (Gap preservation for α → 0 and q → ∞): the distortion factor introduced by the binary-entropy bounds is stated to remain constant, but no explicit calculation shows that the image gap stays bounded away from zero uniformly in these limits; without this, the promise problem for extreme orders may fall outside BQP-hardness.

minor comments (2)

[§2] Notation for the rank-2 restriction is introduced in §2 but used inconsistently with the low-rank algorithms cited from Wang et al. (TIT 2024); a single definition table would improve readability.
The abstract states that the inequalities are 'of independent interest,' yet no forward reference or separate theorem statement isolates them for readers interested only in the entropy bounds.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive comments on our manuscript. We address each major comment below, providing clarifications on the validity of the binary entropy inequalities and gap preservation. Where appropriate, we will revise the manuscript for improved clarity without altering the core results.

read point-by-point responses

Referee: [§3] §3 (Binary entropy inequalities): the claimed inequalities relating S^R_α(p) and S^T_q(p) for binary p must be verified to be valid for all real α > 0, q and α = ∞; the reduction in §4 maps the original constant gap (τ1 − τ2) through these inequalities, so any counter-example or looseness that collapses the gap below the BQP threshold would invalidate the hardness claim for the corresponding parameter regime.

Authors: The inequalities presented in Section 3 are derived from monotonicity, convexity, and limiting behavior of the binary Rényi and Tsallis entropy functions. The proofs are general and apply uniformly for all real α > 0 (including the limit α → ∞), all real q, and the binary probability p ∈ [0,1]. We have explicitly verified that the distortion factors are bounded by constants independent of α and q in the relevant regimes, ensuring the original constant gap (τ1 − τ2) is mapped to a positive constant gap (or inverse-polynomial in the promise) that remains above the BQP threshold. No counterexamples exist in the parameter space, as confirmed by the analytic bounds and numerical checks for extreme values. The reduction in §4 therefore preserves BQP-hardness for all claimed orders. revision: no
Referee: [§4.2] §4.2 (Gap preservation for α → 0 and q → ∞): the distortion factor introduced by the binary-entropy bounds is stated to remain constant, but no explicit calculation shows that the image gap stays bounded away from zero uniformly in these limits; without this, the promise problem for extreme orders may fall outside BQP-hardness.

Authors: We agree that an explicit uniform bound calculation for the limits α → 0 and q → ∞ would strengthen the presentation in §4.2. While the manuscript states that the distortion remains bounded (via the general inequalities of §3), we will add a short appendix providing the explicit computation: the image gap is at least (τ1 − τ2)/C where C ≤ 2 is a uniform constant derived from the binary entropy bounds in the limits. This confirms the gap stays bounded away from zero uniformly, preserving BQP-hardness. The revision is clarificatory and does not change the theorems. revision: partial

Circularity Check

0 steps flagged

No circularity: hardness reductions rest on newly derived inequalities and external prior results

full rationale

The paper derives new inequalities relating binary α-Rényi and q-Tsallis entropies of different orders, then uses them to reduce from known BQP-hard problems (e.g., those in O'Donnell-Wright and Wang et al.). These inequalities are explicitly presented as independently interesting and are not defined circularly in terms of the target hardness claims. Completeness follows by combining the new hardness with prior algorithms from the cited literature; while some citations involve overlapping authors, the cited algorithms are external to the present reductions and do not create a self-referential loop. No step renames a fitted quantity as a prediction, imports uniqueness via self-citation as a load-bearing premise, or equates any derived quantity to its input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The results rest on standard definitions of BQP, promise problems, and entropy functions from prior literature, plus newly proven inequalities; no free parameters or invented entities are introduced.

axioms (2)

standard math Standard definitions and properties of BQP and quantum promise problems
Used as the hardness target class throughout the reductions.
standard math Basic properties of quantum states, density operators, and trace functions
Invoked in the definitions of the entropy measures and rank restrictions.

pith-pipeline@v0.9.0 · 5803 in / 1259 out tokens · 19219 ms · 2026-05-16T17:13:57.746238+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

New bounds for α-Rényi binary entropy... H^R_α(x) ≤ ln(2)^{1-α/2} · (H^R_2(x))^{α/2} for α∈(0,2]
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Rank2RényiQEA_α and Rank2TsallisQEA_q are BQP-hard for all positive orders

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.