{"id":"arxiv/2610.06835","url":"https://arxiv.org/abs/2610.06835","tags":["quant-ph","cs.CC"],"score":0,"title":"Distributional Quantum Query Complexity","domain":"quant-ph","source":"arxiv","authors":["Shalev Ben-David","M. H. Ebtehaj"],"reviews":0,"subject":"quant-ph","summary":"Quantum query complexity enjoys a variety of pleasing joint computation properties: for example, a composition theorem asserting $Q(f\\circ g)=Θ(Q(f)Q(g))$ for all Boolean functions $f$ and $g$; a direct sum theorem asserting that computing $k$ copies of a function (or search problem) costs $Ω(k)$ times as much as the cost of computing one copy; and a direct product theorem asserting that for Boolean functions, even succeeding at the direct sum problem with exponentially small probability still requires $Ω(k)$ times the cost of computing one copy to bounded error. However, all of these…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-05","reactions":{}}