  The dynamical structure factor is one of the experimental quantities crucial
in scrutinizing the validity of the microscopic description of strongly
correlated systems. However, despite its long-standing importance, it is
exceedingly difficult in generic cases to numerically calculate it, ensuring
that the necessary approximations involved yield a correct result.
Acknowledging this practical difficulty, we discuss in what way results on the
hardness of classically tracking time evolution under local Hamiltonians are
precisely inherited by dynamical structure factors; and hence offer in the same
way the potential computational capabilities that dynamical quantum simulators
do: We argue that practically accessible variants of the dynamical structure
factors are BQP-hard for general local Hamiltonians. Complementing these
conceptual insights, we improve upon a novel, readily available, measurement
setup allowing for the determination of the dynamical structure factor in
different architectures, including arrays of ultra-cold atoms, trapped ions,
Rydberg atoms, and superconducting qubits. Our results suggest that quantum
simulations employing near-term noisy intermediate scale quantum devices should
allow for the observation of features of dynamical structure factors of
correlated quantum matter in the presence of experimental imperfections, for
larger system sizes than what is achievable by classical simulation.
