Abstract

It is well known that quantum, randomized and deterministic (sequential) query complexities are polynomially related for total boolean functions. We find that significantly larger separations between the parallel generalizations of these measures are possible. In particular,
(1) We employ the cheatsheet framework to obtain an unbounded parallel quantum query advantage over its randomized analogue for a total function, falsifying a conjecture of Jeffery et al. 2017 (arXiv:1309.6116).
(2) We strengthen (1) by constructing a total function which exhibits an unbounded parallel quantum query advantage despite having no sequential advantage, suggesting that genuine quantum advantage could occur entirely due to parallelism.
(3) We construct a total function that exhibits a polynomial separation between 2-round quantum and randomized query complexities, contrasting a result of Montanaro in 2010 (arXiv:1001.0018) that there is at most a constant separation for 1-round (nonadaptive) algorithms.
(4) We develop a new technique for deriving parallel quantum lower bounds from sequential upper bounds. We employ this technique to give lower bounds for Boolean symmetric functions and read-once formulas, ruling out large parallel query advantages for them.
We also provide separations between randomized and deterministic parallel query complexities analogous to items (1)-(3).

Publication Details
Publication Type
Journal Article
Year of Publication
2025
Volume
Volume 325
Issue
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
DOI
https://doi.org/10.4230/LIPIcs.ITCS.2025.31
URL
https://arxiv.org/abs/2410.02665
Journal
In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs)
Contributors
Groups
Start Page
pp. 31:1-31:14
Date Published
02/2025