License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2023.33
URN: urn:nbn:de:0030-drops-183038
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18303/
Chia, Nai-Hui ;
Chung, Kai-Min ;
Hsieh, Yao-Ching ;
Lin, Han-Hsuan ;
Lin, Yao-Ting ;
Shen, Yu-Ching
On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation
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 Ω(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.
BibTeX - Entry
@InProceedings{chia_et_al:LIPIcs.CCC.2023.33,
author = {Chia, Nai-Hui and Chung, Kai-Min and Hsieh, Yao-Ching and Lin, Han-Hsuan and Lin, Yao-Ting and Shen, Yu-Ching},
title = {{On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation}},
booktitle = {38th Computational Complexity Conference (CCC 2023)},
pages = {33:1--33:45},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-282-2},
ISSN = {1868-8969},
year = {2023},
volume = {264},
editor = {Ta-Shma, Amnon},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18303},
URN = {urn:nbn:de:0030-drops-183038},
doi = {10.4230/LIPIcs.CCC.2023.33},
annote = {Keywords: Hamiltonian simulation, Depth lower bound, Parallel query lower bound}
}
|
Keywords: |
|
Hamiltonian simulation, Depth lower bound, Parallel query lower bound |
|
Collection: |
|
38th Computational Complexity Conference (CCC 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
10.07.2023 |
