Complexity of Quantum Impurity Problems
Open accessThe DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.
Abstract
We give a quasi-polynomial time classical algorithm for estimating the ground state energy and for computing low energy states of quantum impurity models. Such models describe a bath of free fermions coupled to a small interacting subsystem called an impurity. The full system consists of n fermionic modes and has a Hamiltonian H=H0+Himp\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${H=H_0+H_{imp}}$$\end{document}, where H0 is quadratic in creation–annihilation operators and Himp is an arbitrary Hamiltonian acting on a subset of O(1) modes. We show that the ground energy of H can be approximated with an additive error 2-b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${2^{-b}}$$\end{document} in time n3exp[O(b3)]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${n^3 \exp{[O(b^3)]}}$$\end{document}. Our algorithm also finds a low energy state that achieves this approximation. The low energy state is represented as a superposition of exp[O(b3)]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\exp{[O(b^3)]}}$$\end{document} fermionic Gaussian states. To arrive at this result we prove several theorems concerning exact ground states of impurity models. In particular, we show that eigenvalues of the ground state covariance matrix decay exponentially with the exponent depending very mildly on the spectral gap of H0. A key ingredient of our proof is Zolotarev’s rational approximation to the x\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\sqrt{x}}$$\end{document} function. We anticipate that our algorithms may be used in hybrid quantum-classical simulations of strongly correlated materials based on dynamical mean field theory. We implemented a simplified practical version of our algorithm and benchmarked it using the single impurity Anderson model.
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.
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
Resistance Minimum in Dilute Magnetic Alloys
Kondo, J. (1964) · Progress of Theoretical Physics · doi:10.1143/ptp.32.37 · Cited by 3,658
Childs, A. M., Kothari, R., & Somma, R. D. (2017) · SIAM Journal on Computing · doi:10.1137/16m1087072 · Cited by 646
Classical simulation of noninteracting-fermion quantum circuits
Terhal, B. M., & DiVincenzo, D. P. (2002) · Physical Review A · doi:10.1103/physreva.65.032325 · Cited by 329 · cited 1×
“[21,22].”
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 1×
“This can be done efficiently since H(γ) is a sparse and efficiently row-computable Hamiltonian [40].”
BackgroundSolving strongly correlated electron models on a quantum computer
Wecker, D., Hastings, M. B., Wiebe, N., Clark, B. K., Nayak, C., & Troyer, M. (2015) · Physical Review A · doi:10.1103/physreva.92.062318 · Cited by 285 · cited 1×
“[36]; we summarize it here for completeness.”
Schuch, N., & Verstraete, F. (2009) · Nature Physics · doi:10.1038/nphys1370 · Cited by 260 · cited 1×
“Formally, this problem is complete for the complexity class QMA – a quantum analogue of NP [11, 12].”
BackgroundQuantum Hamiltonian Complexity
Gharibian, S., Huang, Y., Landau, Z., & Shin, S. W. (2015) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000066 · Cited by 144
Cited by
Quantum 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
Self-citationThe future of quantum computing with superconducting qubits
Bravyi, S., Dial, O., Gambetta, J. M., Gil, D., & Nazario, Z. (2022) · Journal of Applied Physics · doi:10.1063/5.0082975 · Cited by 334
Self-citationQuantum Algorithms to Simulate Many-Body Physics of Correlated Fermions
Jiang, Z., Sung, K. J., Kechedzhi, K., Smelyanskiy, V. N., & Boixo, S. (2018) · Physical Review Applied · doi:10.1103/physrevapplied.9.044036 · Cited by 175
“Recently, superpositions of fermionic Gaussian states were used to approximate low-energy states of quantum impurity models [50], which can be useful in a quantum-classical hybrid scheme for correlated materials [35].”
MethodQuantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithm
Verdon, G., Marks, J., Nanda, S., Leichenauer, S., & Hidary, J. (2019) · arXiv · doi:10.48550/arxiv.1910.02071 · Cited by 45
Metadata
- Authors
- Bravyi, S., & Gosset, D.
- Venue
- Communications in Mathematical Physics
- Published
- 2017-08-31
- Volume
- 356
- Issue
- 2
- Pages
- 451-500
- ISSN
- 0010-3616 (ISSN-L)
- 1432-0916
- OpenAlex
- W2517482430
- Cited by
- 84
- References
- 7
- FWCI
- 2.30
- Type
- journal article
- Language
- en
- Open access
- green
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: Complexity of Quantum Impurity Problems. https://app.cochat.ai/papers/10.1007/s00220-017-2976-9
- The paper
- Bravyi, S., & Gosset, D. (2017). Complexity of Quantum Impurity Problems. Communications in Mathematical Physics. https://doi.org/10.1007/s00220-017-2976-9
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.