A quantum algorithm for simulating non-sparse Hamiltonians
arXiv:1803.08273
Abstract
We present a quantum algorithm for simulating the dynamics of Hamiltonians that are not necessarily sparse. Our algorithm is based on the input model where the entries of the Hamiltonian are stored in a data structure in a quantum random access memory (qRAM) which allows for the efficient preparation of states that encode the rows of the Hamiltonian. We use a linear combination of quantum walks to achieve poly-logarithmic dependence on precision. The time complexity of our algorithm, measured in terms of the circuit depth, is , where is the evolution time, is the dimension of the system, and is the error in the final state, which we call precision. Our algorithm can be directly applied as a subroutine for unitary implementation and quantum linear systems solvers, achieving dependence for both applications.
arXiv comment19 pages, 1 figure, presentation improved
References in corpus (14)
- Quantum algorithm for solving linear systems of equations
- Quantum support vector machine for big data classification
- Quantum principal component analysis
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Quantum machine learning: a classical perspective
- On the relationship between continuous- and discrete-time quantum walk
- Hamiltonian simulation with nearly optimal dependence on all parameters
- Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
- A quantum linear system algorithm for dense matrices
- Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
- Quantum Recommendation Systems
- Hamiltonian Simulation by Uniform Spectral Amplification
- Advances in quantum machine learning