Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds

In this work, we show that Rank2RényiQEA_$\alpha$ and Rank2TsallisQEA_q are BQP-hard for all positive orders $\alpha$ and $q$, even with constant additive-error precision (Theorem 2). Our results fully resolve Problem 1 in the low-rank setting and introduce a new, systematic approach to establishing the computational hardness of estimating quantum entropies.

We next summarize the known quantum query upper bounds for estimating quantum entropies [65, 68, 43], as presented in Table 1.²²2The notation $\tilde{O}(f)$ is used to denote $O(f\mathrm{polylog}(f))$. The input model underlying these upper bounds is the purified quantum access input model, originally introduced in [70]. In particular, these upper bounds imply containments of complexity classes when the descriptions of the state-preparation circuits (“source codes”) are explicitly provided.

By combining Theorem 2 with the quantum query algorithms of [65, 68, 43], whose upper bounds are summarized in Table 1, we obtain the following corollaries:

It is worth highlighting that the rank-$2$ case is the smallest non-trivial rank that captures BQP-hardness of estimating quantum entropies, since all pure states (i.e., the rank-$1$ case) have zero entropy. By contrast, for closeness testing of quantum states with respect to the trace distance, BQP-hardness already arises in the pure-state setting [51, 66]. The possibility that rank-$2$ instances capture BQP-hardness was implicitly suggested in [43]. Our proof of Theorem 2 further clarifies the underlying reason: the reduction essentially relies on inequalities relating quantum binary entropies of different orders (see Section 1.3 for details).

In addition to estimating quantum entropies of positive orders, we also investigate the order-zero case for quantum Rényi and Tsallis entropies, as stated in Theorem 5. For the Rényi entropy, this case corresponds to the quantum max (Hartley) entropy; while for the Tsallis entropy, it essentially coincides with the rank of the state.

Notably, the behavior of quantum query upper bounds for estimating these order-zero entropies aligns with Theorem 5: such bounds scale polynomially with the reciprocal of the smallest non-zero eigenvalue of the state [65, Section III.B], which can be arbitrarily small in general. In particular, the complexity class NQP can be viewed as a precise variant of BQP that always rejects no instances, where the promise gap may be arbitrarily small. This class is equal to the classical class ${\mathrm{𝖼𝗈𝖢}}_{=}𝖯=\text{NQP}$ [3, 75], where ${𝖢}_{=}𝖯$, introduced in [63], is closely related to the standard counting class PP, since ${𝖢}_{=}𝖯\subseteq \text{PP}\subseteq {\text{NP}}^{{𝖢}_{=}𝖯}$.³³3Since PP is closed under complement, it follows that ${\mathrm{𝖼𝗈𝖢}}_{=}𝖯\subseteq \text{PP}$. For further details and properties of ${𝖢}_{=}𝖯$, which lies within the counting hierarchy, we refer to [72].

Before presenting the proof techniques underlying Theorem 2, we briefly review known approaches to establishing the computational hardness of the Quantum Entropy Approximation Problem (QEA) and its variants. One standard approach proceeds via the Quantum Entropy Difference Problem (QED), which concerns the quantity $\mathrm{S}({\rho }_0)-\mathrm{S}({\rho }_1)$ and can be solved using a search version of QEA.⁴⁴4Specifically, one can decide whether a given QED instance corresponding to $({\rho }_0,{\rho }_1)$ is a yes or no instance by estimating $\mathrm{S}({\rho }_0)$ and $\mathrm{S}({\rho }_1)$ separately to the required precision. The key quantity in this approach is the distance version of the (quantum) entropy difference [59, 5], namely the quantum Jensen–Shannon divergence (QJS) introduced in [44],

whose square root is a distance metric [62, 54]. A particularly direct proof was recently outlined in [43, Equation (4)], crucially relying on the following identity:

By combining Equation 1 with known inequalities relating QJS to the trace distance [23, 9], one can directly reduce the Quantum State Distinguishability Problem (QSD), defined in terms of the trace distance, to QED. Since QSD is QSZK-hard [70, 71], it follows that QED is QSZK-hard under Karp reduction, and consequently, QEA is QSZK-hard under Turing reduction.

