English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We show that the quantum query complexity of evaluating NAND-tree instanceswith average choice complexity at most $W$ is $O(W)$, where average choicecomplexity is a measure of the difficulty of winning the associated two-playergame. This generalizes a superpolynomial speedup over classical querycomplexity due to Zhan et al. [Zhan et al., ITCS 2012, 249-265]. We furthershow that the player with a winning strategy for the two-player game associatedwith the NAND-tree can win the game with an expected$\widetilde{O}(N^{1/4}\sqrt{{\cal C}(x)})$ quantum queries against a randomopponent, where ${\cal C }(x)$ is the average choice complexity of theinstance. This gives an improvement over the query complexity of the naivestrategy, 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 choicecomplexity to the effective resistance of these graphs, which itselfcorresponds to the span program witness size.

NAND-Trees, Average Choice Complexity, and Effective Resistance