arXiv:2610.06835
Distributional Quantum Query Complexity
Shalev Ben-David, M. H. Ebtehaj
Abstract
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 results are strictly for worst-case quantum query complexity. For example, if we have a fixed distribution $μ$ over inputs, the direct sum theorem says nothing about the quantum query complexity of computing $k$ copies of $f$ when the input comes from the product distribution $μ^k$ instead of being worst-case. (Note that while a standard Yao-type minimax theorem guarantees a hard distribution for the direct sum problem, there's no guarantee that this hard distribution is a product distribution.) A similar problem occurs for the direct product theorem and the composition theorem: none of these results respect distributions. In this work, we give distributional joint computation lower bounds for the composition, direct sum, and direct product problems. Along the way, we introduce some new tools for handling quantum query lower bounds, including (a) a new ``multiplicative'' variant of the $γ_2$ norm (which we use in place of the multiplicative adversary method for proving the direct product theorem), and (b) a new ``Shaltiel-free'' measure of quantum query complexity, which we show characterizes the composition behavior of distributional quantum query complexity and satisfies pleasing properties.
AI Summary
The paper studies whether quantum query composition, direct-sum, and strong direct-product lower bounds remain valid for fixed input distributions. Worst-case results do not ensure hardness under the corresponding product or composed distributions. For a search relation $f$, distribution $\mu$, and success parameters $0<\beta<\alpha<1$, it proves $Q_{1-\alpha^k}^{\mu^{\otimes k}}(f^{\otimes k})\geq \frac{k(\alpha-\beta)}{10\alpha\log(2(1-\beta)/(\alpha-\beta))}Q_{1-\beta}^{\mu}(f)$. Thus, for fixed separated success parameters, achieving exponentially small all-copy success still requires $\Omega(k)$ times the single-copy distributional query complexity. This covers decision and relational search problems. For composition with a Boolean inner function $g$, it obtains $Q_\epsilon^{\mu\circ(\nu_0,\nu_1)}(f\circ g)=\Omega(\epsilon Q_{2\epsilon}^{\mu}(f)\,\mathrm{sfAdv}^{(\nu_0,\nu_1)}(g))$. The new Shaltiel-free adversary measure replaces ordinary inner-function complexity: rare, recognizable easy inputs can invalidate a naive multiplicative bound. Its dependence on the inner problem is optimal for arbitrary outer functions, as characterized through composition with the promise function distinguishing $0^n$ from $1^n$. The proofs formulate distributional computation as Gram-matrix conversion toward output witnesses, with error measured by weighted fidelity. They develop distributional filtered-$\gamma_2$ bounds, a rescaled catalyst-reuse conversion algorithm, and a multiplicative analogue based on Alberti’s fidelity formula. The resulting Alberti adversary satisfies the exact identity $\mathrm{AAdv}_{\alpha^k}^{\mu^{\otimes k}}(f^{\otimes k})=k\mathrm{AAdv}_\alpha^\mu(f)$. The guarantees retain error-parameter slack: distributional error cannot generally be amplified as in the worst-case setting. Composition does not yield a product of ordinary distributional complexities, and suggested cryptographic uses are motivations rather than demonstrated applications.
The tools were also used to assist the authors with proofreading, phrasing, clarity, and \LaTeX{} presentation.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.