Title: The Quantum Complexity of Computing Schatten $p$-norms,
Abstract: We consider the quantum complexity of computing Schatten $p$-norms and
related quantities, and find that the problem of estimating these quantities is
closely related to the one clean qubit model of computation. We show that the
problem of approximating $\text{Tr}\, (|A|^p)$ for a log-local $n$-qubit
Hamiltonian $A$ and $p=\text{poly}(n)$, up to a suitable level of accuracy, is
contained in DQC1; and that approximating this quantity up to a somewhat higher
level of accuracy is DQC1-hard. In some cases the level of accuracy achieved by
the quantum algorithm is substantially better than a natural classical
algorithm for the problem. The same problem can be solved for arbitrary sparse
matrices in BQP. One application of the algorithm is the approximate
computation of the energy of a graph.