  We construct quantum circuits which exactly encode the spectra of correlated
electron models up to errors from rotation synthesis. By invoking these
circuits as oracles within the recently introduced "qubitization" framework,
one can use quantum phase estimation to sample states in the Hamiltonian
eigenbasis with optimal query complexity $O(\lambda / \epsilon)$ where
$\lambda$ is an absolute sum of Hamiltonian coefficients and $\epsilon$ is
target precision. For both the Hubbard model and electronic structure
Hamiltonian in a second quantized basis diagonalizing the Coulomb operator, our
circuits have T gate complexity $O({N + \log (1/\epsilon}))$ where $N$ is
number of orbitals in the basis. This enables sampling in the eigenbasis of
electronic structure Hamiltonians with T complexity $O(N^3 /\epsilon + N^2
\log(1/\epsilon)/\epsilon)$. Compared to prior approaches, our algorithms are
asymptotically more efficient in gate complexity and require fewer T gates near
the classically intractable regime. Compiling to surface code fault-tolerant
gates and assuming per gate error rates of one part in a thousand reveals that
one can error correct phase estimation on interesting instances of these
problems beyond the current capabilities of classical methods using only about
a million superconducting qubits in a matter of hours.
