It is not possible, using standard lattice techniques in Euclidean space, to calculate the complete fermionic spectrum of a quantum field theory. Algorithms running on quantum computers have the potential to access the theory with real-time evolution, enabling a direct computation. As a testing ground we consider the 1+1-dimensional Schwinger model with the presence of a $\theta$ term using a staggered fermions discretization. We study the convergence properties of two different algorithms -adiabatic evolution and the Quantum Approximate Optimization Algorithm- with an emphasis on their cost in terms of CNOT gates. This is crucial to understand the feasibility of these algorithms, because calculations on near-term quantum devices depend on their rapid convergence. We also propose a blocked algorithm that has the first indications of a better scaling behavior with the dimensionality of the problem.