  A major thrust in quantum algorithm development over the past decade has been
the search for the quantum algorithms that will deliver practical quantum
advantage first. Today's quantum computers and even early fault-tolerant
quantum computers will be limited in the number of operations they can
implement per circuit. We introduce quantum algorithms for ground state energy
estimation (GSEE) that accommodate this design constraint. The first estimates
ground state energies and has a quadratic improvement on the ground state
overlap parameter compared to other methods in this regime. The second
certifies that the estimated ground state energy is within a specified error
tolerance of the true ground state energy, addressing the issue of gap
estimation that beleaguers several ground state preparation and energy
estimation algorithms. We note, however, that the scaling of this certification
technique is, unfortunately, worse than that of the GSEE algorithm. These
algorithms are based on a novel use of the quantum computer to facilitate
rejection sampling. After a classical computer is used to draw samples, the
quantum computer is used to accept or reject the samples. The set of accepted
samples correspond to draws from a target distribution. While we use this
technique for ground state energy estimation, it may find broader application.
Our work pushes the boundaries of what operation-limited quantum computers are
capable of and thus brings the target of quantum advantage closer to the
present.
