Distributional quantum query complexity advances understandings of problem costs
Distributional Quantum Query Complexity
Computational Complexity
Summary
Quantum computers measure how hard problems are based on how many times they need to check data, but usually only in the worst case. This paper looks at what happens when the inputs follow a specific random pattern instead. The authors find new ways to understand the difficulty of solving multiple problems together when inputs are distributed in this way. They introduce new mathematical tools to better capture how quantum computers work with these input patterns.
What this means in practice
- •For quantum algorithm designers: Determine cost lower bounds for quantum algorithms when inputs follow specific distributions rather than worst-case inputs.
- •For quantum hardware developers: Understand resource requirements for running multiple quantum query tasks under realistic input distributions to guide hardware specifications.
A theory result. No direct application yet.
Authors
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.