Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2409.04550 · Physical Review Research

Solving free fermion problems on a quantum computer

Maarten Stroeks, Daan Lenterman, Barbara M. Terhal, Yaroslav Herasymenko

Published Nov 18, 2025• 15 citations
arXivHTMLPDF

Abstract

Simulating noninteracting fermion systems is a common task in computational many-body physics. In the 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 run-time 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 (i.e., as hard as any (decision) problem that can be solved on a quantum computer). This implies (under standard assumptions) that our algorithm yields an exponential speedup for 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 nonlattice graphs, are presented in detail. Finally, we show that our simulation algorithm generalizes to other promising targets, including free-boson systems.

DOI
10.1103/zmwm-gdmw

Related papers

Polynomial-time classical and quantum simulation of quantum impurity models

Jiaqing Jiang, Nathan Ju, Ojas Parekh +2 more

Quantum impurity models are paradigmatic models of interacting quantum matter, as well as key computational primitives for modern electronic-structure methods. They describe a small subsystem of interacting fermions coupled to a large, noninteracting bath. We perform a comprehensive study of the computational complexity of simulating impurity models, delineating the boundary between classical and quantum tractability for this class of problems. Our main finding is that static properties of quantum impurity models can be calculated efficiently on a classical computer. Specifically, we give classical algorithms that (1) estimate the ground-state energy to additive precision $δ$ in time $\mathrm{poly}(n,δ^{-1})$, and (2) estimate the partition function at inverse temperature $β$ to relative precision $δ$ in time $\mathrm{poly}(n,β,δ^{-1})$, where $n$ is the system size. These results improve the previous best-known complexity for ground-state energy estimation from quasipolynomial to polynomial time, while establishing for the first time rigorous polynomial-time guarantees for simulating impurity models in thermal equilibrium. On the other hand, we find that simulating dynamical properties of impurity models is hard for classical computers but easy on a quantum computer. As a canonical example, we show that computing their nonequilibrium Green's functions captures the full power of quantum computation, even at finite temperature. Taken together, our results rule out superpolynomial quantum speedups for computing static properties, but provide an avenue for quantum advantage in simulating impurity physics out of equilibrium.

quant-pharXiv:2610.02167•Oct 2, 2026•2 citations

Quantum Algorithms with Applications to Simulating Physical Systems

Anirban Ch Narayan Chowdhury

The simulation of quantum physical systems is expected to be an important application for quantum computers. The work presented in this dissertation aims to improve the resource requirements of quantum computers for solving simulation problems, by providing both novel quantum algorithms and improved implementations of existing ones. I present three main results that cover diverse aspects of simulation including equilibrium physics, the preparation of useful quantum states, and simulations based on classical stochastic processes. The results rely on established quantum algorithms and other recent techniques which I review. My first original contribution is a new quantum algorithm to sample from the thermal Gibbs state of quantum Hamiltonians. The complexity of this algorithm has an exponentially improved dependence on precision compared to an earlier quantum algorithm, and also provides polynomial improvements in other parameters. My second contribution is an improved algorithm to implement reflections about the eigenstates of unitary operators and Hamiltonians, an operation that can be used to prepare ground states of many-body Hamiltonians by quantum amplitude amplification. The improved algorithm for implementing reflections significantly reduces the number of ancilla qubits required over earlier implementations. The improvement relies in part on a novel quantum algorithm for efficiently preparing states with Gaussian-like amplitudes, which may have broad applications. I also prove a lower bound for implementing reflections, which shows that our algorithm is almost optimal. My third and final contribution regards quantum algorithms for classical stochastic processes, which are of importance in statistical physics. I present a quantum algorithm that estimates the average running time of a stochastic process, and provides a quadratic speed-up over a comparable classical algorithm.

•Jan 1, 2019•0 citations

Fast classical simulation algorithms for free-fermion dynamics with magic input

Jiwon Heo, Oliver Reardon-Smith, Michał Oszmaniec +2 more

