Consider the linear eigenvalue problem $$ \hat{M} f = \lambda f, $$ where $\hat{M}$ is a linear operator with eigenfunction $f$ and corresponding eigenvalue $\lambda$. The algorithmic complexity of finding an exact solution scales exponentially with some complexity metric $\epsilon$. Suppose an approximate solution is obtained through an algorithm with polynomial scaling, i.e., $\mathcal{O}(\epsilon^p)$. This algorithm involves solving the auxiliary problem $$ \tilde{\hat{M}} \tilde{f} = \tilde{\lambda} \tilde{f}, $$ where $\tilde{\hat{M}}$ is a truncated version of $\hat{M}$ or $\tilde{f}$ is a constrained ansatz.
(a) Can it be demonstrated that there is no information contained in $\tilde{f}$ alone about the accuracy of the approximation, i.e., $\lambda - \tilde{\lambda}$ cannot be estimated by a function solely dependent on the parameters of $\tilde{f}$?
(b) Is it possible to establish that any useful metric providing insights about the error will require a computational effort scaling at least as $\mathcal{O}(\epsilon^q)$ with $q>p$?
I appreciate any insights, proofs, or references that shed light on the theoretical aspects of these questions.