Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2502.07571 · Physical Review A

Estimation of nonlinear physical quantities by measuring ancillas

Nhat A. Nghiem, Tzu-Chieh Wei

Published Nov 17, 2025• 0 citations
arXivHTMLPDF

Abstract

In this article, we present quantum algorithms for estimating von Neumann entropy and Renyi entropy, which are crucial physical and information-theoretical properties of a given quantum state $\ensuremath{\rho}$. Although there have been existing works that have achieved the same goal, some prior developments assume the unitary that prepares the purification to the target state $\ensuremath{\rho}$. Here, we consider an alternative setting where only copies of $\ensuremath{\rho}$ are given and we construct a quantum algorithm that estimates the desired entropy. Our framework completes the given task by measuring a small number of ancilla qubits without directly measuring the system, and it achieves significant improvement over prior relevant developments. For example, for the Renyi entropy of the order of nonintegral $\ensuremath{\alpha}$, our method achieves almost a power-of-2 improvement in sample complexity with respect to the rank of the given state and almost a power-of-2 improvement in error tolerance compared with the work by Wang et al. [Y. Wang, B. Zhao, and X. Wang, Phys. Rev. Appl. 19, 044041 (2023)].

DOI
10.1103/q6t8-yrjb

Related papers

Time-Efficient Quantum Entropy Estimator via Samplizer

Qisheng Wang, Zhicheng Zhang

Entropy is a measure of the randomness of a system. Estimating the entropy of a quantum state is a basic problem in quantum information. In this paper, we introduce a time-efficient quantum approach to estimating the von Neumann entropy $S(ρ)$ and Rényi entropy $S_α(ρ)$ of an $N$-dimensional quantum state $ρ$, given access to independent samples of $ρ$. Specifically, we provide the following: 1. A quantum estimator for $S(ρ)$ with time complexity $\tilde O(N^2)$, improving the prior best time complexity $\tilde O(N^6)$ by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). 2. A quantum estimator for $S_α(ρ)$ with time complexity $\tilde O(N^{4/α-2})$ for $0<α<1$ and $\tilde O(N^{4-2/α})$ for $α>1$, improving the prior best time complexity $\tilde O(N^{6/α})$ for $0<α<1$ and $\tilde O(N^6)$ for $α>1$ by Acharya, Issa, Shende, and Wagner (2020), though at a cost of a slightly larger sample complexity. Moreover, these estimators are naturally extensible to the low-rank case. We also provide a sample lower bound for estimating $S_α(ρ)$. Technically, our method is quite different from the previous ones that are based on weak Schur sampling and Young diagrams. At the heart of our construction, is a novel tool called samplizer, which can "samplize" a quantum query algorithm to a quantum algorithm with similar behavior using only samples of quantum states; this suggests a unified framework for estimating quantum entropies. Specifically, when a quantum oracle $U$ block-encodes a mixed quantum state $ρ$, any quantum query algorithm using $Q$ queries to $U$ can be samplized to a $δ$-close (in the diamond norm) quantum algorithm using $\tildeΘ(Q^2/δ)$ samples of $ρ$. Moreover, this samplization is proven to be optimal, up to a polylogarithmic factor.

arXiv:2401.09947•Leibniz international proceedings in informatics•Jan 1, 2024•3 citations

Quantum Algorithms for Estimating Quantum Entropies

Youle Wang, Benchi Zhao, Xin Wang

The von Neumann and quantum R\'enyi entropies characterize fundamental properties of quantum systems and lead to many theoretical and practical applications. Quantum algorithms using a purified quantum query model can speed up quantum entropy estimation, while little is known about the complexity of using identical copies of the quantum state. This paper presents quantum entropy estimation algorithms with a cost of copies scaling polynomially in the rank of the state. In contrast to current methods that depend on the dimension of the system, our methods could provide exponential resource savings in the scenario of low-rank states. Furthermore, we show how to construct quantum circuits using primitive single-qubit or two-qubit gates efficiently and thus provide practical methods for estimating quantum entropies of quantum systems. We also conduct simulation experiments to show the effectiveness and noise robustness of our algorithms.

arXiv:2203.02386•Physical Review Applied•Apr 14, 2023•28 citations

Quantum algorithm for estimating α -Renyi entropies of quantum states

Sathyawageeswar Subramanian, Min-Hsiu Hsieh

