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

In Exact Quantum Query model, almost all of the Boolean functions for whichnon-trivial query algorithms exist are symmetric in nature. The most well knowntechniques in this domain exploit parity decision trees, in which the parity oftwo bits can be obtained by a single query. Thus, exact quantum queryalgorithms outperforming parity decision trees are rare. In this paper we firstobtain optimal exact quantum query algorithms ($Q_{algo}(f)$) for a direct sumbased class of $\Omega \left( 2^{\frac{\sqrt{n}}{2}} \right)$ non-symmetricfunctions. We construct these algorithms by analyzing the algebraic normal formtogether with a novel untangling strategy. Next we obtain the generalizedparity decision tree complexity ($D_{\oplus}(f)$) analysing the Walsh Spectrum.Finally, we show that query complexity of $Q_{algo}$ is $\lceil \frac{3n}{4}\rceil$ whereas $D_{\oplus}(f)$ varies between $n-1$ and $\lceil \frac{3n}{4}\rceil+1$ for different classes, underlining linear separation between the twomeasures in many cases. To the best of our knowledge, this is the first familyof algorithms beyond generalized parity (and thus parity) for a large class ofnon-symmetric functions. We also implement these techniques for a larger(doubly exponential in $\frac{n}{4}$) class of Maiorana-McFarland typefunctions, but could only obtain partial results using similar algorithmictechniques.

Exact Quantum Query Algorithms Outperforming Parity -- Beyond The Symmetric functions