A Caltech Library Service

NAND-Trees, Average Choice Complexity, and Effective Resistance

Jeffery, Stacey and Kimmel, Shelby (2015) NAND-Trees, Average Choice Complexity, and Effective Resistance. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Additional Information:Submitted on 6 Nov 2015. The authors would like to thank Ashley Montanaro for helpful discussions. S.J. gratefully acknowledges funding provided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NFS Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). S.K. acknowledges funds provided by the Department of Defense.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
NSF Physics Frontiers CenterPHY-1125565
Gordon and Betty Moore FoundationGBMF-12500028
Department of DefenseUNSPECIFIED
Record Number:CaltechAUTHORS:20160602-065519464
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:67560
Deposited By: Ruth Sustaita
Deposited On:02 Jun 2016 19:01
Last Modified:02 Jun 2023 00:24

Repository Staff Only: item control page