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 $\mathrm{polylog}\log (1/\epsilon )$ on the simulation precision $\epsilon$. This presents an exponential improvement over the dependence $\mathrm{polylog}(1/\epsilon )$ 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 $\Omega (\log \log (1/\epsilon ))$ is established, showing that the $\epsilon$-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 $\mathrm{polylog}\log (1/\epsilon )$ dependence in the parallel setting.

Final version. 57 pages, 6 figures, 1 table

References in corpus (22)

• Quantum algorithm for solving linear systems of equations
• Many body localization and thermalization in quantum statistical mechanics
• Many-body localization edge in the random-field Heisenberg chain
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Recent progress in many-body localization
• Efficient Distributed Quantum Computing
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Simulating sparse Hamiltonians with star decompositions
• Low depth algorithms for quantum amplitude estimation
• Nearly tight Trotterization of interacting electrons
• Efficient Fully-Coherent Quantum Signal Processing Algorithms for Real-Time Dynamics Simulation
• Hamiltonian simulation with random inputs
• Compilation by stochastic Hamiltonian sparsification
• Fast-forwarding quantum evolution
• Randomizing multi-product formulas for Hamiltonian simulation
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
• Quantum algorithm for time-dependent Hamiltonian simulation by permutation expansion
• Multivariate trace estimation in constant quantum depth
• On the complexity of implementing Trotter steps
• Composite Quantum Simulations
• Quantum advantage for differential equation analysis

Cited by in corpus (8)

• Circuit complexity of quantum access models for encoding classical data
• Compact quantum algorithms for time-dependent differential equations
• Solving reaction dynamics with quantum computing algorithms
• Lower bound for simulation cost of open quantum systems: Lipschitz continuity approach
• Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
• Fat-Tree QRAM: A High-Bandwidth Shared Quantum Random Access Memory for Parallel Queries
• Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations