NAND-Trees, Average Choice Complexity, and Effective Resistance

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. [Zhan et al., ITCS 2012, 249-265]. 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 widetilde{O}\(N^1/4sqrt{{cal C}(x\)}) quantum queries against a random opponent, where {cal C }(x) is the average choice complexity of the instance. This gives an improvement over the query complexity of the naive strategy, which costs widetilde{O}\(sqrt{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.