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.

arXiv commentFinal version. 57 pages, 6 figures, 1 table

References in corpus (79)

• A variational eigenvalue solver on a quantum processor
• Quantum algorithm for solving linear systems of equations
• Many body localization and thermalization in quantum statistical mechanics
• Gapless Spin-Fluid Ground State in a Random Quantum Heisenberg Magnet
• Comments on the Sachdev-Ye-Kitaev model
• Many-body localization, thermalization, and entanglement
• Quantum Chemistry in the Age of Quantum Computing
• Many-body localization edge in the random-field Heisenberg chain
• Hamiltonian Simulation by Qubitization
• Quantum algorithms for quantum chemistry and quantum materials science
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Hartree-Fock on a superconducting qubit quantum computer
• The Spectrum in the Sachdev-Ye-Kitaev Model
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Many-body localization: an introduction and selected topics
• Grover's quantum searching algorithm is optimal
• Toward the first quantum simulation with quantum speedup
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Random Oracles in a Quantum World
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• On the relationship between continuous- and discrete-time quantum walk
• Quantum advantage with shallow circuits
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Simulating Physical Phenomena by Quantum Networks
• A random compiler for fast Hamiltonian simulation
• Recent progress in many-body localization
• Search via Quantum Walk
• Low Depth Quantum Simulation of Electronic Structure
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Efficient Distributed Quantum Computing
• Exponential improvement in precision for simulating sparse Hamiltonians
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Nearly optimal lattice simulation by product formulas
• Faster quantum simulation by randomization
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Higher Order Decompositions of Ordered Operator Exponentials
• An introduction to the SYK model
• Digital Quantum Simulation of Minimal AdS/CFT
• The methodology of resonant equiangular composite quantum gates
• Quantum advantage with noisy shallow circuits in 3D
• Exponentially more precise quantum simulation of fermions I: Quantum chemistry in second quantization
• Quantum algorithm for simulating real time evolution of lattice Hamiltonians
• Parallelizing Quantum Circuits
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Quantum Simulation of Chemistry with Sublinear Scaling in Basis Size
• Digital-Analog Quantum Simulations with Superconducting Circuits
• Quantum Circuits with Unbounded Fan-out
• Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
• Exponentially More Precise Quantum Simulation of Fermions in the Configuration Interaction Representation
• Simulating sparse Hamiltonians with star decompositions
• Quantum SDP-Solvers: Better upper and lower bounds
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• Low depth algorithms for quantum amplitude estimation
• Concentration for random product formulas
• Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series
• Nearly tight Trotterization of interacting electrons
• Efficient Fully-Coherent Quantum Signal Processing Algorithms for Real-Time Dynamics Simulation
• Compilation by stochastic Hamiltonian sparsification
• Hamiltonian simulation with random inputs
• Introduction to Quantum Algorithms for Physics and Chemistry
• Fast-forwarding quantum evolution
• Generalized Quantum Search with Parallelism
• 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
• Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• Equivalence Checking of Sequential Quantum Circuits
• Composite Quantum Simulations
• Quantum advantage for differential equation analysis
• Average-Case Quantum Advantage with Shallow Circuits
• On the Need for Large Quantum Depth

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