We describe a quantum algorithm to estimate the $\ensuremath{\alpha}$-Renyi entropy of an unknown density matrix $\ensuremath{\rho}\ensuremath{\in}{\mathbb{C}}^{d\ifmmode\times\else\texttimes\fi{}d}$ for $\ensuremath{\alpha}\ensuremath{\ne}1$ by combining the recent technique of quantum singular value transformations with the method of estimating normalized traces in the one clean qubit model. We consider an oracular input model where the input state is prepared via a quantum oracle that outputs a purified version of the state, assumed to be nonsingular. Our method outputs an estimate of the $\ensuremath{\alpha}$-Renyi entropy to additive precision $\ensuremath{\epsilon}$, using an expected total number $O(\frac{1}{{(x\ensuremath{\epsilon})}^{2}})$ of independent applications of a quantum circuit which coherently queries the input unitary $O(\frac{1}{\ensuremath{\delta}}log\frac{d}{\ensuremath{\epsilon}})$ times, in each case measuring a single output qubit. Here $\ensuremath{\delta}$ is a lower cutoff on the smallest eigenvalue of $\ensuremath{\rho}$ and $x=\frac{1}{d}\mathrm{Tr}({\ensuremath{\rho}}^{\ensuremath{\alpha}})$. The expected number of measurements made in this method can be compared to results in the sample complexity model that generally require $\mathrm{\ensuremath{\Theta}}(\frac{{d}^{2}}{{\ensuremath{\epsilon}}^{2}})$ samples. Furthermore, we also show that multiplicative approximations can be obtained by iteratively using additive approximations, with an overhead logarithmic in the dimension $d$.

arXiv:1908.05251•Physical Review A•Aug 24, 2021•46 citations

Computational hardness of estimating quantum entropies via binary entropy bounds

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.

quant-pharXiv:2601.03734•Leibniz international proceedings in informatics•Jan 8, 2026•0 citations

Measuring Quantum Entropy

Jayadev Acharya, Ibrahim Issa, Nirmal V. Shende +1 more

The entropy of a quantum system is a measure of its randomness and is useful in quantifying entanglement. We study the problem of measuring the von Neumann and Rényi entropies of an unknown mixed quantum state given access to independent copies of the state. For Rényi entropy of integral order exceeding one, we determine the order-optimal copy complexity and show that it is strictly lower than the number of copies required to learn the underlying state. The main technical innovation is a concentration result for certain polynomials that arise in the Kerov algebra of Young diagrams, which is proven using the cycle structure of compositions of certain types of permutations. For von Neumann entropy and Rényi entropy of non-integral orders, we provide upper and lower bounds on the sample complexity of the Empirical Young Diagram (EYD) algorithm, which is the analogue of the empirical plug-in estimator in classical estimation.

arXiv:1711.00814•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•22 citations

Time-Efficient Quantum Entropy Estimator via Samplizer

Qisheng Wang, Zhicheng Zhang

Entropy is a measure of the randomness of a system. Estimating the entropy of a quantum state is a basic problem in quantum information. In this paper, we introduce a time-efficient quantum approach to estimating the von Neumann entropyS(ρ) and Rényi entropySα(ρ) of anN-dimensional quantum state ρ, given access to independent samples of ρ. Specifically, we provide the following quantum estimators. • A quantum estimator forS(ρ) with time complexity Õ (N2),1improving the prior best time complexity Õ(N6) by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). • A quantum estimator forSα(ρ) with time complexity Õ (N4/α−2) for 0N4−2/α) for α > 1, improving the prior best time complexity Õ(N6/α) for 0N6) for α > 1 by Acharya, Issa, Shende, and Wagner (2020), though at a cost of a slightly larger sample complexity. Moreover, these estimators are naturally extensible to the low-rank case. We also provide a sample lower bound Ω(max{N/ε,N1/α−1/ε1/α}) for estimatingSα(ρ). Technically, our method is quite different from the previous ones that are based on weak Schur sampling and Young diagrams. At the heart of our construction, is a novel tool calledsamplizer, which can “samplize” a quantum query algorithm to a quantum algorithm with similar behavior using only samples of quantum states; this suggests a new framework for estimating quantum entropies. Specifically, when a quantum oracleUblockencodes a mixed quantum state ρ, any quantum query algorithm usingQqueries toUcan be samplized to a δ-close (in the diamond norm) quantum algorithm using Θ(Q2/δ) samples of ρ. Moreover, this samplization is proven to be optimal, up to a polylogarithmic factor.

