Leveraging Unknown Structure in Quantum Query Algorithms

Noel T. Anderson, Jay-U Chung, Shelby Kimmel

Quantum span program algorithms for function evaluation commonly have reduced query complexity when promised that the input has a certain structure. We design a modified span progr…