Simulating Sparse Hamiltonians with Star Decompositions
From MaRDI portal
Publication:3070979
DOI10.1007/978-3-642-18073-6_8zbMATH Open1309.68075arXiv1003.3683OpenAlexW1741741009MaRDI QIDQ3070979FDOQ3070979
Authors: Andrew M. Childs, Robin Kothari 
Publication date: 28 January 2011
Published in: Theory of Quantum Computation, Communication, and Cryptography (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1003.3683
Recommendations
- Efficient quantum algorithms for simulating sparse Hamiltonians
- Hamiltonian sparsification and gap-simulation
- Limitations on the simulation of non-sparse Hamiltonians
- Hamiltonian simulation with nearly optimal dependence on spectral norm
- scientific article; zbMATH DE number 6131346
- Optimized spatial matrix representations of quantum Hamiltonians
- Randomized algorithms for Hamiltonian simulation
Cited In (21)
- A generalized circuit for the Hamiltonian dynamics through the truncated series
- A Quantum Implementation Model for Artificial Neural Networks
- Quantum algorithm design: techniques and applications
- Product formulas for exponentials of commutators
- Limitations on the simulation of non-sparse Hamiltonians
- Bounding the costs of quantum simulation of many-body physics in real space
- Efficient quantum algorithms for simulating sparse Hamiltonians
- Black-box Hamiltonian simulation and unitary implementation
- Optimization of quantum Hamiltonian evolution: from two projection operators to local Hamiltonians
- On the gap of Hamiltonians for the adiabatic simulation of quantum circuits
- Hamiltonian simulation with nearly optimal dependence on spectral norm
- Quantum algorithms for Hamiltonian simulation
- Simulating arbitrary pair-interactions by a given Hamiltonian: graph-theoretical bounds on the time-complexity
- Efficient quantum circuits for continuous-time quantum walks on composite graphs
- Obtaining a linear combination of the principal components of a matrix on quantum computers
- Multiple network alignment on quantum computers
- Quantum spin dynamics with pairwise-tunable, long-range interactions
- Context-aware quantum simulation of a matrix stored in quantum memory
- Hamiltonian sparsification and gap-simulation
- Algorithm for quantum simulation
- Divide and conquer approach to quantum Hamiltonian simulation
This page was built for publication: Simulating Sparse Hamiltonians with Star Decompositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3070979)
