Yupan Liu

Kean Chen, Yupan Liu, Qisheng Wang

As often emerges in various basic quantum properties such as Rényi and Tsallis entropies, the trace of quantum state powers $\text{tr}(ρ^q)$ has attracted a lot of attention. The recent work of Liu and Wang (SODA 2025) showed that, even for (possibly) non-integer $q>1$, $\text{tr}(ρ^q)$ can be estimated to within additive error $ε$ using a dimension-independent (and also rank-independent) sample complexity of $\widetilde O(1/ε^{3+\frac2{q-1}})$, together with a lower bound of $Ω(1/ε)$. In addition, combining this result with subsequent work of Liu (STACS 2026) shows that the corresponding promise problem is ${\sf BQP}$-complete. In this paper, we significantly improve and extend the sample complexity bounds for this problem. Furthermore, we show that for $0<q<1$, the problem does not admit an efficient estimator unless ${\sf BQP}={\sf NIQSZK}$, which is considered highly unlikely. In particular, we have the following results. - For $q>2$, we settle the sample complexity with matching upper and lower bounds $\widetildeΘ(1/ε^2)$. - For $1<q<2$, we obtain an upper bound of $\widetilde O(1/ε^{\frac2{q-1}})$, with a lower bound of $Ω(1/ε^{\max\{\frac1{q-1},2\}})$ for dimension-independent (in fact, rank-independent) estimators. - For $0<q<1$, we obtain an upper bound of $O((d/ε)^{\frac2{q}})$, with a lower bound of $Ω((d/ε)^{\frac1{q}})$ for $d$-dimensional states (in fact, both bounds can be naturally refined to depend on the rank rather than the dimension). Accordingly, the corresponding promise problem is ${\sf NIQSZK}$-hard, which is in sharp contrast to the case of $q>1$. Technically, our upper bounds are obtained by (non-plug-in) quantum estimators based on weak Schur sampling, in sharp contrast to the prior approach based on quantum singular value transformation and samplizer.

Yupan Liu

We investigate the computational hardness of estimating the quantum $α$-Rényi entropy ${\rm S}^{\tt R}_α(ρ) = \frac{\ln {\rm Tr}(ρ^α)}{1-α}$ and the quantum $q$-Tsallis entropy ${\rm S}^{\tt T}_q(ρ) = \frac{1-{\rm Tr}(ρ^q)}{q-1}$, both of which converge 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 $ {\rm S}^ {\tt R}_α(ρ)$ or ${\rm S}^{\tt T}_q(ρ)$, is at least $τ_1$ or at most $τ_2$, where $τ_1 - τ_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 $α$ and $q$, and also for $α=\infty$, 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), as well as the one derived from O'Donnell and Wright (STOC 2016), our results imply: - For all real orders $α> 0$ or $α=\infty$, and for all real orders $0 < q \leq 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. These reductions differ substantially from previous approaches, and the inequalities are of independent interest.

Yupan Liu, Pei Wu

Stoquasticity, originating in sign-problem-free physical systems, gives rise to $\sf StoqMA$, introduced by Bravyi, Bessen, and Terhal (2006), a quantum-inspired intermediate class between $\sf MA$ and $\sf AM$. Unentanglement similarly gives rise to ${\sf QMA}(2)$, introduced by Kobayashi, Matsumoto, and Yamakami (CJTCS 2009), which generalizes $\sf QMA$ to two unentangled proofs and still has only the trivial $\sf NEXP$ upper bound. In this work, we initiate a systematic study of the power of unentanglement without destructive interference via ${\sf StoqMA}(2)$, the class of unentangled stoquastic Merlin-Arthur proof systems. Although $\sf StoqMA$ is semi-quantum and may collapse to $\sf MA$, ${\sf StoqMA}(2)$ turns out to be surprisingly powerful. We establish the following results: - ${\sf NP} \subseteq {\sf StoqMA}(2)$ with $\widetilde{O}(\sqrt{n})$-qubit proofs and completeness error $2^{-{\rm polylog}(n)}$. Conversely, ${\sf StoqMA}(2) \subseteq {\sf EXP}$ via the Sum-of-Squares algorithm of Barak, Kelner, and Steurer (STOC 2014); with our lower bound, our refined analysis yields the optimality of this algorithm under ETH. - ${\sf StoqMA}(2)_1 \subseteq {\sf PSPACE}$, and the containment holds with completeness error $2^{-2^{{\rm poly}(n)}}$. - ${\sf PreciseStoqMA}(2)$, a variant of ${\sf StoqMA}(2)$ with exponentially small promise gap, cannot achieve perfect completeness unless ${\sf EXP}={\sf NEXP}$. In contrast, ${\sf PreciseStoqMA}$ achieves perfect completeness, since ${\sf PSPACE} \subseteq {\sf PreciseStoqMA}_1$. - When the completeness error is negligible, ${\sf StoqMA}(k) = {\sf StoqMA}(2)$ for $k\geq 2$. Our lower bounds are obtained by stoquastizing the short-proof ${\sf QMA}(2)$ protocols via distribution testing techniques. Our upper bounds for the nearly perfect completeness case are proved via our new rectangular closure testing framework.