This thesis studies computational tasks that arise in quantum many-body physics, with an emphasis on fermionic systems. We develop complexity-theoretic classifications and constructive algorithmic results, thereby establishing opportunities and limitations of classical and quantum algorithms for carrying out these tasks.

Chapter 2 investigates the fermionic satisfiability problem, FERMIONIC k-SAT, which asks whether there exists a state in the joint null space of parity-preserving local fermionic projectors. This serves as a setting for understanding when the satisfiability of “quantum fermionic constraints” remains classically decidable. We show that the case k = 2 is efficiently solvable classically, but that adding global constraints can crucially change the complexity: enforcing particle-number parity preserves classical tractability, while fixing the particle number itself makes the problem NP-complete. We also show that at higher locality, k = 9, the problem becomes QMA1-hard.

Chapters 3 and 4 address fermionic Hamiltonian optimization through Gaussian approximations, motivated by the broader question of when simple classes of states provably capture a non-vanishing fraction of an interacting ground-state energy. In stark contrast to qubit Hamiltonians—for which product states provably achieve a constant fraction of the ground energy—fermionic Gaussian states achieve only a vanishing fraction in general. This raises the question of whether certain (physically motivated) structural assumptions can be imposed on fermionic Hamiltonians to avoid this “Gaussian breakdown.” Chapter 3 focuses on classically interacting (i.e., density-density interacting) fermionic Hamiltonians, reflecting the diagonal structure of Coulomb terms in electronic-structure models. Here we prove that fermionic Gaussian states achieve a constant approximation ratio of at least 1/3 for such Hamiltonians, and we develop efficient semidefinite programming methods for Gaussian approximations for several traceless and positive-semidefinite families, including variants that enforce a fixed average particle number. Chapter 4 shows that sparsity is another decisive structural assumption: for sparse fermionic Hamiltonians, Gaussian states also achieve a constant ratio of the ground energy, and the corresponding Gaussian state can be found efficiently.

Chapter 5 develops quantum algorithms for simulating (sparse) free fermions in a compressed representation. While free-fermion physics is classically tractable in an asymptotic sense, practical costs can still become prohibitive when simulating large systems. The key idea behind our quantum algorithms is to block-encode correlation matrices, Green’s functions, and related objects into quantum circuits, enabling procedures whose memory costs scale polylogarithmically in the number of modes—an exponential improvement in memory relative to standard classical representations. Depending on geometric structure (lattices versus general graphs), the resulting runtime improvement over the best known classical methods is exponential or strongly polynomial. Because the associated simulation tasks are BQP-hard, the results also imply that compressed free-fermion simulation should be viewed not merely as a convenience, but as a route to potential quantum advantage for some families of instances.

Chapters 6 and 7 share the theme of estimating spectra of many-body Hamiltonians from time-domain data and connect algorithm design to practical bottlenecks in extracting spectral information from experiments. Chapter 6 studies how spectral properties can be recovered from signals derived from time evolution, comparing a classical Monte Carlo scheme that estimates imaginary-time decays to quantum procedures that estimate real-time oscillations generated using phase-estimation-type circuits. We give guarantees on resolvability under assumptions relating to spectral gaps, initial states, and sign-problem-freeness of the Hamiltonian. Chapter 7 targets a different problem related to the practical implementation of phase-estimation-type quantum circuits on near-term devices. These circuits contain an expensive controlled time-evolution step, and their depth can be reduced by removing this control, making them more suitable for such devices. We realize this by employing adapted phase-retrieval methods, at the cost of running reduced-depth circuits more times. Numerical studies on the Fermi–Hubbard model illustrate the feasibility and noise resilience of our methods.

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, polylog(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 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 nonlattice graphs, are presented in detail. Finally, we show that our simulation algorithm generalizes to other promising targets, including free-boson systems.

We introduce the fermionic satisfiability problem, Fermionic k-SAT: this is the problem of deciding whether there is a fermionic state in the null-space of a collection of fermionic, parity-conserving, projectors on n fermionic modes, where each fermionic projector involves at most k fermionic modes. We prove that this problem can be solved efficiently classically for k = 2. In addition, we show that deciding whether there exists a satisfying assignment with a given fixed particle number parity can also be done efficiently classically for Fermionic 2-SAT: this problem is a quantum-fermionic extension of asking whether a classical 2-SAT problem has a solution with a given Hamming weight parity. We also prove that deciding whether there exists a satisfying assignment for particle-number-conserving Fermionic 2-SAT for some given particle number is NP-complete. Complementary to this, we show that Fermionic 9-SAT is QMA₁-hard.

We consider the problem of approximating the ground state energy of a fermionic Hamiltonian using a Gaussian state. In sharp contrast to the dense case [1, 2], we prove that strictly q-local sparse fermionic Hamiltonians have a constant Gaussian approximation ratio; the result holds for any connectivity and interaction strengths. Sparsity means that each fermion participates in a bounded number of interactions, and strictly q-local means that each term involves exactly q fermionic (Majorana) operators. We extend our proof to give a constant Gaussian approximation ratio for sparse fermionic Hamiltonians with both quartic and quadratic terms. With additional work, we also prove a constant Gaussian approximation ratio for the so-called sparse SYK model with strictly 4-local interactions (sparse SYK-4 model). In each setting we show that the Gaussian state can be efficiently determined. Finally, we prove that the O(n⁻¹/²) Gaussian approximation ratio for the normal (dense) SYK-4 model extends to SYK-q for even q > 4, with an approximation ratio of O(n¹/^2−q/4). Our results identify non-sparseness as the prime reason that the SYK-4 model can fail to have a constant approximation ratio [1, 2].

We consider the task of spectral estimation of local quantum Hamiltonians. The spectral estimation is performed by estimating the oscillation frequencies or decay rates of signals representing the time evolution of states. We present a classical Monte Carlo (MC) scheme which efficiently estimates an imaginary-time, decaying signal for stoquastic (i.e. sign-problem-free) local Hamiltonians. The decay rates in this signal correspond to Hamiltonian eigenvalues (with associated eigenstates present in an input state) and can be extracted using a classical signal processing method like ESPRIT. We compare the efficiency of this MC scheme to its quantum counterpart in which one extracts eigenvalues of a general local Hamiltonian from a real-time, oscillatory signal obtained through quantum phase estimation circuits, again using the ESPRIT method. We prove that the ESPRIT method can resolve S = poly(n) eigenvalues, assuming a 1/poly(n) gap between them, with poly(n) quantum and classical effort through the quantum phase estimation (QPE) circuits, assuming efficient preparation of the input state. We prove that our MC scheme plus the ESPRIT method can resolve S = O(1) eigenvalues, assuming a 1/poly(n) gap between them, with poly(n) purely classical effort for stoquastic Hamiltonians, requiring some access structure to the input state. However, we also show that under these assumptions, i.e. S = O(1) eigenvalues, assuming a 1/poly(n) gap between them and some access structure to the input state, one can achieve this with poly(n) purely classical effort for general local Hamiltonians. These results thus quantify some opportunities and limitations of MC methods for spectral estimation of Hamiltonians. We numerically compare the MC eigenvalue estimation scheme (for stoquastic Hamiltonians) and the quantum-phase-estimation-based eigenvalue estimation scheme by implementing them for an archetypal stoquastic Hamiltonian system: the transverse field Ising chain.