The tailor-made approach described above applies only to the order-$1$ case (von Neumann entropy). A more general method for proving the QSZK-hardness of QED, developed in [5] (see also a simplified version in [40]), relies on additional information-theoretic tools, including Fannes’ inequality. This method extends naturally to the promise problems TsallisQEA_q and TsallisQED_q for , which are defined in [43] and correspond to the quantum $q$-Tsallis entropy of the relevant orders. The key quantity in this extension is the quantum $q$-Jensen-Tsallis divergence (QJT_q) introduced in [9], whose square root also serves as a distance metric [54]. The main technical challenge lies in the corresponding inequalities relating these divergences to the trace distance, which were established only very recently in [43, Section 4], using the joint convexity of QJT_q for the relevant orders [17, 61]. The proof is then completed in analogy with the order-$1$ case, employing Fannes’ inequality and the basic properties of the quantum $q$-Tsallis entropy as provided in [50, 24, 78], and the argument requires a complicated trade-off in choosing parameters.

Nevertheless, such joint convexity properties do not hold in general for the (quantum) $q$-Tsallis entropy of arbitrary order $q$, even in the classical case [12]. In addition, although the quantum $\alpha$-Jensen-Rényi divergence (${\mathrm{QJR}}_{\alpha }$) was studied a few years ago in [54] and shown to be the square of a metric for , its joint convexity has not been investigated and may not hold for positive order $\alpha$ in general.

Another common approach is to reduce the Quantum State Closeness to Maximally Mixed State (QSCMM) to QEA. This promise problem, defined via the trace distance with the state ${\rho }_1$ fixed to be the $n$-qubit maximally mixed state ${(I/2)}^{\otimes n}$, is complete for the class NIQSZK [34, 5, 14]. These reductions rely on inequalities that relate different quantum entropies, such as the von Neumann entropy, to the trace distance $\mathrm{T}(\rho ,{(I/2)}^{\otimes n})$, which can be characterized through optimization problems. In particular, the optimization problem corresponding to the easy direction is typically convex, such as [35, Lemma 16], while the one for the hard direction may be non-convex in general,⁵⁵5For the order-$1$ case, the hard direction follows directly from the inequality in [60]. as in the case of the quantum $q$-Tsallis entropy ${\mathrm{S}}_q^{𝚃}(\rho )$ with $q=1+\frac{1}{n-1}$ [43, Section 4.4].

Since solving non-convex optimization problems, even approximately, is often technically challenging, this approach does not extend readily to quantum entropies of positive orders and requires further work in the low-rank setting. In particular, it is necessary to establish analogous inequalities that connect ${\mathrm{S}}_q^{𝚃}(\rho )$ with $\mathrm{T}(\rho ,{\rho }_{𝚄})$, where ${\rho }_{𝚄}$ denotes an $n$-qubit quantum state of polynomially bounded rank with uniformly distributed eigenvalues.

We now outline the proof strategy underlying Theorem 2. Our starting point is an alternative and simplified argument establishing that Rank2QEA is BQP-hard, which serves as an illustrative example of our new approach. While this hardness result was already shown in [43, Theorem 1.2(1)], their proof establishes BQP-hardness only under Turing reduction, specifically through reductions to the counterpart quantum entropy difference problem.⁶⁶6Nevertheless, unlike other quantum complexity classes such as QSZK, BQP-hardness under Turing reduction is no weaker than BQP-hardness under Karp reduction, since the BQP subroutine theorem [6, Section 4] implies that ${\text{BQP}}^{𝒜}\subseteq \text{BQP}$ holds for any efficient quantum algorithm $𝒜$.

Our method is guided by two key observations. The first observation is the following identity: the quantum $2$-Tsallis entropy of a rank-$2$ state $\frac{1}{2}(|{\psi }_0⟩⟨{\psi }_0|+|{\psi }_1⟩⟨{\psi }_1|)$, which in some sense is “BQP-hard to prepare”, coincides with the $2$-Tsallis binary entropy ${\mathrm{H}}_2^{𝚃}(x)$:

In particular, these expressions are proportional to $1-{\left|⟨{\psi }_0|{\psi }_1⟩\right|}^2$, whose constant-precision estimation is known to be BQP-hard [51]. This equivalence immediately implies the BQP-hardness of ${\text{Rank2TsallisQEA}}_2$. To extend the hardness result to Rank2TsallisQEA_q for other orders $q$, including the order-$1$ case, i.e., the von Neumann entropy, it suffices to establish inequalities relating ${\mathrm{H}}_2^{𝚃}(x)$ to the $q$-Tsallis binary entropy.

The second observation is that the (Shannon) binary entropy admits the following power-type bounds, which have been known for more than two decades [57, 39], and can be expressed in terms of the $2$-Tsallis binary entropy:⁷⁷7The lower bound is a special case of [31, Theorem II.6], with a direct proof given in [57]. The upper bound can be further strengthened to $\mathrm{H}(x)\le 2^{\frac{1}{2\mathrm{H}(1/2)}}\mathrm{H}\left(1/2\right)\cdot {\mathrm{H}}_2^{𝚃}{(x)}^{\frac{1}{2\mathrm{H}(1/2)}}$ (see [57, Theorem 1.2]).

