  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:
  $\quad\bullet$ an $\widetilde{\mathcal{O}}\left(
n^{\frac{1+\eta}{2\gamma^2}}\right)$-query quantum algorithm that outputs a
$\gamma$-multiplicative approximation of the Shannon entropy $H(\mathbf{p})$ of
a classical probability distribution $\mathbf{p} = (p_1,\ldots,p_n)$;
  $\quad\bullet$ an $\widetilde{\mathcal{O}}\left(
n^{\frac12+\frac{1+\eta}{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\mathbb{C}^{n\times n}$.
  In both cases, the input is assumed to have entropy bounded away from zero by
a quantity determined by the parameter $\eta>0$, since, as we prove, no
polynomial query algorithm can multiplicatively approximate the entropy of
distributions with arbitrarily low entropy. In addition, we provide
$\Omega\left(n^{\frac{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.
