Improved Quantum Query Upper Bounds Based on Classical Decision Trees


Nikhil Mande October 30, 2022.


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 (

Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • List Decoding of near optimal binary codes at Johnson Bound
  • Are quantum speedups for learning expressive classes possible?
  • Hardness Condensation and Log Approximate Rank Conjecture
  • Quantum Divide and Conquer
  • On Probabilistic Approximations of Boolean Functions via Polynomials, and Polynomial Closure Statements over the Boolean Cube