Sublinear quantum algorithms forestimating von Neumann entropy

Tom Gur¹, Min-Hsiu Hsieh^2*, Sathyawageeswar Subramanian¹

¹University of Warwick, UK
²Hon Hai Research Institute, Taiwan

* Presenter:Min-Hsiu Hsieh, email:minhsiuh@gmail.com

Entropy is a fundamental property of both classical and quantum systems, spanning myriad theoretical and practical applications in physics and computer science. We study the problem of obtaining estimates to within a multiplicative factor $\gamma>1$ of the Shannon entropy of probability distributions and the von Neumann entropy of mixed quantum states. Our main results are:
\begin{itemize}
\item an $\widetilde{\O}\left( n^{\nicefrac{1}{2\gamma^2}}\right)$-query quantum algorithm that outputs a $\gamma$-multiplicative approximation of the Shannon entropy $H(\pbold)$ of a classical probability distribution $\pbold = (p_1,\ldots,p_n)$;

\item an $\widetilde{\O}\left( n^{\nicefrac12+\nicefrac{1}{2\gamma^2}}\right)$-query quantum algorithm that outputs a $\gamma$-multiplicative approximation of the von Neumann entropy $S(\rho)$ of a density matrix $\rho\in\C^{n\times n}$.
\end{itemize}
In addition, we provide $\Omega\left(n^{\nicefrac{1}{3\gamma^2}}\right)$ lower bounds on the query complexity of $\gamma$-multiplicative estimation of Shannon and von Neumann entropies. We work with the quantum purified query access model, which can handle both classical probability distributions and mixed quantum states, and is the most general input model considered in the literature.

Keywords: Quantum Algorithm, Entropy Estimation, Query Complexity