TY - GEN
T1 - Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms
AU - Bansal, Nikhil
AU - Sinha, Makrand
AU - de Wolf, Ronald
N1 - Funding Nikhil Bansal: Supported in part by the NWO VICI grant 639.023.812. Makrand Sinha: Supported by a Simons-Berkeley postdoctoral fellowship. Ronald de Wolf : Partially supported by the Dutch Research Council (NWO/OCW), as part of the Quantum Software Consortium programme (project number 024.003.037), and through QuantERA ERA-NET Cofund project QuantAlgo (680-91-034).
PY - 2022/7/1
Y1 - 2022/7/1
N2 - 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.
AB - 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.
KW - Aaronson-Ambainis conjecture
KW - Analysis of Boolean functions
KW - Classical query complexity
KW - Completely bounded norm
KW - Free probability
KW - Influence
KW - Quantum query complexity
UR - http://www.scopus.com/inward/record.url?scp=85134400933&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85134400933&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CCC.2022.28
DO - 10.4230/LIPIcs.CCC.2022.28
M3 - Conference contribution
AN - SCOPUS:85134400933
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 37th Computational Complexity Conference, CCC 2022
A2 - Lovett, Shachar
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 37th Computational Complexity Conference, CCC 2022
Y2 - 20 July 2022 through 23 July 2022
ER -