We consider simulating an $n$-qubit Hamiltonian with nearest-neighbor interactions evolving for time $t$ on a quantum computer. We show that this simulation has gate complexity $(nt)^{1+o(1)}$ using product formulas, a straightforward approach that …
With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, …