NAND-Trees, Average Choice Complexity, and Effective Resistance

Abstract

We show that the quantum query complexity of evaluating nand-tree instances with average choice complexity at most W is O(W), where average choice complexity is a measure of the difficulty of winning the associated two-player game. This generalizes a superpolynomial speedup over classical query complexity due to Zhan et al. We further show that the player with a winning strategy for the two-player game associated with the nand-tree can win the game with an expected Õ(N^(1/4) √C(x)) quantum queries against a random opponent, where C(x) is the average choice complexity of the instance. This gives an improvement over the query complexity of the naive strategy, which costs Õ(√N) queries. The results rely on a connection between nand-tree evaluation and st-connectivity problems on certain graphs, and span programs for st-connectivity problems. Our results follow from relating average choice complexity to the effective resistance of these graphs, which itself corresponds to the span program witness size.