Solving Free Fermion Problems on a Quantum Computer

Abstract

Simulating noninteracting fermion systems is a common task in computational many-body physics. In absence of translational symmetries, modeling free fermions on $N$ modes usually requires poly$(N)$ computational resources. While often moderate, these costs can be prohibitive in practice when large systems are considered. We present several free-fermion problems that can be solved by a quantum algorithm with substantially reduced computational costs. The memory costs are exponentially improved, poly log$(N)$. The runtime improvement, compared to the best known classical algorithms, is either exponential or significantly polynomial, depending on the geometry of the problem. The simulation of free-fermion dynamics belongs to the BQP-hard complexity class. This implies (under standard assumptions) that our algorithm yields an exponential speedup for any classical algorithm at least for some geometries. The key technique in our algorithm is the block-encoding of objects such as correlation matrices and Green's functions into a unitary. We demonstrate how such unitaries can be efficiently realized as quantum circuits, in the context of dynamics and thermal states of tight-binding Hamiltonians. The special cases of disordered and inhomogeneous lattices, as well as large non-lattice graphs, are presented in detail. Finally, we show that our simulation algorithm generalizes to other promising targets, including free boson systems.

References in corpus (21)

• Kwant: a software package for quantum transport
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Hamiltonian Simulation by Qubitization
• Classical simulation of noninteracting-fermion quantum circuits
• Quantum Metropolis Sampling
• Anderson localization on random regular graphs
• Quantum Algorithm for Simulating the Wave Equation
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Scaling theory of the Anderson transition in random graphs: ergodicity and universality
• Line-Graph Lattices: Euclidean and Non-Euclidean Flat Bands, and Implementations in Circuit Quantum Electrodynamics
• Hierarchy of linear light cones with long-range interactions
• Two critical localization lengths in the Anderson transition on random graphs
• Speed limits and locality in many-body quantum dynamics
• Quantum Algorithms for Estimating Physical Quantities using Block-Encodings
• Exponential quantum speedup in simulating coupled classical oscillators
• Decay of Correlations in Fermi Systems at Non-zero Temperature
• Tkwant: a software package for time-dependent quantum transport
• Matchgate and space-bounded quantum computations are equivalent
• Renormalization Group Analysis of the Anderson Model on Random Regular Graphs
• Compressed quantum simulation of the Ising model
• Gate-based quantum simulation of Gaussian bosonic circuits on exponentially many modes

Cited by in corpus (3)

• Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations
• On the Trotter Error in Many-body Quantum Dynamics with Coulomb Potentials
• Quantum-computing within a bosonic context: Assessing finite basis effects on prototypical vibrational Hamiltonian spectra