2026-07-22T21:50:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16590 2024-03-06T10:57:52Z ddc:004 open_access

Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms Bansal, Nikhil Sinha, Makrand de Wolf, Ronald Aaronson-Ambainis conjecture Quantum query complexity Classical query complexity Free probability Completely bounded norm Analysis of Boolean functions Influence The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if true, would imply that the acceptance probability of every d-query quantum algorithm can be well-approximated almost everywhere (i.e., on almost all inputs) by a poly(d)-query classical algorithm. We prove a special case of the conjecture: in every completely bounded degree-d block-multilinear form with constant variance, there always exists a variable with influence at least 1/poly(d). In a certain sense, such polynomials characterize the acceptance probability of quantum query algorithms, as shown by Arunachalam, Briët and Palazuelos (SICOMP '19). As a corollary we obtain efficient classical almost-everywhere simulation for a particular class of quantum algorithms that includes for instance k-fold Forrelation. Our main technical result relies on connections to free probability theory. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikhil Bansal and Makrand Sinha and Ronald de Wolf 2022 Is Part Of LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2022.28 urn:nbn:de:0030-drops-165908 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.28 eng https://creativecommons.org/licenses/by/4.0/legalcode