One of the most widely used models to study quantum algorithms is the quantum query model. Many algorithms, ranging from Grover’s total search to Shor’s famous factoring algorithm, use the quantum query model.
We are mainly interested in the gap between the exact degree and exact block-multiliear degree of f. The exact block-multilinear degree is simply the 0-approximate block-multilinear degree. This is well-defined since f is a Boolean function, that is, we can always write f as a polynomial using indicator functions, which can then easily be converted to a blockmultilinear polynomial of larger degree. We tried separating these two degrees by using two different approaches, symmetrization and dual witness. The details can be found in Chapter 3 of the report. We also present the main results of the paper by Aaronson et. al. "Forrelation: A problem that optimally separates quantum from classical computing," in Chapter 4.