Quantum computing is a promising new computational paradigm which may allow one to address exponentially hard problems inaccessible in Euclidean lattice QCD. Those include real-time dynamics, matter at non-zero baryon density, field theories with non-trivial CP-violating terms and can often be traced to the sign problem that makes stochastic sampling methods inapplicable. As a prototypical example we consider a low-dimensional theory, Quantum Electrodynamics in 1+1 space-time dimensions with a theta term. Using staggered fermions, this model can be mapped to a quantum Ising-like model with nearest-neighbor interactions which is well-suited for digital gate-based quantum computers. We study and compare properties of three algorithms that can be employed for the initial state preparations: Quantum Adiabatic Evolution (QAE), Quantum Approximate Optimization Algorithm (QAOA) as well as recently proposed Rodeo Algorithm. Understanding their convergence properties may be helpful for designing optimal algorithms with minimal number of CNOT gates for near-term noisy intermediate scale quantum (NISQ) devices that are currently within technological reach.