Taken together, these two key observations yield a reduction from the quantity $1-{\left|⟨{\psi }_0|{\psi }_1⟩\right|}^2$, which is BQP-hard to estimate [51], to Rank2QEA, thereby establishing the BQP-hardness of Rank2QEA under Karp reduction.

Unlike the previous approach based on the quantum (Tsallis) entropy difference [5, 40, 43], which essentially relies on the quantum Jensen-type divergences and is therefore quite restrictive in the choice of orders, our new approach to establishing BQP-hardness extends beyond Rank2TsallisQEA_q for arbitrary positive real orders and also applies to Rank2RényiQEA_$\alpha$. The first key observation admits a Rényi analogue, given by identity in Equation 4, which parallels Equation 2:

The second key observation involves inequalities relating Rényi or Tsallis binary entropies of different orders to the corresponding order-$2$ binary entropies. These inequalities, summarized in Tables 2 and 3, differ depending on the range of the orders under consideration.

Interestingly, the inequalities for $q$-Tsallis binary entropy in Table 3 require consideration of an additional case. This phenomenon is intuitively linked to the monotonicity of the normalized $q$-Tsallis binary entropy, ${\tilde{\mathrm{H}}}_q^{𝚃}(x)≔{\mathrm{H}}_q^{𝚃}(x)/{\mathrm{H}}_q^{𝚃}(1/2)$, implicitly studied in [19]. Numerical evidence suggests a transition point $q^{\ast }(x)\in [2,3]$ at which ${\tilde{\mathrm{H}}}_q^{𝚃}(x)$ changes monotonicity: it is monotonically decreasing on $q\in [0,q^{\ast }(x))$ and monotonically increasing on $q>q^{\ast }(x)$. This informally explains the additional row for $q\in (2,3]$ in Table 3.

Perhaps the most intriguing open problem is the following – what are the limitations of our new approach for establishing the computational hardness of estimating quantum entropies? In particular, can one prove the hardness of the Quantum $\alpha$-Rényi Entropy Approximation Problem (RényiQEA_$\alpha$) for any positive order $\alpha$? The well-known inequalities

can be almost straightforwardly generalized to relate the (quantum) min-entropy to the (quantum) $\alpha$-Rényi entropy for the order $\alpha >1$:⁸⁸8Let ${\{{\lambda }_k\}}_{k=1}^N$ denote the eigenvalues of an $n$-qubit quantum state $\rho$, where $N≔2^n$. The upper bound in Equation 5 follows from the fact that for all $\alpha >1$, $\ln \left({\sum }_{k=1}^N{\lambda }_k^{\alpha }\right)\ge \ln \left({\max }_k{\lambda }_k^{\alpha }\right)=\alpha \ln {\lambda }_{\max }$, since $\ln (x)$ is monotonically increasing for $x>0$. The argument is then completed by multiplying both sides by $1/(1-\alpha )$.

However, our new approach is effective only when the values of the quantum entropies and the promise gap are of comparable magnitude, e.g., when both are constant. Otherwise, reductions based on inequalities relating the quantum min entropy (in the order-$\mathrm{\infty }$ case) to the quantum Rényi entropy of other orders break down for sufficiently large $n$.

Beyond this technical limitation, a more fundamental complexity-theoretic barrier arises. Specifically, estimating the min-entropy ${\text{RényiEA}}_{\mathrm{\infty }}$ is coSBP-complete [73].⁹⁹9We note that the promise problem Circuit-Min-Ent-Gap defined in [73] is SBP-complete, but its promise conditions are the exact opposite of those in EA [29], which is why we consider the complement. Any reduction analogous to our approach for establishing Theorem 2 would imply that the Entropy Approximation Problem EA is coSBP-hard. Since EA is known to be NISZK-complete [28, 29], combining such a reduction with the coSBP-hardness of ${\text{RényiEA}}_{\mathrm{\infty }}$ would yield

where the inclusion $\text{NP}\subseteq \text{MA}\subseteq \text{SBP}$ is proven in [7]. The inclusion $\text{coNP}\subseteq \text{AM}$ in Equation 6 would collapse the polynomial-time hierarchy to its second level [8].

In addition to this main open problem concerning the computational hardness of estimating the quantum Rényi entropy, there are two further open questions:

1. (1)

   What is the computational hardness of estimating the quantum Rényi and Tsallis entropies of the order-$0$ in general?

