Published by the Department of Computer Science, The University of Chicago.

Abstract

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 $[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.

• The article: PDF (302 KB)
• Source material: ZIP (87 KB)
• BibTeX entry for this article (328 bytes)

Submitted June 29, 2023, revised August 23, 2024, published August 28, 2024.

© 2023 Francisco Escudero Gutiérrez
Licensed under a Creative Commons Attribution License

Volume 2024, Article 1

Volume 2024

Published articles