Complexity of quantum impurity problems

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=H_0+H_{imp}$, where $H_0$ is quadratic in creation-annihilation operators and $H_{imp}$ 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}$ in time $n^3\exp [O(b^3)]$. Our algorithm also finds a low energy state that achieves this approximation. The low energy state is represented as a superposition of $\exp [O(b^3)]$ 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 $H_0$. A key ingredient of our proof is Zolotarev's rational approximation to the $\sqrt{x}$ 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.

References in corpus (1)

• Few-qubit quantum-classical simulation of strongly correlated lattice fermions

Cited by in corpus (60)

• Quantum algorithms for quantum chemistry and quantum materials science
• The Future of Quantum Computing with Superconducting Qubits
• Doubling the size of quantum simulators by entanglement forging
• Quantum algorithms to simulate many-body physics of correlated fermions
• Matchgate Shadows for Fermionic Quantum Simulation
• An efficient method for quantum impurity problems out of equilibrium
• Non-Abelian Floquet Spin Liquids in a Digital Rydberg Simulator
• Topologically protected braiding in a single wire using Floquet Majorana modes
• Coupled-cluster impurity solvers for dynamical mean-field theory
• Non-equilibrium quantum impurity problems via matrix-product states in the temporal domain
• Dynamics of Majorana-based qubits operated with an array of tunable gates
• Fusion protocol for Majorana modes in coupled quantum dots
• Dephasing and leakage dynamics of noisy Majorana-based qubits: Topological versus Andreev
• Matchgate benchmarking: Scalable benchmarking of a continuous family of many-qubit gates
• Free fermions behind the disguise
• Characterization of solvable spin models via graph invariants
• Dynamical signatures of quasiparticle interactions in quantum spin chains
• Hybrid quantum-classical algorithm for computing imaginary-time correlation functions
• Inelastic scattering of a photon by a quantum phase-slip
• Approximation algorithms for quantum many-body problems
• Matrix product state algorithms for Gaussian fermionic states
• Many-body Majorana braiding without an exponential Hilbert space
• Classical simulation of non-Gaussian fermionic circuits
• Optimizing sparse fermionic Hamiltonians
• Majorana quasiparticles in atomic spin chains on superconductors
• Doped stabilizer states in many-body physics and where to find them
• Nature of polaron-molecule transition in Fermi polarons
• Optimizing the transport of Majorana zero modes in one-dimensional topological superconductors
• Quasilocal entanglement across the Mott-Hubbard transition
• Sparse modeling of large-scale quantum impurity models with low symmetries
• Unraveling correlated material properties with noisy quantum computers: Natural orbitalized variational quantum eigensolving of extended impurity models within a slave-boson approach
• Efficient learning of quantum states prepared with few fermionic non-Gaussian gates
• Dissipative realization of Kondo models
• Boundary theories of critical matchgate tensor networks
• High ground state overlap via quantum embedding methods
• Improved simulation of quantum circuits dominated by free fermionic operations
• Multi-boundary generalization of thermofield double states and their realization in critical quantum spin chains
• The complexity of simulating local measurements on quantum systems
• Classical simulation of non-Gaussian bosonic circuits
• Variational approach to the dynamics of dissipative quantum impurity models
• Self-Consistent Determination of Single-Impurity Anderson Model Using Hybrid Quantum-Classical Approach on a Spin Quantum Simulator
• Quantum impurity models using superpositions of fermionic Gaussian states: Practical methods and applications
• Fermionic Magic Resources of Quantum Many-Body Systems
• A Non-Gaussian Variational Approach to Fermi Polarons in One- and Two-dimensional Lattices
• Classical simulation and quantum resource theory of non-Gaussian optics
• Simulating realistic screening clouds around quantum impurities: role of spatial anisotropy and disorder
• Optimal trace-distance bounds for free-fermionic states: Testing and improved tomography
• Efficient impurity-bath trial states from superposed Slater determinants
• Efficient Pseudomode Representation and Complexity of Quantum Impurity Models
• Variational quantum simulation of critical Ising model with symmetry averaging
• Topological Modes in Monitored Quantum Dynamics
• Comparative study on compact quantum circuits of hybrid quantum-classical algorithms for quantum impurity models
• Efficient Representation of Gaussian Fermionic Pure States in Non-Computational Bases
• Explicit Pfaffian Formula for Amplitudes of Fermionic Gaussian Pure States in Arbitrary Pauli Bases
• Shuttling Majorana zero modes in disordered and noisy topological superconductors
• Design and benchmarks for emulating Kondo dynamics on a quantum chip
• Classifying fermionic states via many-body correlation measures
• Excited states from local effective Hamiltonians of matrix product states and their entanglement spectrum transition
• Decoherence of Majorana zero modes mediated by gapless fermions
• Quantum entropy thermalization