2. (2)

   Can the inequalities in Table 2 be tightened? For instance, is it possible to prove that ${\left(\frac{{\mathrm{H}}_{\alpha }^{𝚁}(x)}{\ln (2)}\right)}^{2/\alpha }$ is monotonically non-decreasing in $\alpha$ for all fixed $x\in [0,1]$, as suggested by numerical evidence and as a generalization of Theorem 20?

We first review additional prior work on the computational complexity of decision problems related to entropies. A variant of Entropy Approximation (EA), specifically the sampler associated with distributions described by a degree-$3$ polynomial, was shown to be ${\mathrm{𝖲𝖹𝖪}}_{𝖫}$-complete [21]. More recently, another variant of EA, where the promises involve different entropies – namely deciding whether the max entropy (order $0$) is small or the smoothed $2$-Rényi entropy is large – was proven to be NISZK-complete in [46], playing a key role in batch verification of non-interactive statistical zero-knowledge. Furthermore, variants of Quantum Entropy Difference (QED), which are connected to estimating the von Neumann entropy of quantum states, have attracted attention in recent years: the case where the state-preparation circuits are shallow depth was studied in [25] and shown to be as hard as the Learning with Errors (LWE) problem, while the case where the state-preparation circuits act on $O(\log n)$ qubits was shown to be BQL-complete in [37].

In addition to results on entropy-related decision problems, while there is no direct connection to our approach, it is worth noting that conceptually similar inequalities relating different orders of information-theoretic quantities, similar to the Rényi binary entropies in Table 3 and the Tsallis binary entropies in Table 3, were established in [42] for the quantum ${\mathrm{\ell }}_{\alpha }$ distance ${\mathrm{T}}_{\alpha }({\rho }_0,{\rho }_1)$ defined via the Schatten norm ${\parallel A\parallel }_{\alpha }≔{\left(\mathrm{Tr}\left({|A|}^{\alpha }\right)\right)}^{1/\alpha }$. Specifically, such inequalities connect the trace distance ($\alpha =1$) to other orders where $\alpha >1$.

The $q$-logarithm function ${\ln }_q:{ℝ}^{+}\to ℝ$ for any real $q\ne 1$ is defined as ${\ln }_q(x)≔\frac{1-x^{1-q}}{q-1}$.

We then list several useful bounds for the Tsallis and Rényi binary entropies:

We also require the following folklore lower bound for the binary min-entropy, as presented, for example, in [20, Section 2]:

Next, we introduce different notions of quantum entropies for states:

We also present the promise problem for estimating quantum Tsallis entropies:

We start by defining a promise problem closely related to Fidelity-Pure-Pure, introduced in [51, Problem 1]:

The promise problem PureInfidelity, essentially the task of estimating the pure-state infidelity, $1-{|⟨{\psi }_0|{\psi }_1⟩|}^2$, to within constant precision, is BQP-hard:

The proof can be found in [41, Section 2.3] in the full version. It is worth mentioning that, subsequent to [51], constructions similar to Lemma 13 were used to establish hardness for closeness testing problems with respect to other closeness measures between pure states, such as the (squared) Hilbert–Schmidt distance [37, Lemma 4.23], the trace distance [66, Theorem 4.1] and [43, Lemma 2.17].

Following [33, Section 25], we define the generalized binomial coefficients, which is denoted by $\left(\genfrac{}{}{0pt}{}{a}{k}\right)$, for any real $\alpha$ and non-negative integer $k$:

Moreover, we make use of the following properties of the generalized binomial series:

To establish Theorem 18, we first note that the first equality in both Items (1) and (2) holds immediately, since ${\mathrm{S}}_q^{𝚃}(|\psi ⟩⟨\psi |)=0$ and ${\mathrm{S}}_{\alpha }^{𝚁}(|\psi ⟩⟨\psi |)=0$ for any pure state $|\psi ⟩$ and for all orders $q$ and $\alpha$. To demonstrate the second equality, we require the following lemma concerning the trace of powers of a rank-$2$ quantum state:

The proof of Lemma 19 proceeds by analyzing the eigenvalues of the matrix $|{\psi }_0⟩⟨{\psi }_0|+|{\psi }_1⟩⟨{\psi }_1|$, which yields $\mathrm{Tr}\left({(|{\psi }_0⟩⟨{\psi }_0|+|{\psi }_1⟩⟨{\psi }_1|)}^q\right)={(1-|⟨{\psi }_0|{\psi }_1⟩|)}^q+{(1+|⟨{\psi }_0|{\psi }_1⟩|)}^q$. Together with Proposition 14(1), this establishes Lemma 19. The complete proof can be found in the full version, specifically in [41, Section 3.1].

In this subsection, we present the proof of Theorem 16.

In this subsection, we demonstrate the proof of Theorem 17.