Parallel Quantum Algorithm for Hamiltonian Simulation

Abstract: We study how parallelism can speed up quantum simulation. A parallel quantum algorithm is proposed for simulating the dynamics of a large class of Hamiltonians with good sparse structures, called uniform-structured Hamiltonians, including various Hamiltonians of practical interest like local Hamiltonians and Pauli sums. Given the oracle access to the target sparse Hamiltonian, in both query and gate complexity, the running time of our parallel quantum simulation algorithm measured by the quantum circuit depth has a doubly (poly-)logarithmic dependence polylog log(1/є) on the simulation precision є. This presents an exponential improvement over the dependence polylog(1/є) of previous optimal sparse Hamiltonian simulation algorithm without parallelism. To obtain this result, we introduce a novel notion of parallel quantum walk, based on Childs’ quantum walk. The target evolution unitary is approximated by a truncated Taylor series, which is obtained by combining these quantum walks in a parallel way. A lower bound Ω(log log(1/є)) is established, showing that the є-dependence of the gate depth achieved in this work cannot be significantly improved. Our algorithm is applied to simulating three physical models: the Heisenberg model, the Sachdev-Ye-Kitaev model and a quantum chemistry model in second quantization. By explicitly calculating the gate complexity for implementing the oracles, we show that on all these models, the total gate depth of our algorithm has a polylog log(1/є) dependence in the parallel setting.

quantum computing and information

Audience: researchers in the topic

( paper )

Comments: Online Seminar. To request the zoom link, please send a message cqsiadmin@uts.edu.au using your business/organisation/institution email address. Seminar Webpage: www.uts.edu.au/research/centre-quantum-software-and-information/events/qsi-seminar-zhicheng-zhang-ucas-beijing

---

Centre for Quantum Software and Information Seminar Series

Series comments: To request the zoom link, please send a message to: cqsiadmin@uts.edu.au using your business/organisation/institution email address. Watch previous seminars on YouTube: - QSI Seminar Series 2021 (https://youtube.com/playlist?list=PLux7B14QYkPbDDOpqKSWScHXHodiBwr48) - QSI Seminar Series 2020 (https://youtube.com/playlist?list=PLux7B14QYkPZREUXReOq01ewLl02QXBXa)

---