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].

翻译：功能评估的量子程序算法有时在承诺投入有一定结构时降低了查询的复杂性。 我们设计了一个经过修改的跨度程序算法,以显示这些改进即使没有预期的希望,也会持续下去。 我们将此方法推广到更普遍的状态转换问题。 作为一种应用,我们证明对于几个搜索问题来说,平均查询复杂性具有指数化和超超极量量子优势,将Montanaro的搜索与建议(Montanaro, TQC 2010)相提并论。</s>