  In this work we investigate a binned version of Quantum Phase Estimation
(QPE) set out by [Somma 2019] and known as the Quantum Eigenvalue Estimation
Problem (QEEP). Specifically, we determine whether the circuit decomposition
techniques we set out in previous work, [Clinton et al 2020], can improve the
performance of QEEP in the NISQ regime. To this end we adopt a physically
motivated abstraction of NISQ device capabilities as in [Clinton et al 2020].
Within this framework, we find that our techniques reduce the threshold at
which it becomes possible to perform the minimum two-bin instance of this
algorithm by an order of magnitude. This is for the specific example of a two
dimensional spin Fermi-Hubbard model. For example, given a $10\%$ acceptable
error on a $3\times 3$ spin Fermi-Hubbard model, with a depolarizing noise rate
of $10^{-6}$, we find that the phase estimation protocol of [Somma 2019] could
be performed with a bin width of approximately $1/9$ the total spectral range
at the circuit depth where traditional gate synthesis methods would yield a bin
width that covers the entire spectral range. We explore possible modifications
to this protocol and propose an application, which we call Randomized Quantum
Eigenvalue Estimation Problem (rQeep). rQeep outputs estimates on the fraction
of eigenvalues which lie within randomly chosen bins and upper bounds the total
deviation of these estimates from the true values. One use case we envision for
this algorithm is resolving density of states features of local Hamiltonians,
such as spectral gaps.
