Skip to content
Preprint

Exact Quantum Query Complexity of the Five-Bit Symmetric Boolean Function $\Exact^5_{3,4}$

Oct 2026 · 0 citations · 28 references
Physics Computer Science

TL;DR

This paper proves that the exact quantum query complexity of f is 4, and uses the same certificate to derive a valid, though not claimed tight, lower bound on the worst-case error of every algorithm using at most three queries.

Abstract

Let \(f = \text{EXACT}^5_{3,4}\) be the Boolean function that equals 1 exactly on inputs of Hamming weight 3 or 4. Earlier numerical studies reported success probabilities close to one using three queries, but the existence of an exact three-query algorithm had remained unresolved. This paper settles this problem by proving that the exact quantum query complexity of \(f\) is \(4\). For the lower bound, we express every three-query algorithm through layer-by-layer Gram matrices of low-degree Fourier coefficients. We then construct a fixed rational dual certificate whose slack matrices are all positive definite. This certificate separates the necessary Gram-matrix region from the exact-output condition and therefore rules out every exact algorithm using at most three queries in the stated model. The positivity verification reduces to five small rational matrices and Sylvester's criterion. For the upper bound, we invoke the previously known four-query algorithm for the seven-bit function \(\text{EXACT}^7_{3,4}\) and apply the standard padding reduction. To quantify the near-exact behavior, we use the same certificate to derive a valid, though not claimed tight, lower bound \(\frac{25600}{43779488192449}>0\) on the worst-case error of every algorithm using at most three queries. This positive error gap is compatible with the near-unit success probabilities reported in earlier numerical studies, which do not establish exact computation.

View source

Similar papers

Preprint Sep 2026

Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE

A deterministic classical algorithm for the binary-error Learning-with-Errors problem, which is of independent cryptographic interest, and a full sample--time tradeoff that interpolates between exponential and polynomial runtime is established.

Robin Kothari, Tony Metger, Ryan O'Donnell et al. · 0 citations
Preprint Sep 2026

Improved Quantum Query Bounds for Boolean Matrix Product Verification

We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification ($\mathsf{BMPV}$), answering a longstanding open question in quantum query complexity. For $n\times n$ matrices, our upper bound is $\widetilde O(n^{17/12})$, improving on the standard $O(n^{3/2})$ bound o...

Amin Shiraz Gilani, François Le Gall, Xing-Yu Zhou · 0 citations
Preprint Oct 2026

A Four-by-Four Obstruction to Polynomial Removal for Ordered Binary Matrices

We exhibit a fixed $4\times 4$ binary matrix with no polynomial induced ordered removal bound. At depth $h\geq 1$, let $m=2^h$. Our explicit host has order $(14h+2)m$, exactly $2m^6+\frac{1}{2}(m-2)m^5$ induced copies, and exact editing distance $m^2$ cells. Its normalized editing distance is $\Theta(h^{-2})$, while it...

Zi-Nan Wang · 0 citations
Preprint Sep 2026

Exponential Quantum Advantage in Testing Fourier Dimensionality

This work considers the property testing task of determining whether a function has Fourier dimension at most $k, or is $\epsilon$-far from being so, and shows that there is an $O(k/\sqrt{\epsilon})$-query quantum property tester for this problem, which is shown to be almost optimal.

Kenny Chen · 0 citations
Preprint Oct 2026

Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions

We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most $k$ nonzero Fourier coefficients. We give a learner with near-optimal $\widetilde{O}(k)$ sample complexity independent of the input length $n$. The learner uses only separate measurements of individual examples. This...

Ze-Kun Ye · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.