Optimal parallel quantum query algorithms
arXiv:1309.6116
Abstract
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.
arXiv comment19 pages LaTeX
References in corpus (12)
- Quantum Algorithms Revisited
- Grover's quantum searching algorithm is optimal
- Search via Quantum Walk
- Negative weights make adversaries stronger
- A Limit on the Speed of Quantum Computation in Determining Parity
- Quantum query complexity of state conversion
- An introduction to measurement based quantum computation
- Fast parallel circuits for the quantum Fourier transform
- Quantum Algorithm for k-distinctness with Prior Knowledge on the Input
- Sharp Quantum vs. Classical Query Complexity Separations
- Quantum search for multiple items using parallel queries
- Optimal quantum query bounds for almost all Boolean functions