Simulating sparse Hamiltonians with star decompositions
arXiv:1003.3683 · doi:10.1007/978-3-642-18073-6_8
Abstract
We present an efficient algorithm for simulating the time evolution due to a sparse Hamiltonian. In terms of the maximum degree d and dimension N of the space on which the Hamiltonian H acts for time t, this algorithm uses (d^2(d+log* N)||Ht||)^{1+o(1)} queries. This improves the complexity of the sparse Hamiltonian simulation algorithm of Berry, Ahokas, Cleve, and Sanders, which scales like (d^4(log* N)||Ht||)^{1+o(1)}. To achieve this, we decompose a general sparse Hamiltonian into a small sum of Hamiltonians whose graphs of non-zero entries have the property that every connected component is a star, and efficiently simulate each of these pieces.
11 pages. v2: minor corrections
References in corpus (4)
Cited by in corpus (49)
- A variational eigenvalue solver on a quantum processor
- Quantum Chemistry in the Age of Quantum Computing
- Toward the first quantum simulation with quantum speedup
- Quantum Algorithms for Quantum Field Theories
- Can One Trust Quantum Simulators?
- Gate count estimates for performing quantum chemistry on small quantum computers
- Hybrid quantum-classical approach to correlated materials
- From transistor to trapped-ion computers for quantum chemistry
- Emerging quantum computing algorithms for quantum chemistry
- Quantum Spin Dynamics with Pairwise-Tunable, Long-Range Interactions
- Quantum Algorithm for Linear Regression
- Quantum Algorithms for Simulating the Lattice Schwinger Model
- Noisy intermediate-scale quantum computers
- Hamiltonian Simulation Using Linear Combinations of Unitary Operations
- Quantum Complexity of Time Evolution with Chaotic Hamiltonians
- Bounding the costs of quantum simulation of many-body physics in real space
- Introduction to Quantum Algorithms for Physics and Chemistry
- Quantum Walks
- Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
- Variational quantum eigensolvers for sparse Hamiltonians
- Black-box Hamiltonian simulation and unitary implementation
- Superdiffusive quantum stochastic walk definable of arbitrary directed graph
- Efficient simulation of sparse Markovian quantum dynamics
- Quantum rejection sampling
- Toward simulating Superstring/M-theory on a quantum computer
- Hamiltonian simulation with nearly optimal dependence on spectral norm
- Efficient quantum circuits for continuous-time quantum walks on composite graphs
- Product Formulas for Exponentials of Commutators
- Circuit complexity of quantum access models for encoding classical data
- Improved Bounds for Eigenpath Traversal
- Span-program-based quantum algorithm for the rank problem
- Obtaining A Linear Combination of the Principal Components of a Matrix on Quantum Computers
- Parallel Quantum Algorithm for Hamiltonian Simulation
- A quantum algorithm for track reconstruction in the LHCb vertex detector
- Multiple Network Alignment on Quantum Computers
- A Quantum Implementation Model for Artificial Neural Networks
- Efficient Quantum Algorithms for Analyzing Large Sparse Electrical Networks
- Approximating Hamiltonian dynamics with the Nyström method
- Quantum Spectral Clustering through a Biased Phase Estimation Algorithm
- Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
- A Generalized Circuit for the Hamiltonian Dynamics Through the Truncated Series
- Efficient Algorithms for Universal Quantum Simulation
- Context aware quantum simulation of a matrix stored in quantum memory
- Quantum simulation of quantum mechanical system with spatial noncommutativity
- Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
- Efficient implementation of unitary transformations
- Efficient quantum circuits for dense and non-unitary operators
- Using Quantum Computers to Learn Physics
- Optimisation of Quantum Hamiltonian Evolution: From Two Projection Operators to Local Hamiltonians