The DOI matches its Crossref record; 63 of the 64 references it cites were found in a registry or an index.
Hamiltonian simulation with optimal sample complexity
Open accessAbstract
We investigate the sample complexity of Hamiltonian simulation: how many copies of an unknown quantum state are required to simulate a Hamiltonian encoded by the density matrix of that state? We show that the procedure proposed by Lloyd, Mohseni, and Rebentrost [ Nat. Phys. , 10(9):631–633, 2014] is optimal for this task. We further extend their method to the case of multiple input states, showing how to simulate any Hermitian polynomial of the states provided. As applications, we derive optimal algorithms for commutator simulation and orthogonality testing, and we give a protocol for creating a coherent superposition of pure states, when given sample access to those states. We also show that this sample-based Hamiltonian simulation can be used as the basis of a universal model of quantum computation that requires only partial swap operations and simple single-qubit states.
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
Figures


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?
In the citing paper
“As detailed by Aspuru-Guzik et al. 45 and Dobˇ s´ ıˇ cek et al. 275 , the number of ancilla qubits can be greatly reduced, while maintaining the same precision by using the iterative quantum phase estimation algorithm (IPEA).”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [275]
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
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Quantum Computation and Quantum Information: 10th Anniversary Edition
Nielsen, M. A., & Chuang, I. L. (2012) · doi:10.1017/cbo9780511976667 · Cited by 8,436
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691
Quantum computation with quantum dots
Loss, D., & DiVincenzo, D. P. (1998) · Physical Review A · doi:10.1103/physreva.57.120 · Cited by 6,840 · cited 1×
“In many solid state implementations of quantum computers such as quantum dots [LD98], donor-pairs [Kan98], and electron spins [VYW + 00], the Heisenberg exchange is the natural coupling interaction between qubits.”
BackgroundElementary gates for quantum computation
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995) · Physical Review A · doi:10.1103/physreva.52.3457 · Cited by 4,311 · cited 1×
“While it is beneficial to create computing models that take advantage of this Heisenberg exchange interaction, the Heisenberg interaction is not universal for spin-1/2 systems [BBC + 95].”
MethodA silicon-based nuclear spin quantum computer
Kane, B. E. (1998) · Nature · doi:10.1038/30156 · Cited by 3,779
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×
“In addition, Hamiltonian simulation has implications for more general computational problems, including adiabatic algorithms [FGGS00], quantum walk algorithms [CCD + 03], and algorithms for systems of linear equations [HHL09].”
MethodLloyd, S. (1996) · Science · doi:10.1126/science.273.5278.1073 · Cited by 3,088 · cited 1×
“Lloyd provided the first formal results on simulation, considering Hamiltonians that consist of sums of non-commuting terms.(1) Other lines of research have focused on simulating sparse Hamiltonians, with a long sequence of work recently culminating in an optimal algorithm(2) (see ref.”
BackgroundQuantum Detection and Estimation Theory
(1976) · Mathematics in Science and Engineering · doi:10.1016/s0076-5392(08)x6017-5 · Cited by 2,426
Quantum Support Vector Machine for Big Data Classification
Rebentrost, P., Mohseni, M., & Lloyd, S. (2014) · Physical Review Letters · doi:10.1103/physrevlett.113.130503 · Cited by 1,951
Cited by
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., & Lloyd, S. (2017) · Nature · doi:10.1038/nature23474 · Cited by 4,779
“This quantum BLAS (qBLAS) translates into quantum speedups for a variety of data analysis and machine learning algorithms including linear algebra, least-squares fitting, gradient descent, Newton’s method, principal component analysis, linear, semidefinite, and quadratic programming, topological analysis, and support…”
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
“…the ancilla of some output from a quantum circuit ˆ G , we instead keep this ancilla, leading to an unconditional quadratic improvement in time scaling, and an exponential improvement in error scaling over the sample-based Lloyd, Mohseni, and Rebentrost (LMR) model [32, 28], as summarized in Table.”
MethodSelf-citationGilyén, A., Su, Y., Low, G. H., & Wiebe, N. (2019) · Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing · doi:10.1145/3313276.3316366 · Cited by 542
“This technique can be used in combination with the optimal block-Hamiltonian simulation result Corollary 32, in order to get much better simulation performance, compared to density matrix exponentiation techniques [38, 40] which does not use purification.”
MethodSelf-citationQuantum Algorithms: A Survey of Applications and End-to-end Complexities
Dalzell, A. M., McArdle, S., Berta, M., Bienias, P., Chen, C.-F., Gilyén, A., Hann, C. T., Kastoryano, M. J., Khabiboulline, E. T., Kubica, A., et al. (2023) · RWTH Publications (RWTH Aachen) · doi:10.18154/rwth-2026-02888 · Cited by 359
Metadata
- Authors
- Kimmel, S., Lin, C. Y.-Y., Low, G. H., Ozols, M., & Yoder, T. J.
- Affiliations
- Joint Center for Quantum Information and Computer Science (US)
- Massachusetts Institute of Technology (US)
- Venue
- npj Quantum Information
- Published
- 2017-03-30
- Volume
- 3
- Issue
- 1
- ISSN
- 2056-6387 (ISSN-L)
- OpenAlex
- W2490964415
- Cited by
- 85
- References
- 64
- Citations by year
- 2026: 4 · 2025: 17 · 2024: 10 · 2023: 9 · 2022: 6 · 2021: 7 · 2020: 9 · 2019: 12 · 2018: 5 · 2017: 4
- FWCI
- 4.90
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Licence
- cc-by
- creativecommons.org/licenses/by/4.0 (tdm)
- creativecommons.org/licenses/by/4.0 (vor)
- Locations
- npj Quantum Information (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- University Libraries (University of Maryland) (submittedVersion)
- Apollo (University of Cambridge) (submittedVersion, cc-by)
- arXiv (Cornell University)
- Digital Repository at the University of Maryland (University of Maryland College Park)
- Apollo (cc-by)
- Funders
- National Science Foundation
- U.S. Department of Defense (32 CFR 168 a)
- Massachusetts Institute of Technology
- Leverhulme Trust (ECF-2015-256)
- European Commission (600700)
- National Defense Science and Engineering Graduate (32 CFR 168a, CFR 168a)
- Army Research Office (32 CFR 168A)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- Hamiltonian simulation, sample complexity, quantum state tomography, optimal algorithms, Hermitian polynomials, universal quantum computation
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: Hamiltonian simulation with optimal sample complexity. https://app.cochat.ai/papers/10.1038/s41534-017-0013-7
- The paper
- Kimmel, S., Lin, C. Y.-Y., Low, G. H., Ozols, M., & Yoder, T. J. (2017). Hamiltonian simulation with optimal sample complexity. npj Quantum Information. https://doi.org/10.1038/s41534-017-0013-7
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.