Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters
Authors:
- Dominic W. BerryDBDominic W. Berry
- Andrew M. ChildsACAndrew M. Childs
- Robin KothariRKRobin Kothari
Top Cited Papers
- 1 October 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 792-809
Abstract
We present an algorithm for sparse Hamiltonian simulation whose complexity is optimal (up to log factors) as a function of all parameters of interest. Previous algorithms had optimal or near-optimal scaling in some parameters at the cost of poor scaling in others. Hamiltonian simulation via a quantum walk has optimal dependence on the sparsity at the expense of poor scaling in the allowed error. In contrast, an approach based on fractional-query simulation provides optimal scaling in the error at the expense of poor scaling in the sparsity. Here we combine the two approaches, achieving the best features of both. By implementing a linear combination of quantum walk steps with coefficients given by Bessel functions, our algorithm's complexity (as measured by the number of queries and 2-qubit gates) is logarithmic in the inverse error, and nearly linear in the product tau of the evolution time, the sparsity, and the magnitude of the largest entry of the Hamiltonian. Our dependence on the error is optimal, and we prove a new lower bound showing that no algorithm can have sub linear dependence on tau.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Simulating quantum dynamics on a quantum computerJournal of Physics A: Mathematical and Theoretical, 2011
- Quantum Algorithm for Linear Systems of EquationsPhysical Review Letters, 2009
- Quantum lower bounds by polynomialsJournal of the ACM, 2001
- Limit on the Speed of Quantum Computation in Determining ParityPhysical Review Letters, 1998
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- Universal Quantum SimulatorsScience, 1996
- Quantum Mechanical ComputersOptics News, 1985
- Simulating physics with computersInternational Journal of Theoretical Physics, 1982
- Fast Multiple-Precision Evaluation of Elementary FunctionsJournal of the ACM, 1976
- Error Analysis of Miller's Recurrence AlgorithmMathematics of Computation, 1964