  Quantum span program algorithms for function evaluation sometimes have
reduced query complexity when promised that the input has a certain structure.
We design a modified span program algorithm to show these improvements persist
even without a promise ahead of time, and we extend this approach to the more
general problem of state conversion. As an application, we prove exponential
and superpolynomial quantum advantages in average query complexity for several
search problems, generalizing Montanaro's Search with Advice [Montanaro, TQC
2010].
