Optimization and Quantum Simulation of Fermions

Abstract

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.