  Simulation of quantum systems of a large number of strongly interacting
particles persists as one of the most challenging, and computationally
demanding, tasks in classical simulation, involving both non-relativistic
applications like condensed matter physics and quantum chemistry, as well as
relativistic applications like lattice gauge theory simulation. One of the
major motivations for building a fault-tolerant quantum computer is the
efficient simulation of many-body systems on such a device. While significant
developments have been made in the quantum simulation of non-relativistic
systems, the simulation of lattice gauge theories has lagged behind, with
state-of-the-art Trotterized simulations requiring many orders of magnitude
more resources than non-relativistic simulation, in stark contrast to the
similar difficulty of these tasks in classical simulation. In this work, we
conduct an in-depth analysis of the cost of simulating Abelian and non-Abelian
lattice gauge theories in the Kogut-Susskind formulation using simulation
methods with near-optimal scaling in system size, evolution time, and error. We
provide explicit circuit constructions, as well as T-gate counts and qubit
counts for the entire simulation algorithm. This investigation, the first of
its kind, leads to up to 25 orders of magnitude improvement over Trotterization
in spacetime volume for non-Abelian simulations. Such a dramatic improvement
results largely from our algorithm having polynomial scaling with the number of
colors, as opposed to exponential scaling in existing approaches. Our work
demonstrates that the use of advanced algorithmic techniques leads to dramatic
reductions in the cost of ab initio simulations of fundamental interactions,
bringing it in step with resources required for first principles quantum
simulation of chemistry and condensed matter physics.
