Exponential improvement in precision for simulating sparse Hamiltonians
Open accessThe DOI matches its Crossref record; 38 of the 38 references it cites were found in a registry or an index.
Abstract
We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a d-sparse Hamiltonian H on n qubits can be simulated for time t with precision ε using O(τlog(τ/ε)/log log(τ/ε)) queries and O(τnlog2(τ/ε)/log log(τ/ε)) additional 2-qubit gates, where τ=d2||H||maxt. Unlike previous approaches based on product formulas, the query complexity is independent of the number of qubits acted on, and for time-varying Hamiltonians, the gate complexity is logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful than the discrete model even for very small error. We also significantly simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of "oblivious amplitude amplification" that can be applied even though the reflection about the input state is unavailable. Finally, we prove new lower bounds showing that our algorithms are optimal as a function of the error.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“Indeed, there are already proposals 200 for NISQ algorithms based on variational principles 201,202 .”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [202]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691
Quantum Algorithm for Linear Systems of Equations
Harrow, A. W., Hassidim, A., & Lloyd, S. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.150502 · Cited by 3,325 · cited 1×
“Sparse Hamiltonian simulation is also useful in quantum algorithms [1, 12, 21, 15].”
MethodLloyd, S. (1996) · Science · doi:10.1126/science.273.5278.1073 · Cited by 3,088 · cited 2×
“Lloyd provided an explicit algorithm for simulating many realistic quantum systems, namely those whose Hamiltonian is a sum of interactions acting nontrivially on a small number of subsystems of limited dimension [24].”
BackgroundPerfect State Transfer in Quantum Spin Networks
Christandl, M., Datta, N., Ekert, A., & Landahl, A. J. (2004) · Physical Review Letters · doi:10.1103/physrevlett.92.187902 · Cited by 1,179 · cited 1×
“, N } [15].”
Exponential algorithmic speedup by a quantum walk
Childs, A. M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., & Spielman, D. A. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780552 · Cited by 825 · cited 1×
“(also applied in [11]) is to use edge coloring to decompose the Hamiltonian H into a sum of Hamiltonians ∑η j=1Hj , where each Hj is easy to simulate.”
MethodSelf-citationSuzuki, M. (1991) · Journal of Mathematical Physics · doi:10.1063/1.529425 · Cited by 762 · cited 1×
“This was later improved using high-order product formulas (from [29]) and more efficient decompositions of the Hamiltonian [9, 5, 13].”
MethodEfficient Quantum Algorithms for Simulating Sparse Hamiltonians
Berry, D. W., Ahokas, G., Cleve, R., & Sanders, B. C. (2007) · Communications in Mathematical Physics · doi:10.1007/s00220-006-0150-x · Cited by 692 · cited 7×
“, [24, 1, 9, 5, 13]), as well as an alternative approach based on sums of unitary operators [14].”
BackgroundMethodInfluentialSelf-citationQuantum lower bounds by polynomials
Beals, R., Buhrman, H., Cleve, R., Mosca, M., & de Wolf, R. (2001) · Journal of the ACM · doi:10.1145/502090.502097 · Cited by 639
Self-citationOn the Relationship Between Continuous- and Discrete-Time Quantum Walk
Childs, A. M. (2010) · Communications in Mathematical Physics · doi:10.1007/s00220-009-0930-1 · Cited by 411 · cited 3×
“In the context of time-independent sparse Hamiltonian simulation, the quantum walk-based simulation of [10, 6] achieves linear dependence on t, whereas our upper bound”
BackgroundMethodInfluentialSelf-citationAnalog analogue of a digital quantum computation
Farhi, E., & Gutmann, S. (1998) · Physical Review A · doi:10.1103/physreva.57.2403 · Cited by 384
Research works printed but not linked: 7
- [8] Andrew M. Childs, Quantum information processing in continuous time , Ph.D. thesis, Massachusetts Institute of Technology, 2004. [p. 2] - · doi:10.5555/1037515
- [12] Andrew M. Childs, David Gosset, and Zak Webb, Universal computation by multi-particle quantum walk , Science 339 (2013), no. 6121, 791-794, arXiv:1205.3782. [p. 21] - · arXiv
- [13] Andrew M. Childs and Robin Kothari, Simulating sparse Hamiltonians with star decompositions , Theory of Quantum Computation, Communication, and Cryptography (TQC 2010), Lecture Notes in Computer Science, vol. 6519, pp. 94-103, 2011, arXiv:1003.3683. [pp. 2, 14] - · arXiv
- 10.5555/2481569.2481570 · doi:10.5555/2481569.2481570
- [24] Camille Jordan, Essai sur la g´ eom´ etrie ` a n dimensions , Bulletin de la Soci´ et´ e Math´ ematique de France 3 (1875), 103-174. [p. 10] -
- [29] Rajeev Motwani and Prabhakar Raghavan, Randomized algorithms , Cambridge University Press, 1995. [p. 27] -
- [34] George N. Watson, A treatise on the theory of Bessel functions , Cambridge University Press, 1922. [p. 20] -
Cited by
Quantum computational chemistry
McArdle, S., Endo, S., Aspuru-Guzik, A., Benjamin, S. C., & Yuan, X. (2020) · Reviews of Modern Physics · doi:10.1103/revmodphys.92.015003 · Cited by 1,621
Quantum Chemistry in the Age of Quantum Computing
Cao, Y., Romero, J., Olson, J. P., Degroote, M., Johnson, P. D., Kieferová, M., Kivlichan, I. D., Menke, T., Peropadre, B., Sawaya, N. P. D., et al. (2019) · Chemical Reviews · doi:10.1021/acs.chemrev.8b00803 · Cited by 1,560
Hamiltonian Simulation by Qubitization
Low, G. H., & Chuang, I. L. (2019) · Quantum · doi:10.22331/q-2019-07-12-163 · Cited by 854
“See Cor. 7, 8, 9 for applications.”
BackgroundInfluentialQuantum Algorithms for Quantum Chemistry and Quantum Materials Science
Bauer, B., Bravyi, S., Motta, M., & Chan, G. K.-L. (2020) · Chemical Reviews · doi:10.1021/acs.chemrev.9b00829 · Cited by 848
Optimal Hamiltonian Simulation by Quantum Signal Processing
Low, G. H., & Chuang, I. L. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.010501 · Cited by 769
“sub-logarithmic scaling in error O ( τ log (τ/ ) log log (τ/ ) ) [17, 21].”
BackgroundInfluential
Metadata
- Authors
- Berry, D. W., Childs, A. M., Cleve, R., Kothari, R., & Somma, R. D.
- Affiliations
- Macquarie University (AU)
- University of Waterloo (CA)
- Los Alamos National Laboratory (US)
- Venue
- Proceedings of the forty-sixth annual ACM symposium on Theory of computing
- Publisher
- ACM
- Published
- 2014-05-31
- Pages
- 283-292
- OpenAlex
- W1985671429
- Cited by
- 324
- References
- 28
- Citations by year
- 2026: 16 · 2025: 38 · 2024: 38 · 2023: 49 · 2022: 25 · 2021: 38 · 2020: 17 · 2019: 26 · 2018: 17 · 2017: 19 · 2016: 17 · 2015: 16 · 2014: 6
- FWCI
- 11.38
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- ACM Symposium on Theory of Computing (STOC) (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Army Research Office
- Natural Sciences and Engineering Research Council of Canada
- Ontario Ministry of Research and Innovation
- Australian Research Council (FT100100761)
- Laboratory Directed Research and Development Program at LANL
- Canadian Institute for Advanced Research
- Mitacs
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Keywords
- quantum simulation, sparse Hamiltonians, query complexity, time evolution simulation, lower bounds, fault-tolerant quantum computing, product formula
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Exponential improvement in precision for simulating sparse Hamiltonians. https://app.cochat.ai/papers/10.1145/2591796.2591854
- The paper
- Berry, D. W., Childs, A. M., Cleve, R., Kothari, R., & Somma, R. D. (2014). Exponential improvement in precision for simulating sparse Hamiltonians. Proceedings of the forty-sixth annual ACM symposium on Theory of computing. https://doi.org/10.1145/2591796.2591854
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.