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
Adiabatic quantum state generation and statistical zero knowledge
Aharonov, D., & Ta-Shma, A. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780546 · Cited by 322 · cited 4×
“Sparse Hamiltonian simulation is also useful in quantum algorithms [1, 12, 21, 15].”
BackgroundMethodInfluentialPreconditioned Quantum Linear System Algorithm
Clader, B. D., Jacobs, B. C., & Sprouse, C. R. (2013) · Physical Review Letters · doi:10.1103/physrevlett.110.250504 · Cited by 288 · cited 1×
“Sparse Hamiltonian simulation is also useful in quantum algorithms [1, 12, 21, 15].”
MethodQuantum Simulation of Time-Dependent Hamiltonians and the Convenient Illusion of Hilbert Space
Poulin, D., Qarry, A., Somma, R., & Verstraete, F. (2011) · Physical Review Letters · doi:10.1103/physrevlett.106.170501 · Cited by 265 · cited 2×
“Another previous simulation method [28] also improved the dependence on h′, but at the cost of substantially worse dependence on t and ε.”
BackgroundMethodSelf-citationMarriott, C., & Watrous, J. (2005) · computational complexity · doi:10.1007/s00037-005-0194-x · Cited by 241 · cited 5×
“The motivation for oblivious amplitude amplification comes from work of Marriott and Watrous on in-place amplification of QMA [25] (see also related work using amplitude amplification to obtain a quadratic improvement [27]).”
MethodInfluentialLimit on the Speed of Quantum Computation in Determining Parity
Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (1998) · Physical Review Letters · doi:10.1103/physrevlett.81.5442 · Cited by 181 · cited 2×
“We observe that simulating this Hamiltonian (with sufficiently high precision) for any time t > 0 gives an unbounded-error algorithm for the parity of n bits, which also requires Ω(n) queries [18, 4].”
BackgroundQuantum Lower Bounds by Polynomials
Beals, R., Buhrman, H., Cleve, R., Mosca, M., & de Wolf, R. (1998) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9802049 · Cited by 164
Self-citationQuantum Query Complexity of State Conversion
Lee, T., Mittal, R., Reichardt, B. W., palek, R., & Szegedy, M. (2011) · 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.75 · Cited by 138 · cited 3×
“For the problem of evaluating a classical function of a black-box input, an approach based on an invariant called the γ2 norm shows that the continuous-query complexity is at most a constant factor smaller than the discrete-query complexity for a bounded-error simulation [23].”
BackgroundNagaj, D., Wocjan, P., & Zhang, Y. (2009) · Quantum Information and Computation · doi:10.26421/qic9.11-12-8 · Cited by 134 · cited 1×
“The motivation for oblivious amplitude amplification comes from work of Marriott and Watrous on in-place amplification of QMA [25] (see also related work using amplitude amplification to obtain a quadratic improvement [27]).”
MethodAny AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
Ambainis, A., Childs, A. M., Reichardt, B. W., Špalek, R., & Zhang, S. (2010) · SIAM Journal on Computing · doi:10.1137/080712167 · Cited by 122
Self-citationSimulating quantum dynamics on a quantum computer
Wiebe, N., Berry, D. W., Høyer, P., & Sanders, B. C. (2011) · Journal of Physics A: Mathematical and Theoretical · doi:10.1088/1751-8113/44/44/445308 · Cited by 110 · cited 1×
“This dependence on h ′ is a dramatic improvement over previous methods for simulating time-dependent Hamiltonians using high-order product formulas [30].”
MethodSelf-citationAdiabatic Quantum State Generation and Statistical Zero KnowledgePreprint
Aharonov, D., & Ta‐Shma, A. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0301023 · Cited by 109 · cited 4×
“Sparse Hamiltonian simulation is also useful in quantum algorithms [1, 12, 21, 15].”
BackgroundMethodInfluentialBlack-box Hamiltonian simulation and unitary implementation
Childs, A. M., & Berry, D. W. (2012) · Quantum Information and Computation · doi:10.26421/qic12.1-2-4 · Cited by 101
Self-citationProduct formula methods for time-dependent Schrodinger problems
Huyghebaert, J., & Raedt, H. D. (1990) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/23/24/019 · Cited by 75 · cited 1×
“An explicit simulation of the continuous-query model by the fractionalquery model was provided by [16]; the proof is a straightforward application of a result of [22].”
MethodA Quantum Algorithm for the Hamiltonian NAND Tree
Farhi, E., Goldstone, J., & Gutmann, S. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0702144 · Cited by 70 · cited 5×
“[19] E. Farhi and S. Gutmann.”
BackgroundInfluentialDiscrete-query quantum algorithm for NAND trees
Childs, A. M., Cleve, R., Jordan, S. P., & Yonge-Mallo, D. (2009) · Theory of Computing · doi:10.4086/toc.2009.v005a005 · Cited by 67
Self-citationMochon, C. (2007) · Physical Review A · doi:10.1103/physreva.75.042313 · Cited by 50 · cited 2×
“sumed in [26]); we provide a proof in the full version of this paper [7].”
BackgroundSymmetry-Assisted Adversaries for Quantum State Generation
Ambainis, A., Magnin, L., Roetteler, M., & Roland, J. (2011) · 2011 IEEE 26th Annual Conference on Computational Complexity · doi:10.1109/ccc.2011.24 · Cited by 49 · cited 1×
“In order of increasing generality, such tasks include state generation [3], state conversion [23], and implementing unitary operations [6].”
BackgroundQuantum algorithm for solving linear systems of equationsPreprint
Harrow, A. W., Hassidim, A., & Lloyd, S. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0811.3171 · Cited by 48 · cited 1×
“Sparse Hamiltonian simulation is also useful in quantum algorithms [1, 12, 21, 15].”
MethodEfficient discrete-time simulations of continuous-time quantum query algorithms
Cleve, R., Gottesman, D., Mosca, M., Somma, R. D., & Yonge-Mallo, D. L. (2009) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1536414.1536471 · Cited by 40 · cited 13×
“The existence of such a U that makes O(log(1/ε)/log log(1/ε)) queries was shown by [16].”
BackgroundMethodInfluentialSelf-citationAn Analog Analogue of a Digital Quantum ComputationPreprint
Farhi, E., & Gutmann, S. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9612026 · Cited by 16
Gate-efficient discrete simulations of continuous-time quantum query algorithms
Berry, D. W., Cleve, R., & Gharibian, S. (2014) · Quantum Information and Computation · doi:10.26421/qic14.1-2-1 · Cited by 15 · cited 9×
“Up to this point our proof is similar to previous approaches [16, 8].”
BackgroundMethodResultInfluentialSelf-citationHamiltonian Simulation Using Linear Combinations of Unitary OperationsPreprint
Childs, A. M., & Wiebe, N. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1202.5822 · Cited by 13
Self-citationZero-knowledge against quantum attacksPreprint
Watrous, J. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0511020 · Cited by 6 · cited 1×
“The motivation for oblivious amplitude amplification comes from work of Marriott and Watrous on in-place amplification of QMA [27] (see also related work on quantum rewinding for zero-knowledge proofs [33] and on using amplitude amplification to obtain a quadratic improvement [30]).”
BackgroundQuantum Arthur-Merlin GamesPreprint
Marriott, C., & Watrous, J. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0506068 · Cited by 5 · cited 5×
“The motivation for oblivious amplitude amplification comes from work of Marriott and Watrous on in-place amplification of QMA [25] (see also related work using amplitude amplification to obtain a quadratic improvement [27]).”
MethodInfluentialNagajDaniel, WocjanPaweł, & Zhangyong (2009) · Quantum Information and Computation · doi:10.5555/2012098.2012106 · Cited by 4
Gate-efficient discrete simulations of continuous-time quantum query algorithmsPreprint
Berry, D. W., Cleve, R., & Gharibian, S. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1211.4637 · Cited by 3 · cited 9×
“Up to this point our proof is similar to previous approaches [16, 8].”
BackgroundMethodResultInfluentialSelf-citationSimulating Quantum Dynamics On A Quantum ComputerPreprint
Wiebe, N., Berry, D. W., Høyer, P., & Sanders, B. C. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1011.3489 · Cited by 1 · cited 1×
“This dependence on h ′ is a dramatic improvement over previous methods for simulating time-dependent Hamiltonians using high-order product formulas [30].”
MethodSelf-citationFast Amplification of QMAPreprint
Nagaj, D., Wocjan, P., & Zhang, Y. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0904.1549 · cited 1×
“The motivation for oblivious amplitude amplification comes from work of Marriott and Watrous on in-place amplification of QMA [25] (see also related work using amplitude amplification to obtain a quadratic improvement [27]).”
Method
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
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.