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.

, , , , , ,
Leibniz International Proceedings in Informatics
37th Computational Complexity Conference, CCC 2022

Bansal, N, Sinha, M, & de Wolf, R.M. (2022). Influence in completely bounded block-multilinear forms and classical simulation of quantum algorithms. In Computational Complexity Conference (pp. 28:1–28:21). doi:10.4230/LIPIcs.CCC.2022.28