Trace Estimation of Quantum State Powers: Sample Complexity and Computational Hardness
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912999183220736 |
|---|---|
| author | Chen, Kean Liu, Yupan Wang, Qisheng |
| author_facet | Chen, Kean Liu, Yupan Wang, Qisheng |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_09563 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Trace Estimation of Quantum State Powers: Sample Complexity and Computational Hardness Chen, Kean Liu, Yupan Wang, Qisheng Quantum Physics Information Theory 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. |
| title | Trace Estimation of Quantum State Powers: Sample Complexity and Computational Hardness |
| topic | Quantum Physics Information Theory |
| url | https://arxiv.org/abs/2505.09563 |