Dynamical structure factors of dynamical quantum simulators Baeza, Maria Laura Bermejo Vega, Juan Quantum simulation Dynamical structure factor Rydberg atoms Trapped ions 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 bounded-error quantum polynomial time (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. 2020-11-16T11:58:17Z 2020-11-16T11:58:17Z 2020 info:eu-repo/semantics/article Maria Laura Baez, Marcel Goihl, Jonas Haferkamp, Juani Bermejo-Vega, Marek Gluza, Jens Eisert Proceedings of the National Academy of Sciences Oct 2020, 117 (42) 26123-26134; [DOI: 10.1073/pnas.2006103117] http://hdl.handle.net/10481/64294 10.1073/pnas.2006103117 eng eu-repo/grantAgreement/EC/H2020/817482 http://creativecommons.org/licenses/by-nc-nd/3.0/es/ info:eu-repo/semantics/openAccess Atribución-NoComercial-SinDerivadas 3.0 España NATL ACAD SCIENCES