A Near-Quartic Separation Between Certificate Complexity and Quantum Query Complexity

• URL: http://arxiv.org/abs/2609.11664v1
• Date: Thu, 10 Sep 2026 15:04:28 GMT
• Title: A Near-Quartic Separation Between Certificate Complexity and Quantum Query Complexity
• Abstract summary: We construct a total Boolean function $f$ for which $Q(f) = widetildeO(sqrt[4]C(f))$, where $Q(f)$ denotes the bounded-error quantum query complexity and $C(f)$ denotes the certificate complexity.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We construct a total Boolean function $f$ for which $Q(f) = \widetilde{O}(\sqrt[4]{C(f)})$, where $Q(f)$ denotes the bounded-error quantum query complexity and $C(f)$ denotes the certificate complexity. This resolves a longstanding open question and is tight up to logarithmic factors.

Related papers

• Randomized query complexity can beat certificate complexity [1.7889544416325804]
  We construct a function with R(f) = O(sqrtC(f)), which is optimal up to log factors.<n>The same function also has $Q(f) = O(C(f)1/4), where Q(f) is the bounded-error quantum query complexity of f.
  arXiv  Detail & Related papers  (2026-09-14T05:29:42Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  We present two quantum algorithms that produce the normalized solution $|xrangle$ of linear system $Ax=| b rangle$ to accuracy $$ with complexity independent of the condition number $=lVert A-1rVert$.<n>Our filtering-based solver is extremely simple with a favorable runtime prefactor.
  arXiv  Detail & Related papers  (2026-07-08T17:49:40Z)
• Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry [0.0]
  For general max-k-XORSAT with $k geq 3$, no-time algorithm can do substantially better than random guessing on worst-case instances.<n>We make this connection explicit and extend the hardness to max-E$k$-LINSAT$(q,r)$ with bounded degree $D$ and over arbitrary finite fields.
  arXiv  Detail & Related papers  (2026-06-11T16:59:12Z)
• DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians [20.990700912031773]
  We study the computational complexity of estimating the normalized trace $2-nTr[f(A)]$ for a log-local Hamiltonian $A$ acting on $n$ qubits.<n>This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions $f(x)$.<n>We show that if $f(x)$ is a continuous function with approximate degree $(rm poly(n))$, then estimating $2-nTr[f(A)]$ up to constant additive error is
  arXiv  Detail & Related papers  (2026-04-02T01:15:12Z)
• Quantum State-Aware Query Complexity: Krylov Compression and Polynomial Query Duality [0.0]
  This state-aware perspective refines the worst-case bounds, Krylov/Favard approximation with quantum queries, and explains how state-dependent spectral structure can yield substantial savings over uniform designs.
  arXiv  Detail & Related papers  (2025-10-13T18:00:03Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known.<n>Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language [0.0]
  We present a quantum property testing algorithm for recognizing a context-free language that is a concatenation of two palindromes $L_REV$.
  arXiv  Detail & Related papers  (2024-06-17T07:19:20Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• Quantum divide and conquer [6.527258283771695]
  Divide-and-conquer framework is used extensively in classical algorithm design. We describe a quantum divide-and-conquer framework that, in certain cases, yields an analogous recurrence relation $$C_Q(n) leq sqrta, C_Q(n/b) + O(Ctextrmaux_Q(n))$$ that characterizes the quantum query complexity.
  arXiv  Detail & Related papers  (2022-10-12T17:14:28Z)
• Multidimensional Quantum Walks, with Application to $k$-Distinctness [0.5064404027153093]
  We give a new upper bound of $widetildeOleft(n3/4-1/4(2k-1)right)$ on the time complexity.<n>We show how to solve the welded trees problem in $O(n)$ queries and $O(n2)$ time using this new technique.
  arXiv  Detail & Related papers  (2022-08-29T10:51:56Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
  We study the computational complexity of adversarially robust proper learning of halfspaces in the distribution-independent PAC model. We give a computationally efficient learning algorithm and a nearly matching computational hardness result for this problem.
  arXiv  Detail & Related papers  (2020-07-30T04:18:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.