Walking the Hypercube: Unbiased Quantum Partition Functions Without the Matrix

Computing the partition function $\mathcal{Z} = \mathrm{tr}(e^{-\beta H})$ of a quantum spin Hamiltonian $H$ on $n$ sites is a fundamental problem in statistical physics and quantum chemistry. However exact evaluation requires $O(8^n)$ time and $O(4^n)$ memory making it intractable for all but the smallest systems. We propose an unbiased stochastic estimator of $\mathcal{Z}$, and more generally of $\mathrm{tr}(f(H))$ for any function $f$ admitting a convergent power series over exponentially large, implicitly defined operators using only local random walks, avoiding both matrix materialization and matrix-vector products. Our approach combines Graph Random Features with the Hutchinson's stochastic trace estimator, and exploits the algebraic structure of quantum spin Hamiltonians to reduce the per-step computational cost to $O(n + d)$, where $d$ is the mean degree of the spin coupling graph, independent of the Hilbert space dimension $N = 2^n$. We validate the estimator empirically against exact matrix exponentiation for small system sizes, and demonstrate its applicability to system sizes where exact methods are infeasible.