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

Lin and Lin have recently shown how starting with a classical query algorithm(decision tree) for a function, we may find upper bounds on its quantum querycomplexity. More precisely, they have shown that given a decision tree for afunction $f:\{0,1\}^n\to[m]$ whose input can be accessed via queries to itsbits, and a guessing algorithm that predicts answers to the queries, there is aquantum query algorithm for $f$ which makes at most $O(\sqrt{GT})$ quantumqueries where $T$ is the depth of the decision tree and $G$ is the maximumnumber of mistakes of the guessing algorithm. In this paper we give a simpleproof of and generalize this result for functions $f:[\ell]^n \to [m]$ withnon-binary input as well as output alphabets. Our main tool for thisgeneralization is non-binary span program which has recently been developed fornon-binary functions, and the dual adversary bound. As applications of our mainresult we present several quantum query upper bounds, some of which are new. Inparticular, we show that topological sorting of vertices of a directed graph$\mathcal{G}$ can be done with $O(n^{3/2})$ quantum queries in the adjacencymatrix model. Also, we show that the quantum query complexity of the maximumbipartite matching is upper bounded by $O(n^{3/4}\sqrt m + n)$ in the adjacencylist model.

Quantum Speedup Based on Classical Decision Trees