We investigate the computational complexity of estimating the operator norm distance ${\rm T}_{\infty}(ρ_0,ρ_1)$, defined via the operator norm $\|A\|_{\infty} = σ_{\max}(A)$, given ${\rm poly}(n)$-size state-preparation circuits of $n$-qubit quantum states $ρ_0$ and $ρ_1$. We provide efficient quantum estimators for the operator norm distance whose complexity is independent of the rank (and thus the dimension) of the states: 1. When one state is pure, we establish an optimal quantum estimator using $Θ(1/ε)$ queries to the state-preparation circuits. Consequently, for constant additive error, say $ε=1/5$, our estimator runs in ${\rm poly}(n)$ time. Since the operator norm distance ${\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)$ is exactly half of the trace distance ${\rm T}(|ψ\rangle\!\langleψ|,ρ)$, our result also gives rank-independent query complexity for estimating both quantities, whereas the approaches due to van Apeldoorn, Cornelissen, Gily{é}n, and Nannicini (SODA 2023) and Wang and Zhang (TIT 2024) have query complexity scaling at least linearly with ${\rm rank}(ρ)$, which can be $\exp(n)$ in general. 2. For general quantum states, we also provide a quantum estimator using $\widetilde{O}(1/ε^{3/2})$ queries to the state-preparation circuits, which shows that the corresponding promise problem is ${\sf BQP}$-complete and improves the ${\sf QMA}$ upper bound sketched by Liu and Wang (ESA 2025). Together with an $Ω(1/ε)$ quantum query complexity lower bound, this leaves only square-root room for improvement. The key intuition behind our estimators is that, when one state is pure, the pure state $|ψ\rangle$ has overlap at least $1/2$ with the top unit eigenvector of $|ψ\rangle\!\langleψ|-ρ$, reflecting a structural feature specific to the operator norm distance.

The complexity class Quantum Statistical Zero-Knowledge (QSZK), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound QIP(2) ∩ co-QIP(2), which was simplified following the inclusion QIP(2) ⊆ PSPACE established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, QIP(2) denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and co-QIP(2) denotes the complement of QIP(2). We slightly improve this upper bound to QIP(2) ∩ co-QIP(2) with a quantum linear-space honest prover. Specifically, the honest prover uses space linear in the size of the transcript of the original QSZK proof system. A similar improvement also applies to the upper bound for the non-interactive variant NIQSZK. Our main techniques are algorithmic versions of the Holevo-Helstrom measurement and the Uhlmann transform, both implementable in quantum linear space, implying polynomial-time complexity in the state dimension, using the recent space-efficient quantum singular value transformation of Le Gall, Liu, and Wang (CC, to appear).

We investigate the computational hardness of estimating the quantum α-Rényi entropy S^𝚁_α(ρ) = (ln Tr(ρ^α))/(1-α) and the quantum q-Tsallis entropy S^𝚃_q(ρ) = (1-Tr(ρ^q))/(q-1), both converging to the von Neumann entropy as the order approaches 1. The promise problems Quantum α-Rényi Entropy Approximation (RényiQEA_α) and Quantum q-Tsallis Entropy Approximation (TsallisQEA_q) ask whether S^𝚁_α(ρ) or S^𝚃_q(ρ), respectively, is at least τ_Y or at most τ_N, where τ_Y - τ_N 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 orders, the rank-2 variants Rank2RényiQEA_α 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), our results imply: - For all real order α > 0 and 0 < q ≤ 1, LowRankRényiQEA_α and LowRankTsallisQEA_q are BQP-complete, where both are restricted versions of RényiQEA_α and TsallisQEA_q with ρ 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 α-Rényi or q-Tsallis binary entropies of different orders, where the reductions differ substantially from previous approaches, and the inequalities are also of independent interest.

