Simulating Sparse Hamiltonians with Star Decompositions
Open accessThe DOI matches its Crossref record; 17 of the 20 references it cites were found in a registry or an index.
Abstract
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 (d2(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 (d4(d+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.
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 cited source says what the claim attributes to it.
In the citing paper
“The quantum 'split-operator' method 75,273 is analogous to classical exact wave function simulation techniques such as matching pursuit/split-operator Fourier transform 176 .”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [273]
The check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“Kinetic energy terms can be diagonalized using the quantum Fourier transform.”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [273]
Experimental — accuracy not yet measuredIn the citing paper
“Independently of Lloyd's quantum simulation algorithm 37 , Zalka 273 introduced a quantum algorithm for simulation of single- and many-body quantum systems.”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [273]
In the citing paper
“The Green's function for a quantum particle is then approximated by a product of exponentials with potential and kinetic energy in the exponents.”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [273]
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
Lloyd, S. (1996) · Science · doi:10.1126/science.273.5278.1073 · Cited by 3,088 · cited 12×
“These Hamiltonians are then recombined using the Lie–Trotter formula, which expresses the time evolution due to H as a product of time evolutions due to the Hj.”
MethodInfluentialExponential 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
Self-citationEfficient 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 8×
“[3], providing the best known method for high-precision simulation of sparse Hamiltonians.”
BackgroundMethodInfluentialQuantum Computation by Adiabatic Evolution
Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (2000) · arXiv · doi:10.48550/arxiv.quant-ph/0001106 · Cited by 536 · cited 1×
“Besides simulating physics, Hamiltonian simulation has algorithmic applications, such as adiabatic optimization [5], unstructured search [6], and the implementation of continuous-time quantum walks [7, 8].”
MethodDeterministic coin tossing with applications to optimal parallel list ranking
Cole, R. J., & Vishkin, U. (1986) · Information and Control · doi:10.1016/s0019-9958(86)80023-7 · Cited by 413 · cited 1×
“Vishkin [13] by Goldberg, Plotkin and Shannon [14].”
MethodOn 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 2×
“[3] has also been improved using a completely different approach [10, 11].”
BackgroundMethodSelf-citationAnalog analogue of a digital quantum computation
Farhi, E., & Gutmann, S. (1998) · Physical Review A · doi:10.1103/physreva.57.2403 · Cited by 384 · cited 1×
“Besides simulating physics, Hamiltonian simulation has algorithmic applications, such as adiabatic optimization [5], unstructured search [6], and the implementation of continuous-time quantum walks [7, 8].”
MethodAdiabatic 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 1×
“This was later generalized by Aharonov and Ta-Shma [2] to the case of sparse (and efficiently row-computable) Hamiltonians.”
MethodParallel Symmetry-Breaking in Sparse Graphs
Goldberg, A. V., Plotkin, S. A., & Shannon, G. E. (1988) · SIAM Journal on Discrete Mathematics · doi:10.1137/0401044 · Cited by 203
Research works printed but not linked: 1
- 8. Farhi, E., Goldstone, J., Gutmann, S.: A quantum algorithm for the Hamiltonian NAND tree. Theory Of Computing 4 (2008) 169-190 · doi:10.4086/toc.2008.v004a008
Cited by
A variational eigenvalue solver on a photonic quantum processor
Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., & O’Brien, J. L. (2014) · Nature Communications · doi:10.1038/ncomms5213 · Cited by 4,552
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
Quantum Chemistry in the Age of Quantum Computing
Cao, Y., Romero, J., Olson, J., Degroote, M., Johnson, P., Kieferová, M., Kivlichan, I., Menke, T., Peropadre, B., Sawaya, N., et al. (n.d.) · OPUS - Open Publications of UTS Scholars (University of Technology Sydney) · Cited by 1,265
Toward the first quantum simulation with quantum speedup
Childs, A. M., Maslov, D., Nam, Y., Ross, N. J., & Su, Y. (2018) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1801723115 · Cited by 551
Self-citationQuantum Algorithms for Quantum Field Theories
Jordan, S. P., Lee, K. S. M., & Preskill, J. (2012) · Science · doi:10.1126/science.1217069 · Cited by 517
Metadata
- Authors
- Childs, A. M., & Kothari, R.
- Affiliations
- University of Waterloo (CA)
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 2011
- Pages
- 94-103
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W1741741009
- Cited by
- 85
- References
- 20
- Citations by year
- 2025: 2 · 2024: 3 · 2023: 6 · 2022: 2 · 2021: 4 · 2020: 4 · 2019: 5 · 2018: 6 · 2017: 10 · 2016: 6 · 2015: 2 · 2014: 12 · 2013: 6 · 2012: 9
- FWCI
- 8.37
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Lecture notes in computer science (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Mitacs
- Natural Sciences and Engineering Research Council of Canada
- Army Research Office
- 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 › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- quantum simulation, star decomposition, Hamiltonian decomposition, time evolution, query complexity, maximum degree, quantum algorithms, Hamiltonian graphs
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: Simulating Sparse Hamiltonians with Star Decompositions. https://app.cochat.ai/papers/10.1007/978-3-642-18073-6_8
- The paper
- Childs, A. M., & Kothari, R. (2011). Simulating Sparse Hamiltonians with Star Decompositions. Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-642-18073-6_8
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.