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 study the problem of computing the Hamming weight of an $n$-bit stringmodulo $m$, for any positive integer $m \leq n$ whose only prime factors are 2and 3. We show that the exact quantum query complexity of this problem is$\left\lceil n(1 - 1/m) \right\rceil$. The upper bound is via an iterativequery algorithm whose core components are the well-known 1-query quantumalgorithm (essentially due to Deutsch) to compute the Hamming weight a 2-bitstring mod 2 (i.e., the parity of the input bits), and a new 2-query quantumalgorithm to compute the Hamming weight of a 3-bit string mod 3.  We show a matching lower bound (in fact for arbitrary moduli $m$) via avariant of the polynomial method [de Wolf, SIAM J. Comput., 32(3), 2003]. Thisbound is for the weaker task of deciding whether or not a given $n$-bit inputhas Hamming weight 0 modulo $m$, and it holds even in the strongernon-deterministic quantum query model where an algorithm must have positiveacceptance probability iff its input evaluates to 1. For $m>2$ our lower boundexceeds $n/2$, beating the best lower bound provable using the generalpolynomial method [Theorem 4.3, Beals et al., J. ACM 48(4), 2001].

Exact quantum query complexity of computing Hamming weight modulo powers of two and three