The classical cost of simulating free-fermion (matchgate) circuits depends on both the input state and the computational task. We develop classical algorithms for circuits with non-Gaussian inputs, addressing exact sampling and both additive-error and exact estimation of expectation values. For inputs consisting of $n$ copies of the four-mode magic state, we give exact sampling algorithms, generalizing the Clifford and Clifford algorithm for Boson sampling, for passive and active free-fermion dynamics with worst-case arithmetic cost $O(2^n)$ per sample, without any multiplicative polynomial prefactor. The passive algorithm enables an exact simulation of the non-interacting regime of a recent trapped-ion experiment. We also extend recently developed additive-error estimation of number correlators and related observables from passive to active dynamics with runtime polynomial in $n$ and the inverse additive-error, for input states formed by products of $n$ four-mode even parity states. Our estimator uses a Gaussian-state decomposition adapted to each sampled state to control its second moment. This includes estimation of individual output probabilities. Finally, we show that for even-parity product inputs composed of constant-size blocks, expectation values of Majorana monomials of logarithmic weight can be computed exactly in polynomial time, improving on prior Majorana propagation-style algorithms with quasi-polynomial runtime. The exact algorithm processes the input blocks by dynamic programming, sharing calculations across subsets of Majorana factors. Our suite of algorithms provide classical benchmarks for fermionic quantum simulations across a broad spectrum of computational tasks.

quant-pharXiv:2609.40187•Oct 1, 2026•0 citations

Quantum Algorithms for Scientific Computing and Approximate Optimization

Stuart Hadfield

Quantum computation appears to offer significant advantages over classical computation and this has generated a tremendous interest in the field. In this thesis we study the application of quantum computers to computational problems in science and engineering, and to combinatorial optimization problems. We outline the results below. Algorithms for scientific computing require modules, i.e., building blocks, implementing elementary numerical functions that have well-controlled numerical error, are uniformly scalable and reversible, and that can be implemented efficiently. We derive quantum algorithms and circuits for computing square roots, logarithms, and arbitrary fractional powers, and derive worst-case error and cost bounds. We describe a modular approach to quantum algorithm design as a first step towards numerical standards and mathematical libraries for quantum scientific computing. A fundamental but computationally hard problem in physics is to solve the time-independent Schrödinger equation. This is accomplished by computing the eigenvalues of the corresponding Hamiltonian operator. The eigenvalues describe the different energy levels of a system. The cost of classical deterministic algorithms computing these eigenvalues grows exponentially with the number of system degrees of freedom. The number of degrees of freedom is typically proportional to the number of particles in a physical system. We show an efficient quantum algorithm for approximating a constant number of low-order eigenvalues of a Hamiltonian using a perturbation approach. We apply this algorithm to a special case of the Schrödinger equation and show that our algorithm succeeds with high probability, and has cost that scales polynomially with the number of degrees of freedom and the reciprocal of the desired accuracy. This improves and extends earlier results on quantum algorithms for estimating the ground state energy. We consider the simulation of quantum mechanical systems on a quantum computer. We show a novel divide and conquer approach for Hamiltonian simulation. Using the Hamiltonian structure, we can obtain faster simulation algorithms. Considering a sum of Hamiltonians we split them into groups, simulate each group separately, and combine the partial results. Simulation is customized to take advantage of the properties of each group, and hence yield refined bounds to the overall simulation cost. We illustrate our results using the electronic structure problem of quantum chemistry, where we obtain significantly improved cost estimates under mild assumptions. We turn to combinatorial optimization problems. An important open question is whether quantum computers provide advantages for the approximation of classically hard combinatorial problems. A promising recently proposed approach of Farhi et al. is the Quantum Approximate Optimization Algorithm (QAOA). We study the application of QAOA to the Maximum Cut problem, and derive analytic performance bounds for the lowest circuit-depth realization, for both general and special classes of graphs. Along the way, we develop a general procedure for analyzing the performance of QAOA for other problems, and show an example demonstrating the difficulty of obtaining similar results for greater depth. We show a generalization of QAOA and its application to wider classes of combinatorial optimization problems, in particular, problems with feasibility constraints. We introduce the Quantum Alternating Operator Ansatz, which utilizes more general unitary operators than the original QAOA proposal. Our framework facilitates low-resource implementations for many applications which may be particularly suitable for early quantum computers. We specify design criteria, and develop a set of results and tools for mapping diverse problems to explicit quantum circuits. We derive constructions for several important prototypical problems including Maximum Independent Set, Graph Coloring, and the Traveling Salesman problem, and show appealing resource cost estimates for their implementations.

arXiv:1805.03265•Jan 1, 2018•79 citations

