2026-07-25T05:30:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18303 2024-03-06T11:01:33Z ddc:004 open_access

On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation Chia, Nai-Hui Chung, Kai-Min Hsieh, Yao-Ching Lin, Han-Hsuan Lin, Yao-Ting Shen, Yu-Ching Hamiltonian simulation Depth lower bound Parallel query lower bound 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 Ω(T) 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 work, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nai-Hui Chia and Kai-Min Chung and Yao-Ching Hsieh and Han-Hsuan Lin and Yao-Ting Lin and Yu-Ching Shen 2023 Is Part Of LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2023.33 urn:nbn:de:0030-drops-183038 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.33 eng https://creativecommons.org/licenses/by/4.0/legalcode