On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation

Hamiltonian simulation is one of the most important problems in the field of quantum computing. There have been extended efforts on designing algorithms for faster simulation, and the evolution time $T$ for the simulation greatly affect algorithm runtime as expected. While there are some specific types of Hamiltonians that can be fast-forwarded, i.e., simulated within time $o(T)$, for some large classes of Hamiltonians (e.g., all local/sparse Hamiltonians), existing simulation algorithms require running time at least linear in the evolution time $T$. On the other hand, while there exist lower bounds of $Omega(T)$  emph{circuit size} for some large classes of Hamiltonian,  these lower bounds do not rule out the possibilities of Hamiltonian simulation with large but ``low-depth'' circuits by running things in parallel. As a result, physical systems with system size scaling with $T$ can potentially do a fast-forwarding simulation. Therefore, it is intriguing whether we can achieve fast Hamiltonian simulation with the power of parallelism.
 
In this talk, we give a negative result for the above open problem in various settings. In the oracle model, we prove that there are time-independent sparse Hamiltonians that cannot be simulated via an oracle circuit of depth $o(T)$. In the plain model, relying on the random oracle heuristic, we show that there exist time-independent local Hamiltonians and time-dependent geometrically local Hamiltonians on $n$ qubits that cannot be simulated via an oracle circuit of depth $o(T/n^c)$, where the Hamiltonians act on $n$ qubits, and $c$ is a constant. Lastly, we generalize the above results and show that any simulators that are geometrically local Hamiltonians cannot do the simulation much faster than parallel quantum algorithms. 
 
Joint work with Nai-Hui Chia, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, and Yu-Ching Shen