Improved Quantum Query Upper Bounds Based on Classical Decision Trees

Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro

Given a classical query algorithm as a decision tree, when does there exist a quantum query algorithm with a speed-up over the classical one? We provide a general construction base…