2023-06-28
Influences of fourier completely bounded polynomials and classical simulation of quantum algorithms
Publication
Publication
We give a new presentation of the main result of Arunachalam, Briët and Palazuelos (SICOMP'19) and show that quantum query algorithms are characterized by a new class of polynomials which we call Fourier completely bounded polynomials. We conjecture that all such polynomials have an influential variable. This conjecture is weaker than the famous Aaronson-Ambainis (AA) conjecture (Theory of Computing'14), but has the same implications for classical simulation of quantum query algorithms. We prove a new case of the AA conjecture by showing that it holds for homogeneous Fourier completely bounded polynomials. This implies that if the output of d-query quantum algorithm is a homogeneous polynomial p of degree 2d, then it has a variable with influence at least Var[p]2. In addition, we give an alternative proof of the results of Bansal, Sinha and de Wolf (CCC'22 and QIP'23) showing that block-multilinear completely bounded polynomials have influential variables. Our proof is simpler, obtains better constants and does not use randomness.
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.48550/arXiv.2304.06713 | |
| Networks , Marie Skłodowska-Curie | |
| Organisation | Algorithms and Complexity |
|
Escudero Gutiérrez, F. (2023). Influences of fourier completely bounded polynomials and classical simulation of quantum algorithms. doi:10.48550/arXiv.2304.06713 |
|
