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 Aaronson-Ambainis conjecture (Theory of Computing '14) says that everylow-degree bounded polynomial on the Boolean hypercube has an influentialvariable. This conjecture, if true, would imply that the acceptance probabilityof every $d$-query quantum algorithm can be well-approximated almost everywhere(i.e., on almost all inputs) by a $\mathrm{poly}(d)$-query classical algorithm.We prove a special case of the conjecture: in every completely boundeddegree-$d$ block-multilinear form with constant variance, there always exists avariable with influence at least $1/\mathrm{poly}(d)$. In a certain sense, suchpolynomials characterize the acceptance probability of quantum queryalgorithms, as shown by Arunachalam, Bri\"et and Palazuelos (SICOMP '19). As acorollary we obtain efficient classical almost-everywhere simulation for aparticular class of quantum algorithms that includes for instance $k$-foldForrelation. Our main technical result relies on connections to freeprobability theory.

Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms