Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters

Dominic W. Berry, Andrew M. Childs, Robin Kothari

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionResearchpeer-review

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.

LanguageEnglish
Title of host publicationProceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages792-809
Number of pages18
ISBN (Electronic)9781467381918
ISBN (Print)9781467381925
DOIs
Publication statusPublished - 11 Dec 2015
Event56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 - Berkeley, United States
Duration: 17 Oct 201520 Oct 2015

Other

Other56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
CountryUnited States
CityBerkeley
Period17/10/1520/10/15

Fingerprint

Hamiltonians
Bessel functions

Cite this

Berry, D. W., Childs, A. M., & Kothari, R. (2015). Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. In Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015 (pp. 792-809). [7354428] Piscataway, NJ: Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/FOCS.2015.54
Berry, Dominic W. ; Childs, Andrew M. ; Kothari, Robin. / Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. Piscataway, NJ : Institute of Electrical and Electronics Engineers (IEEE), 2015. pp. 792-809
@inproceedings{94530578b53641fdae97936966dd7e50,
title = "Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters",
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.",
author = "Berry, {Dominic W.} and Childs, {Andrew M.} and Robin Kothari",
year = "2015",
month = "12",
day = "11",
doi = "10.1109/FOCS.2015.54",
language = "English",
isbn = "9781467381925",
pages = "792--809",
booktitle = "Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015",
publisher = "Institute of Electrical and Electronics Engineers (IEEE)",
address = "United States",

}

Berry, DW, Childs, AM & Kothari, R 2015, Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. in Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015., 7354428, Institute of Electrical and Electronics Engineers (IEEE), Piscataway, NJ, pp. 792-809, 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, United States, 17/10/15. https://doi.org/10.1109/FOCS.2015.54

Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. / Berry, Dominic W.; Childs, Andrew M.; Kothari, Robin.

Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. Piscataway, NJ : Institute of Electrical and Electronics Engineers (IEEE), 2015. p. 792-809 7354428.

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionResearchpeer-review

TY - GEN

T1 - Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters

AU - Berry, Dominic W.

AU - Childs, Andrew M.

AU - Kothari, Robin

PY - 2015/12/11

Y1 - 2015/12/11

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84960348682&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2015.54

DO - 10.1109/FOCS.2015.54

M3 - Conference proceeding contribution

SN - 9781467381925

SP - 792

EP - 809

BT - Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015

PB - Institute of Electrical and Electronics Engineers (IEEE)

CY - Piscataway, NJ

ER -

Berry DW, Childs AM, Kothari R. Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. In Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. Piscataway, NJ: Institute of Electrical and Electronics Engineers (IEEE). 2015. p. 792-809. 7354428 https://doi.org/10.1109/FOCS.2015.54