  We study the complexity of quantum query algorithms that make p queries in
parallel in each timestep. This model is in part motivated by the fact that
decoherence times of qubits are typically small, so it makes sense to
parallelize quantum algorithms as much as possible. We show tight bounds for a
number of problems, specifically Theta((n/p)^{2/3}) p-parallel queries for
element distinctness and Theta((n/p)^{k/(k+1)} for k-sum. Our upper bounds are
obtained by parallelized quantum walk algorithms, and our lower bounds are
based on a relatively small modification of the adversary lower bound method,
combined with recent results of Belovs et al. on learning graphs. We also prove
some general bounds, in particular that quantum and classical p-parallel
complexity are polynomially related for all total functions f when p is small
compared to f's block sensitivity.
