Certificate complexity reveals limits of exact zero error quantum queries
Certification complexity of Boolean functions
Computational Complexity
Summary
The paper studies how to measure the 'certificate complexity' of Boolean functions, which means finding the smallest number of input bits needed to confirm the function's output. The authors focus on quantum query models, especially those requiring zero-error or exact answers, where traditional certificate notions are unclear. They develop new ways to understand certification in these quantum models and show how this can give better lower bounds on their complexity. Their work provides a specific example where these new bounds are tight, even when other measures suggest simpler solutions.
What this means in practice
- •For quantum algorithm designers: Identify fundamental limits for zero-error quantum query algorithms to guide realistic algorithm design.
- •For compiler developers for quantum hardware: Use new lower bound methods to optimize quantum query strategies ensuring exact computations where needed.
A theory result. No direct application yet.
Authors
Chandrima Kayal, Sophie Laplante, Émile Larroque, Krišjānis Prūsis, Jevgēnijs Vihrovs
Abstract
Certificate complexity $(C(f ))$ is a fundamental measure of complexity of Boolean functions f which counts the number of bits of an input that need to be known in order for the value of the function to be determined. A certificate can be viewed as a partial assignment, or a boolean subcube where the function is constant. Certificate complexity is well understood for deterministic query (or decision tree) complexity $(D)$ and other query models such as bounded-error randomized and quantum complexity $(R, Q)$, but not as well for quantum zero-error $(Q_0)$ and exact query complexity $(Q_E)$, where there is no agreed-upon certificate 'object' (even for $Q$). Instead, we study an operational notion of certification and apply it to various query-based models, with a focus on zero-error and exact quantum query complexity, but also on polynomial degree measures. We give new characterizations of $C, RC$ (randomized certificate complexity) and $QC$ (quantum certificate complexity), in terms of various measures such as classical and quantum sabotage complexity, unambiguous certificate complexity, and variants of polynomial degree. Certification complexity also gives rise to new lower bounds on $Q_E$ and $Q_0$, the quantum analogues of $D$ and $R_0$, complexity measures for which few lower bound techniques are known which are not already lower bounds for two-sided error quantum query complexity. We exhibit a total Boolean function for which our certification complexity measure gives a tight lower bound for $Q_0$, but rational degree and $Q$ are asymptotically smaller.