IEEE Transactions on Information Theory•Jun 9, 2025•6 citations
In this article, we present quantum algorithms for estimating von Neumann entropy and Renyi entropy, which are crucial physical and information-theoretical properties of a given quantum state \ensuremathρ\ensuremath{\rho}\ensuremathρ. Although there have been existing works that have achieved the same goal, some prior developments assume the unitary that prepares the purification to the target state \ensuremathρ\ensuremath{\rho}\ensuremathρ. Here, we consider an alternative setting where only copies of \ensuremathρ\ensuremath{\rho}\ensuremathρ are given and we construct a quantum algorithm that estimates the desired entropy. Our framework completes the given task by measuring a small number of ancilla qubits without directly measuring the system, and it achieves significant improvement over prior relevant developments. For example, for the Renyi entropy of the order of nonintegral \ensuremathα\ensuremath{\alpha}\ensuremathα, our method achieves almost a power-of-2 improvement in sample complexity with respect to the rank of the given state and almost a power-of-2 improvement in error tolerance compared with the work by Wang et al. [Y. Wang, B. Zhao, and X. Wang, Phys. Rev. Appl. 19, 044041 (2023)].
Entropy is a measure of the randomness of a system. Estimating the entropy of a quantum state is a basic problem in quantum information. In this paper, we introduce a time-efficient quantum approach to estimating the von Neumann entropy S(ρ)S(ρ)S(ρ) and Rényi entropy Sα(ρ)S_α(ρ)Sα​(ρ) of an NNN-dimensional quantum state ρρρ, given access to independent samples of ρρρ. Specifically, we provide the following: 1. A quantum estimator for S(ρ)S(ρ)S(ρ) with time complexity O~(N2)\tilde O(N^2)O~(N2), improving the prior best time complexity O~(N6)\tilde O(N^6)O~(N6) by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). 2. A quantum estimator for Sα(ρ)S_α(ρ)Sα​(ρ) with time complexity O~(N4/α−2)\tilde O(N^{4/α-2})O~(N4/α−2) for 0<α<10<α<10<α<1 and O~(N4−2/α)\tilde O(N^{4-2/α})O~(N4−2/α) for α>1α>1α>1, improving the prior best time complexity O~(N6/α)\tilde O(N^{6/α})O~(N6/α) for 0<α<10<α<10<α<1 and O~(N6)\tilde O(N^6)O~(N6) for α>1α>1α>1 by Acharya, Issa, Shende, and Wagner (2020), though at a cost of a slightly larger sample complexity. Moreover, these estimators are naturally extensible to the low-rank case. We also provide a sample lower bound for estimating Sα(ρ)S_α(ρ)Sα​(ρ). Technically, our method is quite different from the previous ones that are based on weak Schur sampling and Young diagrams. At the heart of our construction, is a novel tool called samplizer, which can "samplize" a quantum query algorithm to a quantum algorithm with similar behavior using only samples of quantum states; this suggests a unified framework for estimating quantum entropies. Specifically, when a quantum oracle UUU block-encodes a mixed quantum state ρρρ, any quantum query algorithm using QQQ queries to UUU can be samplized to a δδδ-close (in the diamond norm) quantum algorithm using Θ~(Q2/δ)\tildeΘ(Q^2/δ)Θ~(Q2/δ) samples of ρρρ. Moreover, this samplization is proven to be optimal, up to a polylogarithmic factor.
The von Neumann and quantum R\'enyi entropies characterize fundamental properties of quantum systems and lead to many theoretical and practical applications. Quantum algorithms using a purified quantum query model can speed up quantum entropy estimation, while little is known about the complexity of using identical copies of the quantum state. This paper presents quantum entropy estimation algorithms with a cost of copies scaling polynomially in the rank of the state. In contrast to current methods that depend on the dimension of the system, our methods could provide exponential resource savings in the scenario of low-rank states. Furthermore, we show how to construct quantum circuits using primitive single-qubit or two-qubit gates efficiently and thus provide practical methods for estimating quantum entropies of quantum systems. We also conduct simulation experiments to show the effectiveness and noise robustness of our algorithms.
We describe a quantum algorithm to estimate the $\ensuremath{\alpha}$-Renyi entropy of an unknown density matrix $\ensuremath{\rho}\ensuremath{\in}{\mathbb{C}}^{d\ifmmode\times\else\texttimes\fi{}d}$ for $\ensuremath{\alpha}\ensuremath{\ne}1$ by combining the recent technique of quantum singular value transformations with the method of estimating normalized traces in the one clean qubit model. We consider an oracular input model where the input state is prepared via a quantum oracle that outputs a purified version of the state, assumed to be nonsingular. Our method outputs an estimate of the $\ensuremath{\alpha}$-Renyi entropy to additive precision $\ensuremath{\epsilon}$, using an expected total number $O(\frac{1}{{(x\ensuremath{\epsilon})}^{2}})$ of independent applications of a quantum circuit which coherently queries the input unitary $O(\frac{1}{\ensuremath{\delta}}log\frac{d}{\ensuremath{\epsilon}})$ times, in each case measuring a single output qubit. Here $\ensuremath{\delta}$ is a lower cutoff on the smallest eigenvalue of $\ensuremath{\rho}$ and $x=\frac{1}{d}\mathrm{Tr}({\ensuremath{\rho}}^{\ensuremath{\alpha}})$. The expected number of measurements made in this method can be compared to results in the sample complexity model that generally require $\mathrm{\ensuremath{\Theta}}(\frac{{d}^{2}}{{\ensuremath{\epsilon}}^{2}})$ samples. Furthermore, we also show that multiplicative approximations can be obtained by iteratively using additive approximations, with an overhead logarithmic in the dimension ddd.
We investigate the computational hardness of estimating the quantum ααα-Rényi entropy SαR(ρ)=ln⁡Tr(ρα)1−α{\rm S}^{\tt R}_α(ρ) = \frac{\ln {\rm Tr}(ρ^α)}{1-α}SαR​(ρ)=1−αlnTr(ρα)​ and the quantum qqq-Tsallis entropy SqT(ρ)=1−Tr(ρq)q−1{\rm S}^{\tt T}_q(ρ) = \frac{1-{\rm Tr}(ρ^q)}{q-1}SqT​(ρ)=q−11−Tr(ρq)​, both of which converge to the von Neumann entropy as the order approaches 111. The promise problems Quantum ααα-Rényi Entropy Approximation (RényiQEAα_αα​) and Quantum qqq-Tsallis Entropy Approximation (TsallisQEAq_qq​) ask whether $ {\rm S}^ {\tt R}_α(ρ)$ or SqT(ρ){\rm S}^{\tt T}_q(ρ)SqT​(ρ), is at least τ1τ_1τ1​ or at most τ2τ_2τ2​, where τ1−τ2τ_1 - τ_2τ1​−τ2​ is typically a positive constant. Previous hardness results cover only the von Neumann entropy (order 111) and some cases of the quantum qqq-Tsallis entropy, while existing approaches do not readily extend to other orders. We establish that for all positive real ααα and qqq, and also for α=∞α=\inftyα=∞, the rank-222 variants Rank2RényiQEAα_αα​ and Rank2TsallisQEAq_qq​ 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α> 0α>0 or α=∞α=\inftyα=∞, and for all real orders 0<q≤10 < q \leq 10<q≤1, LowRankRényiQEAα_αα​ and LowRankTsallisQEAq_qq​ are BQP-complete, where both are restricted versions of RényiQEAα_αα​ and TsallisQEAq_qq​ with ρρρ of polynomial rank. - For all real order q>1q>1q>1, TsallisQEAq_qq​ is BQP-complete. Our hardness results stem from reductions based on new inequalities relating the ααα-Rényi or qqq-Tsallis binary entropies of different orders. These reductions differ substantially from previous approaches, and the inequalities are of independent interest.
The entropy of a quantum system is a measure of its randomness and is useful in quantifying entanglement. We study the problem of measuring the von Neumann and Rényi entropies of an unknown mixed quantum state given access to independent copies of the state. For Rényi entropy of integral order exceeding one, we determine the order-optimal copy complexity and show that it is strictly lower than the number of copies required to learn the underlying state. The main technical innovation is a concentration result for certain polynomials that arise in the Kerov algebra of Young diagrams, which is proven using the cycle structure of compositions of certain types of permutations. For von Neumann entropy and Rényi entropy of non-integral orders, we provide upper and lower bounds on the sample complexity of the Empirical Young Diagram (EYD) algorithm, which is the analogue of the empirical plug-in estimator in classical estimation.
Entropy is a measure of the randomness of a system. Estimating the entropy of a quantum state is a basic problem in quantum information. In this paper, we introduce a time-efficient quantum approach to estimating the von Neumann entropyS(ρ) and Rényi entropySα(ρ) of anN-dimensional quantum state ρ, given access to independent samples of ρ. Specifically, we provide the following quantum estimators. • A quantum estimator forS(ρ) with time complexity Õ (N2),1improving the prior best time complexity Õ(N6) by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). • A quantum estimator forSα(ρ) with time complexity Õ (N4/α−2) for 0N4−2/α) for α > 1, improving the prior best time complexity Õ(N6/α) for 0N6) for α > 1 by Acharya, Issa, Shende, and Wagner (2020), though at a cost of a slightly larger sample complexity. Moreover, these estimators are naturally extensible to the low-rank case. We also provide a sample lower bound Ω(max{N/ε,N1/α−1/ε1/α}) for estimatingSα(ρ). Technically, our method is quite different from the previous ones that are based on weak Schur sampling and Young diagrams. At the heart of our construction, is a novel tool calledsamplizer, which can “samplize” a quantum query algorithm to a quantum algorithm with similar behavior using only samples of quantum states; this suggests a new framework for estimating quantum entropies. Specifically, when a quantum oracleUblockencodes a mixed quantum state ρ, any quantum query algorithm usingQqueries toUcan be samplized to a δ-close (in the diamond norm) quantum algorithm using Θ(Q2/δ) samples of ρ. Moreover, this samplization is proven to be optimal, up to a polylogarithmic factor.