Quantum Advantages via Fourier Growth Analysis of Boolean Functions

Kewen Wu

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2025-39
May 1, 2025

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2025/EECS-2025-39.pdf

Intuitively quantum computations can easily aggregate signals on the Fourier basis whereas classical algorithms cannot. Raz-Tal (STOC'19, JACM'22) and Bansal-Sinha (STOC'21) formalized this using the notion of Fourier growth from Boolean function analysis. Continuing this line of work, we establish sharp Fourier growth bounds for classical (parity) query algorithms, randomized communication protocols, and parallel quantum query algorithms with limited adaptivity. As such, we obtain unconditional exponential quantum advantages in various query and communication settings.

Advisor: Avishay Tal

\"Edit"; ?>

BibTeX citation:

@phdthesis{Wu:EECS-2025-39,
    Author = {Wu, Kewen},
    Title = {Quantum Advantages via Fourier Growth Analysis of Boolean Functions},
    School = {EECS Department, University of California, Berkeley},
    Year = {2025},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2025/EECS-2025-39.html},
    Number = {UCB/EECS-2025-39},
    Abstract = {Intuitively quantum computations can easily aggregate signals on the Fourier basis whereas classical algorithms cannot. Raz-Tal (STOC'19, JACM'22) and Bansal-Sinha (STOC'21) formalized this using the notion of Fourier growth from Boolean function analysis. Continuing this line of work, we establish sharp Fourier growth bounds for classical (parity) query algorithms, randomized communication protocols, and parallel quantum query algorithms with limited adaptivity. As such, we obtain unconditional exponential quantum advantages in various query and communication settings.}
}

EndNote citation:

%0 Thesis
%A Wu, Kewen
%T Quantum Advantages via Fourier Growth Analysis of Boolean Functions
%I EECS Department, University of California, Berkeley
%D 2025
%8 May 1
%@ UCB/EECS-2025-39
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2025/EECS-2025-39.html
%F Wu:EECS-2025-39