We investigate the computational complexity of estimating the trace of quantum state powers tr(ρ<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">^q</i>) for an <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> qubit mixed quantum state ρ, given its state-preparation circuit of size poly <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(n)</i>. This quantity is closely related to and often interchangeable with the Tsallis entropy S<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">_q</i>(ρ) = 1—tr(ρ<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">^q</i>)/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i>—1, where <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i> = 1 corresponds to the von Neumann entropy. For any non-integer <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i>≥ 1 + Ω(1), we provide a quantum estimator for S<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i>(ρ) with time complexity poly <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(n)</i>, exponentially improving the prior best results of exp<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(n)</i> due to Acharya, Issa, Shende, and Wagner (ISIT 2019), Wang, Guan, Liu, Zhang, and Ying (TIT 2024)| Wang, Zhang, and Li (TIT 2024), and Wang and Zhang (TIT 2025). Our speedup is achieved by introducing efficiently computable <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">uniform approximations</i> of positive power functions into quantum singular value transformation. Our quantum algorithm reveals a sharp phase transition between the case of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i> = 1 and constant <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i> > 1 in the computational complexity of the Quantum <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i>-Tsallis Entropy Difference Problem (TsallisQED <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">_q</i> ), particularly deciding whether the difference S<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">_q</i>(ρ0)−S<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">_q</i> (ρ1) is at least 0.001 or at most −0.001: • For any 1 + Ω (1) ≤ <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i> ≤ 2, TsallisQED <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">_q</i> is BQP-complete, which implies that Purity Estimation is also BQP-complete. • For any 1≤<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i>≤1+1/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> — 1, TsallisQED q is QSZK-hard, leading to hardness of approximating the von Neumann entropy because S<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">_q</i>(ρ) ≤ S (ρ), as long as BQPQSZK. The hardness results are derived from reductions based on new inequalities for the quantum <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i>-Jensen–(Shannon–)Tsallis divergence with 1 ≤ <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i> ≤ 2, which are of independent interest.

We introduce two models of space-bounded quantum interactive proof systems, QIPL and QIP_{U}L. The QIP_{U}L model, a space-bounded variant of quantum interactive proofs (QIP) introduced by Watrous (CC 2003) and Kitaev and Watrous (STOC 2000), restricts verifier actions to unitary circuits. In contrast, QIPL allows logarithmically many pinching intermediate measurements per verifier action, making it the weakest model that encompasses the classical model of Condon and Ladner (JCSS 1995). We characterize the computational power of QIPL and QIP_{U}L. When the message number m is polynomially bounded, QIP_{U}L ⊊ QIPL unless P = NP: - QIPL^HC, a subclass of QIPL defined by a high-concentration condition on yes instances, exactly characterizes NP. - QIP_{U}L is contained in P and contains SAC¹ ∪ BQL, where SAC¹ denotes problems solvable by classical logarithmic-depth, semi-unbounded fan-in circuits. However, this distinction vanishes when m is constant. Our results further indicate that (pinching) intermediate measurements uniquely impact space-bounded quantum interactive proofs, unlike in space-bounded quantum computation, where BQL = BQ_{U}L. We also introduce space-bounded unitary quantum statistical zero-knowledge (QSZK_{U}L), a specific form of QIP_{U}L proof systems with statistical zero-knowledge against any verifier. This class is a space-bounded variant of quantum statistical zero-knowledge (QSZK) defined by Watrous (SICOMP 2009). We prove that QSZK_{U}L = BQL, implying that the statistical zero-knowledge property negates the computational advantage typically gained from the interaction.

We investigate the computational complexity of estimating the trace of quantum state powers tr(ρq ) for an n-qubit mixed quantum state ρ, given its state-preparation circuit of size poly(n ). This quantity is closely related to and often interchangeable with the Tsallis entropywhere q = 1 corresponds to the von Neumann entropy. For any non-integer q ≥ 1 + Ω(1), we provide a quantum estimator for Sq (ρ ) with time complexity poly(n), exponentially improving the prior best results of exp(n ) due to Acharya, Issa, Shende, and Wagner (ISIT 2019), Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Wang and Zhang (ESA 2024). Our speedup is achieved by introducing efficiently computable uniform approximations of positive power functions into quantum singular value transformation.

Abstract The complexity class Quantum Statistical Zero-Knowledge captures computational difficulties of the time-bounded quantum state testing problem with respect to the trace distance, deciding whether $$\textrm{T}(\rho_0,\rho_1)$$ T ( ρ 0 , ρ 1 ) is at least $$\alpha$$ α or at most $$\beta$$ β , known as the Quantum State Distinguishability Problem (QSDP) introduced by Watrous (FOCS 2002). However, $$\textrm{QSDP}[\alpha,\beta]$$ QSDP [ α , β ] is in only within the constant polarizing regime, where $$\alpha \, \textrm{and} \, \beta$$ α and β are constants satisfying $$\alpha^2 > \beta$$ α 2 > β (rather than $$\alpha > \beta$$ α > β ), similar to its classical counterpart shown by Sahai and Vadhan (JACM 2003) due to the polarization lemma (error reduction for SDP). Recently, Berman, Degwekar, Rothblum, and Vasudevan (TCC 2019) extended the containment of SDP beyond the polarizing regime via the time-bounded distribution testing problems with respect to the triangular discrimination and the Jensen-Shannon divergence. Our work introduces proper quantum analogs for these problems by defining quantum counterparts for triangular discrimination. We investigate whether the quantum analogs behave similarly to their classical counterparts and examine the limitations of existing approaches to polarization regarding quantum distances. These new -complete problems improve containments of QSDP beyond the polarizing regime and establish a simple -hardness for the quantum entropy difference problem (QEDP) defined by Ben-Aroya, Schwartz, and Ta-Shma (ToC 2010). Furthermore, we prove that QSDP with some exponentially small errors is in , while the same problem without error is in .