  Recent experiments demonstrated quantum computational advantage in random
circuit sampling and Gaussian boson sampling. However, it is unclear whether
these experiments can lead to practical applications even after considerable
research effort. On the other hand, simulating the quantum coherent dynamics of
interacting spins has been considered as a potential first useful application
of quantum computers, providing a possible quantum advantage. Despite evidence
that simulating the dynamics of hundreds of interacting spins is challenging
for classical computers, concrete proof is yet to emerge. We address this
problem by proving that sampling from the output distribution generated by a
wide class of quantum spin Hamiltonians is a hard problem for classical
computers. Our proof is based on the Taylor series of the output probability,
which contains the permanent of a matrix as a coefficient when bipartite spin
interactions are considered. We devise a classical algorithm that extracts the
coefficient using an oracle estimating the output probability. Since
calculating the permanent is #P-hard, such an oracle does not exist unless the
polynomial hierarchy collapses. With an anticoncentration conjecture, the
hardness of the sampling task is also proven. Based on our proof, we estimate
that an instance involving about 200 spins will be challenging for classical
devices but feasible for intermediate-scale quantum computers with
fault-tolerant qubits.
