Understand
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.
Built on
Simulating physics with computers
Feynman, R.: · 1982
Earlier work this paper cites.
Deterministic coin tossing with applications to optimal parallel list ranking
Cole, R., Vishkin, U.: · 1986
Earlier work this paper cites.
Parallel symmetry-breaking in sparse graphs
Goldberg, A.V., Plotkin, S.A., Shannon, G.E.: · 1988
Earlier work this paper cites.
Universal quantum simulators
Lloyd, S.: · 1996
Earlier work this paper cites.
Analog analogue of a digital quantum computation
Farhi, E., Gutmann, S.: · 1998
Earlier work this paper cites.
Similar
Quantum computation by adiabatic evolution
Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: · 2000
Cited alongside, same era.
Some simple distributed algorithms for sparse networks
Panconesi, A., Rizzi, R.: · 2001
Cited alongside, same era.
Adiabatic quantum state generation and statistical zero knowledge
Aharonov, D., Ta-Shma, A.: · 2003
Cited alongside, same era.
Exponential algorithmic speedup by a quantum walk
Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., Spielman, D.A.: · 2003
Cited alongside, same era.
Quantum information processing in continuous time
Childs, A.M.: · 2004
Cited alongside, same era.
Then
Efficient quantum algorithms for simulating sparse Hamiltonians
Berry, D., Ahokas, G., Cleve, R., Sanders, B.: · 2007
Later among the works it cites.
A quantum algorithm for the Hamiltonian NAND tree
Farhi, E., Goldstone, J., Gutmann, S.: · 2008
Later among the works it cites.
The quantum query complexity of implementing black-box unitary transformations
Berry, D.W., Childs, A.M.: · 2009
Later among the works it cites.
On the relationship between continuous- and discrete-time quantum walk
Childs, A.M.: · 2010
Closest in time.
Limitations on the simulation of non-sparse Hamiltonians
Childs, A.M., Kothari, R.: · 2010
Closest in time.
Beyond the bibliography
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…