  In recent years simulations of chemistry and condensed materials has emerged
as one of the preeminent applications of quantum computing, offering an
exponential speedup for the solution of the electronic structure for certain
strongly correlated electronic systems. To date, most treatments have ignored
the question of whether relativistic effects, which are described most
generally by quantum electrodynamics (QED), can also be simulated on a quantum
computer in polynomial time. Here we show that effective QED, which is
equivalent to QED to second order in perturbation theory, can be simulated in
polynomial time under reasonable assumptions while properly treating all four
components of the wavefunction of the fermionic field. In particular, we
provide a detailed analysis of such simulations in position and momentum basis
using Trotter-Suzuki formulas. We find that the number of $T$-gates needed to
perform such simulations on a $3D$ lattice of $n_s$ sites scales at worst as
$O(n_s^3/\epsilon)^{1+o(1)}$ in the thermodynamic limit for position basis
simulations and $O(n_s^{4+2/3}/\epsilon)^{1+o(1)}$ in momentum basis. We also
find that qubitization scales slightly better with a worst case scaling of
$\widetilde{O}(n_s^{2+2/3}/\epsilon)$ for lattice eQED and complications in the
prepare circuit leads to a slightly worse scaling in momentum basis of
$\widetilde{O}(n_s^{5+2/3}/\epsilon)$. We further provide concrete gate counts
for simulating a relativistic version of the uniform electron gas that show
challenging problems can be simulated using fewer than $10^{13}$ non-Clifford
operations and also provide a detailed discussion of how to prepare
multi-reference configuration interaction states in effective QED which can
provide a reasonable initial guess for the ground state. Finally, we estimate
the planewave cutoffs needed to accurately simulate heavy elements such as
gold.
