DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians

Zhengfeng Ji, Tongyang Li, Changpeng Shao +2

We study the computational complexity of estimating the normalized trace $2^{-n}\mathrm{Tr}[f(A)]$ for a log-local Hamiltonian $A$ acting on $n$ qubits. This problem arises natural…