Improved Quantum Query Upper Bounds Based on Classical Decision Trees

Speaker

Nikhil Mande October 30, 2022.

Abstract

In the first part of this talk we will discuss the notion of rank of decision trees, which is essentially the largest depth of a complete subtree embedded in the initial tree. We observe the equivalence of rank and “guessing complexity,” a measure of decision trees used by Lin and Lin [Theory of Computing’16] and Beigi and Taghavi [Quantum’20] to give upper bounds on quantum query complexity of functions based on classical query algorithms for them. In the second part of the talk we will first note that the best speed-up obtainable using the approach of Beigi and Taghavi is captured by a polynomial optimization program on assignments of real weights to edges of the underlying classical decision tree. We then give a recursive expression for the optimal solution to this program and bound the optimum from above in terms of natural measures of the decision tree.

Based on joint work with Arjan Cornelissen and Subhasree Patro (https://arxiv.org/abs/2203.02968)