Time:12:10, Monday, May 22, 2023
Speaker:Prof. Kai-Min Chung
               鐘楷閔教授
               Institute of Information Science, Academia Sinica
Title:On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation
Place:R36169, 1F, Dept. of Physics, Building of Science College, NCKU

Abstract:

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