Post

Teaser: coming soon to an #arXiv near you! (my coauthors did not change the title in time)

@ccanonne.github.io

Given that the object of study ("Forrelation") is already a pun/portmanteau, I think a little bit of levity in the title is absolutely fair game.

Nalini Joshi

@monsoon0.bsky.social

7 Feb

But what is “forrelation”?

Clément Canonne

@ccanonne.github.io

It's an (artificial) task that was introduced to show a quantum advantage over classical: given as input oracle access to two boolean functions f,g: {0,1}^n→{0,1} with the promise that the correlation <f,^g> is either <-ε or >ε (^g being the Fourier transform or g), one must decide which case holds.

7/2/26, 9:13 pm0 reposts1 like

Clément Canonne

@ccanonne.github.io

7 Feb

(Forrelation=correlation+Fourier transform) This can be solved with 1 quantum query to the oracles for f,g, but classically exponentially many queries (in n) are known to be necessary for most values of ε... Only the extremal case (eps=1, "as (anti)correlated as possible" was not fully understood.