Improved Quantum Algorithms for Simulating Many-Body Systems

Sophia Simon

Quantum computers are expected to significantly outperform classical computers for certain computational tasks. One of the most promising applications is the simulation of many-body systems such as complex molecules or materials. In this thesis, we present several quantum algorithms for simulating many-body systems that can provide considerably better scaling than prior approaches. First, we describe a fully coherent quantum algorithm for simulating molecular dynamics within the Born-Oppenheimer approximation that leads to super-polynomially better scaling with respect to the error tolerance than previous work. Our algorithm utilizes the Koopman-von Neumann formulation of classical mechanics. This allows us to express the classical equations of motion as unitary dynamics which can be efficiently simulated on a quantum computer. We demonstrate that these simulations can be performed either at constant energy or at constant temperature. The latter allows us to estimate thermodynamic properties such as the Helmholtz free energy of the system. Next, we present two closely related quantum algorithms for solving continuous optimization problems such as finding the equilibrium configurations of molecules. These algorithms do not require any explicit gradient estimations. Instead, we encode the optimization problem into the dynamics of a quantum or classical system with friction. The dynamics are governed by a carefully chosen time-dependent Hamiltonian and thus can be simulated using efficient Hamiltonian simulation algorithms. We provide evidence that our fully coherent quantum algorithms can, in certain cases, provide exponentially better asymptotic scaling than approaches based on gradient descent. Lastly, we present a quantum algorithm for preparing the ground state of a set of interacting systems that can circumvent the exponential scaling suggested by the Van Vleck catastrophe. Our algorithm utilizes a divide-and-conquer strategy that repeatedly uses phase estimation to merge ground states of increasingly larger subsystems. We provide rigorous bounds for this approach and show that, under certain assumptions, our algorithm scales only quasi-polynomially with the number of systems.

•Jun 1, 2026•0 citations

Quantum Algorithms to Simulate Many-Body Physics of Correlated Fermions

Zhang Jiang, Kevin J. Sung, Kostyantyn Kechedzhi +2 more

Physical systems with strongly correlated electrons (fermions) are notoriously difficult to study using traditional computers. Meanwhile, as programmable $q\phantom{\rule{0}{0ex}}u\phantom{\rule{0}{0ex}}a\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}t\phantom{\rule{0}{0ex}}u\phantom{\rule{0}{0ex}}m$ computers become a reality, efficient (and preferably general) quantum algorithms are needed, in the face of limited qubit-qubit connectivity in the near term. Addressing both problems, the authors develop quantum algorithms that run on two-dimensional qubit lattices with nearest-neighbor interactions, to simulate strongly correlated fermions. Their approach avoids the parity problem in mapping fermionic operators to qubit operators, with hardly any overhead, and can be used for a whole class of problems.

