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 present a trichotomy theorem for the quantum query complexity of regularlanguages. Every regular language has quantum query complexity Theta(1),~Theta(sqrt n), or Theta(n). The extreme uniformity of regular languagesprevents them from taking any other asymptotic complexity. This is in contrastto even the context-free languages, which we show can have query complexityTheta(n^c) for all computable c in [1/2,1]. Our result implies an equivalenttrichotomy for the approximate degree of regular languages, and adichotomy---either Theta(1) or Theta(n)---for sensitivity, block sensitivity,certificate complexity, deterministic query complexity, and randomized querycomplexity.  The heart of the classification theorem is an explicit quantum algorithmwhich decides membership in any star-free language in ~O(sqrt n) time. Thiswell-studied family of the regular languages admits many interestingcharacterizations, for instance, as those languages expressible as sentences infirst-order logic over the natural numbers with the less-than relation.Therefore, not only do the star-free languages capture functions such as OR,they can also express functions such as "there exist a pair of 2's such thateverything between them is a 0."  Thus, we view the algorithm for star-free languages as a nontrivialgeneralization of Grover's algorithm which extends the quantum quadraticspeedup to a much wider range of string-processing algorithms than waspreviously known. We show a variety of applications---new quantum algorithmsfor dynamic constant-depth Boolean formulas, balanced parentheses nestedconstantly many levels deep, binary addition, a restricted word break problem,and path-discovery in narrow grids---all obtained as immediate consequences ofour classification theorem.

A Quantum Query Complexity Trichotomy for Regular Languages