A Caltech Library Service

Optimal Parallel Quantum Query Algorithms

Jeffery, Stacey and Magniez, Frederic and de Wolf, Ronald (2017) Optimal Parallel Quantum Query Algorithms. Algorithmica, 79 (2). pp. 509-529. ISSN 0178-4617.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We study the complexity of quantum query algorithms that make p queries in parallel in each timestep. We show tight bounds for a number of problems, specifically Θ((n/p)2/3) p-parallel queries for element distinctness and Θ((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.

Item Type:Article
Related URLs:
URLURL TypeDescription ReadCube access
Additional Information:© 2016 Springer. Received: 20 February 2015. Accepted: 24 August 2016. Published online: 8 September 2016. We thank Jérémie Roland for helpful discussions. Partially supported by the French ANR Blanc project ANR-12-BS02-005 (RDAM), a Vidi grant from the Netherlands Organization for Scientific Research (NWO), ERC Consolidator grant QPROGRESS, the European Commission IST STREP projects Quantum Computer Science (QCS) 255961, Quantum Algorithms (QALGO) 600700, and the US ARO. An extended abstract of this paper appeared in the Proceedings of the 22nd European Symposium on Algorithms (ESA’14), pp. 592–604.
Funding AgencyGrant Number
Agence Nationale pour la Recherche (ANR)ANR-12-BS02-005 (RDAM
European Research Council (ERC)QPROGRESS
European CommissionIST STREP
European Research Council (ERC)(QCS) 255961
European Research Council (ERC)(QALGO) 600700
Army Research Office (ARO)UNSPECIFIED
Record Number:CaltechAUTHORS:20170825-092340784
Persistent URL:
Official Citation:Jeffery, S., Magniez, F. & de Wolf, R. Algorithmica (2017) 79: 509.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:80792
Deposited By: Ruth Sustaita
Deposited On:28 Aug 2017 19:54
Last Modified:28 Aug 2017 19:54

Repository Staff Only: item control page