arXiv:1711.05395•Physical Review Applied•Apr 26, 2018•193 citations
Simulating noninteracting fermion systems is a common task in computational many-body physics. In the 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 run-time 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 (i.e., as hard as any (decision) problem that can be solved on a quantum computer). This implies (under standard assumptions) that our algorithm yields an exponential speedup for 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 nonlattice graphs, are presented in detail. Finally, we show that our simulation algorithm generalizes to other promising targets, including free-boson systems.
Quantum impurity models are paradigmatic models of interacting quantum matter, as well as key computational primitives for modern electronic-structure methods. They describe a small subsystem of interacting fermions coupled to a large, noninteracting bath. We perform a comprehensive study of the computational complexity of simulating impurity models, delineating the boundary between classical and quantum tractability for this class of problems. Our main finding is that static properties of quantum impurity models can be calculated efficiently on a classical computer. Specifically, we give classical algorithms that (1) estimate the ground-state energy to additive precision δδδ in time poly(n,δ−1)\mathrm{poly}(n,δ^{-1})poly(n,δ−1), and (2) estimate the partition function at inverse temperature βββ to relative precision δδδ in time poly(n,β,δ−1)\mathrm{poly}(n,β,δ^{-1})poly(n,β,δ−1), where nnn is the system size. These results improve the previous best-known complexity for ground-state energy estimation from quasipolynomial to polynomial time, while establishing for the first time rigorous polynomial-time guarantees for simulating impurity models in thermal equilibrium. On the other hand, we find that simulating dynamical properties of impurity models is hard for classical computers but easy on a quantum computer. As a canonical example, we show that computing their nonequilibrium Green's functions captures the full power of quantum computation, even at finite temperature. Taken together, our results rule out superpolynomial quantum speedups for computing static properties, but provide an avenue for quantum advantage in simulating impurity physics out of equilibrium.
The simulation of quantum physical systems is expected to be an important application for quantum computers. The work presented in this dissertation aims to improve the resource requirements of quantum computers for solving simulation problems, by providing both novel quantum algorithms and improved implementations of existing ones. I present three main results that cover diverse aspects of simulation including equilibrium physics, the preparation of useful quantum states, and simulations based on classical stochastic processes. The results rely on established quantum algorithms and other recent techniques which I review. My first original contribution is a new quantum algorithm to sample from the thermal Gibbs state of quantum Hamiltonians. The complexity of this algorithm has an exponentially improved dependence on precision compared to an earlier quantum algorithm, and also provides polynomial improvements in other parameters. My second contribution is an improved algorithm to implement reflections about the eigenstates of unitary operators and Hamiltonians, an operation that can be used to prepare ground states of many-body Hamiltonians by quantum amplitude amplification. The improved algorithm for implementing reflections significantly reduces the number of ancilla qubits required over earlier implementations. The improvement relies in part on a novel quantum algorithm for efficiently preparing states with Gaussian-like amplitudes, which may have broad applications. I also prove a lower bound for implementing reflections, which shows that our algorithm is almost optimal. My third and final contribution regards quantum algorithms for classical stochastic processes, which are of importance in statistical physics. I present a quantum algorithm that estimates the average running time of a stochastic process, and provides a quadratic speed-up over a comparable classical algorithm.
The classical cost of simulating free-fermion (matchgate) circuits depends on both the input state and the computational task. We develop classical algorithms for circuits with non-Gaussian inputs, addressing exact sampling and both additive-error and exact estimation of expectation values. For inputs consisting of nnn copies of the four-mode magic state, we give exact sampling algorithms, generalizing the Clifford and Clifford algorithm for Boson sampling, for passive and active free-fermion dynamics with worst-case arithmetic cost O(2n)O(2^n)O(2n) per sample, without any multiplicative polynomial prefactor. The passive algorithm enables an exact simulation of the non-interacting regime of a recent trapped-ion experiment. We also extend recently developed additive-error estimation of number correlators and related observables from passive to active dynamics with runtime polynomial in nnn and the inverse additive-error, for input states formed by products of nnn four-mode even parity states. Our estimator uses a Gaussian-state decomposition adapted to each sampled state to control its second moment. This includes estimation of individual output probabilities. Finally, we show that for even-parity product inputs composed of constant-size blocks, expectation values of Majorana monomials of logarithmic weight can be computed exactly in polynomial time, improving on prior Majorana propagation-style algorithms with quasi-polynomial runtime. The exact algorithm processes the input blocks by dynamic programming, sharing calculations across subsets of Majorana factors. Our suite of algorithms provide classical benchmarks for fermionic quantum simulations across a broad spectrum of computational tasks.
Quantum computation appears to offer significant advantages over classical computation and this has generated a tremendous interest in the field. In this thesis we study the application of quantum computers to computational problems in science and engineering, and to combinatorial optimization problems. We outline the results below. Algorithms for scientific computing require modules, i.e., building blocks, implementing elementary numerical functions that have well-controlled numerical error, are uniformly scalable and reversible, and that can be implemented efficiently. We derive quantum algorithms and circuits for computing square roots, logarithms, and arbitrary fractional powers, and derive worst-case error and cost bounds. We describe a modular approach to quantum algorithm design as a first step towards numerical standards and mathematical libraries for quantum scientific computing. A fundamental but computationally hard problem in physics is to solve the time-independent Schrödinger equation. This is accomplished by computing the eigenvalues of the corresponding Hamiltonian operator. The eigenvalues describe the different energy levels of a system. The cost of classical deterministic algorithms computing these eigenvalues grows exponentially with the number of system degrees of freedom. The number of degrees of freedom is typically proportional to the number of particles in a physical system. We show an efficient quantum algorithm for approximating a constant number of low-order eigenvalues of a Hamiltonian using a perturbation approach. We apply this algorithm to a special case of the Schrödinger equation and show that our algorithm succeeds with high probability, and has cost that scales polynomially with the number of degrees of freedom and the reciprocal of the desired accuracy. This improves and extends earlier results on quantum algorithms for estimating the ground state energy. We consider the simulation of quantum mechanical systems on a quantum computer. We show a novel divide and conquer approach for Hamiltonian simulation. Using the Hamiltonian structure, we can obtain faster simulation algorithms. Considering a sum of Hamiltonians we split them into groups, simulate each group separately, and combine the partial results. Simulation is customized to take advantage of the properties of each group, and hence yield refined bounds to the overall simulation cost. We illustrate our results using the electronic structure problem of quantum chemistry, where we obtain significantly improved cost estimates under mild assumptions. We turn to combinatorial optimization problems. An important open question is whether quantum computers provide advantages for the approximation of classically hard combinatorial problems. A promising recently proposed approach of Farhi et al. is the Quantum Approximate Optimization Algorithm (QAOA). We study the application of QAOA to the Maximum Cut problem, and derive analytic performance bounds for the lowest circuit-depth realization, for both general and special classes of graphs. Along the way, we develop a general procedure for analyzing the performance of QAOA for other problems, and show an example demonstrating the difficulty of obtaining similar results for greater depth. We show a generalization of QAOA and its application to wider classes of combinatorial optimization problems, in particular, problems with feasibility constraints. We introduce the Quantum Alternating Operator Ansatz, which utilizes more general unitary operators than the original QAOA proposal. Our framework facilitates low-resource implementations for many applications which may be particularly suitable for early quantum computers. We specify design criteria, and develop a set of results and tools for mapping diverse problems to explicit quantum circuits. We derive constructions for several important prototypical problems including Maximum Independent Set, Graph Coloring, and the Traveling Salesman problem, and show appealing resource cost estimates for their implementations.
Quantum computers are expected to significantly outperform classical computers for certain computational tasks. One of the most promising applications is the simulation of many-body systems such as complex molecules or materials. In this thesis, we present several quantum algorithms for simulating many-body systems that can provide considerably better scaling than prior approaches. First, we describe a fully coherent quantum algorithm for simulating molecular dynamics within the Born-Oppenheimer approximation that leads to super-polynomially better scaling with respect to the error tolerance than previous work. Our algorithm utilizes the Koopman-von Neumann formulation of classical mechanics. This allows us to express the classical equations of motion as unitary dynamics which can be efficiently simulated on a quantum computer. We demonstrate that these simulations can be performed either at constant energy or at constant temperature. The latter allows us to estimate thermodynamic properties such as the Helmholtz free energy of the system. Next, we present two closely related quantum algorithms for solving continuous optimization problems such as finding the equilibrium configurations of molecules. These algorithms do not require any explicit gradient estimations. Instead, we encode the optimization problem into the dynamics of a quantum or classical system with friction. The dynamics are governed by a carefully chosen time-dependent Hamiltonian and thus can be simulated using efficient Hamiltonian simulation algorithms. We provide evidence that our fully coherent quantum algorithms can, in certain cases, provide exponentially better asymptotic scaling than approaches based on gradient descent. Lastly, we present a quantum algorithm for preparing the ground state of a set of interacting systems that can circumvent the exponential scaling suggested by the Van Vleck catastrophe. Our algorithm utilizes a divide-and-conquer strategy that repeatedly uses phase estimation to merge ground states of increasingly larger subsystems. We provide rigorous bounds for this approach and show that, under certain assumptions, our algorithm scales only quasi-polynomially with the number of systems.
Physical systems with strongly correlated electrons (fermions) are notoriously difficult to study using traditional computers. Meanwhile, as programmable $q\phantom{\rule{0}{0ex}}u\phantom{\rule{0}{0ex}}a\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}t\phantom{\rule{0}{0ex}}u\phantom{\rule{0}{0ex}}m$ computers become a reality, efficient (and preferably general) quantum algorithms are needed, in the face of limited qubit-qubit connectivity in the near term. Addressing both problems, the authors develop quantum algorithms that run on two-dimensional qubit lattices with nearest-neighbor interactions, to simulate strongly correlated fermions. Their approach avoids the parity problem in mapping fermionic operators to qubit operators, with hardly any overhead, and can be used for a whole class of problems.