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 achieve essentially the largest possible separation between quantum andclassical query complexities. We do so using a property-testing problem calledForrelation, where one needs to decide whether one Boolean function is highlycorrelated with the Fourier transform of a second function. This problem can besolved using 1 quantum query, yet we show that any randomized algorithm needs~sqrt(N)/log(N) queries (improving an ~N^{1/4} lower bound of Aaronson).Conversely, we show that this 1 versus ~sqrt(N) separation is optimal: indeed,any t-query quantum algorithm whatsoever can be simulated by anO(N^{1-1/2t})-query randomized algorithm. Thus, resolving an open question ofBuhrman et al. from 2002, there is no partial Boolean function whose quantumquery complexity is constant and whose randomized query complexity is linear.We conjecture that a natural generalization of Forrelation achieves the optimalt versus ~N^{1-1/2t} separation for all t. As a bonus, we show that thisgeneralization is BQP-complete. This yields what's arguably the simplestBQP-complete problem yet known, and gives a second sense in which Forrelation"captures the maximum power of quantum computation."

Forrelation: A Problem that Optimally Separates Quantum from Classical Computing