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

The query model has generated considerable interest in both classical andquantum computing communities. Typically, quantum advantages are demonstratedby showcasing a quantum algorithm with a better query complexity compared toits classical counterpart. Exact quantum query algorithms play a pivotal rolein developing quantum algorithms. For example, the Deutsch-Jozsa algorithmdemonstrated exponential quantum advantages over classical deterministicalgorithms. As an important complexity measure, exact quantum query complexitydescribes the minimum number of queries required to solve a specific problemexactly using a quantum algorithm.  In this paper, we consider the exact quantum query complexity of thefollowing two $n$-bit symmetric functions $\text{MOD}_m^n:\{0,1\}^n \rightarrow\{0,...,m-1\}$ and $\text{EXACT}_{k,l}^n:\{0,1\}^n \rightarrow \{0,1\}$, whichare defined as $\text{MOD}_m^n(x) = |x| \bmod m$ and $ \text{EXACT}_{k,l}^n(x)= 1$ iff $|x| \in \{k,l\}$, where $|x|$ is the number of $1$'s in $x$. Ourresults are as follows: i) We present an optimal quantum algorithm forcomputing $\text{MOD}_m^n$, achieving a query complexity of $\lceiln(1-\frac{1}{m}) \rceil$ for $1 < m \le n$. This settles a conjecture proposedby Cornelissen, Mande, Ozols and de Wolf (2021). Based on this algorithm, weshow the exact quantum query complexity of a broad class of symmetric functionsthat map $\{0,1\}^n$ to a finite set $X$ is less than $n$. ii) When $l-k \ge2$, we give an optimal exact quantum query algorithm to compute$\text{EXACT}_{k,l}^n$ for the case $k=0$ or $k=1,l=n-1$. This resolves theconjecture proposed by Ambainis, Iraids and Nagaj (2017) partially.

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$