  Motivated by limitations on the depth of near-term quantum devices, we study
the depth-computation trade-off in the query model, where the depth corresponds
to the number of adaptive query rounds and the computation per layer
corresponds to the number of parallel queries per round. We achieve the
strongest known separation between quantum algorithms with $r$ versus $r-1$
rounds of adaptivity. We do so by using the $k$-fold Forrelation problem
introduced by Aaronson and Ambainis (SICOMP'18). For $k=2r$, this problem can
be solved using an $r$ round quantum algorithm with only one query per round,
yet we show that any $r-1$ round quantum algorithm needs an exponential (in the
number of qubits) number of parallel queries per round.
  Our results are proven following the Fourier analytic machinery developed in
recent works on quantum-classical separations. The key new component in our
result are bounds on the Fourier weights of quantum query algorithms with
bounded number of rounds of adaptivity. These may be of independent interest as
they distinguish the polynomials that arise from such algorithms from arbitrary
bounded polynomials of the same degree.
