REVIEW
Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions
Quantum Physics · Submitted 6 Nov 2026 · 14 references
Pith's verdict: A dense, apparently sound theory paper that resolves a real open question: explicit symmetric functions need more than n/2 quantum queries, with matching n/2+O(n^{1/3}) Hamming-weight recovery.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
An explicit family of symmetric Boolean functions forces n/2 + Ω(n^(1/3)) quantum queries, and exact Hamming weight recovery matches the bound.
The reading
What carries the argument
Two mechanisms carry the argument. Upper bound: a quantum walk on matchings. A one-query parity sampler (imported from exact symmetric-function algorithms) turns a phase query on the unpaired coordinates into a superposition of unequal pairs, and a reversible edge-insertion merges a sampled pair into a matching; assembling these steps gives a walk $W$ that, per query, shifts amplitude from size-$j$ to size-$(j+1)$ matchings with speed $\beta_j=\sqrt{1-(b/(n-2j))^2}$, where $b=n_0-n_1$ is the input's signed bias and stays invariant as unequal pairs are removed. The analysis couples this discrete walk to the continuous transport equation $\partial_t f=-\beta\,\partial_x f-\tfrac12\beta' f$; a hybrid argument in Section 4.4.5 bounds the accumulated norm error by $O(1/L^2+\log n/(L n^{1/3}))$, which forces the measured matching to leave only $O(n^{1/3})$ minority bits, finished by an exact sparse-counting subroutine. The walk stops before the boundary $j=w$, and a stopping-time estimate converts the walk speed into the query budget $t_0=\tfrac12\sqrt{(n-6\ell)^2-D^2}$, whose saving $D^2/4n$ pays for the finishing step. Lower bound: a sum-of-squares witness. The signed weights $\lambda(x)=u_g(|x|-m)$ are built from a rational function $h_g(k)=(-1)^{g+k}/\Delta(k+\tfrac12)$ whose $2g+1$ half-integer poles sit at quadratically spaced positions $\rho-\tfrac12$ with $R=\Theta(g^2)$; the residue theorem turns the required Hamming-layer sums into explicit nonnegative quadratic forms in the values $q(\rho-\tfrac12)$, central negative weights are clipped to zero to cover windows shorter than $R$, and Lemma 5.7 shows the negative mass fraction stays constant for $m\ge 512g^3$. Each extra query degree forces two extra poles, which is why the achievable gap is $g=\Theta(m^{1/3})$ and the hard function's central zero block is $\Theta(m^{2/3})$ layers wide.
Extended reading notes
Core claim
On the paper's own terms the central claim is a matching pair of theorems. Theorem 4.1: for every fixed error $\varepsilon>0$ there is a quantum query algorithm that, on every input $x$, outputs the exact Hamming weight $|x|$ with probability at least $1-\varepsilon$ using at most $n/2+C_\varepsilon n^{1/3}+B_\varepsilon$ queries; since every symmetric Boolean function depends only on $|x|$, the same algorithm computes all of them within the same bound. Theorem 5.2: there is an absolute constant $0<\varepsilon_0<1/2$ and an explicit symmetric total function $F_{2m}=F_{m,g_m}$ with $g_m=\lfloor(m/512)^{1/3}\rfloor$, whose value is 1 exactly on the layers where $j=\max\{k,-k-1\}$ for $k=|x|-m$ satisfies $j\ge R+1$ and $j-R$ is odd, with $R=\Theta(m^{2/3})$, such that $Q_{\varepsilon_0}(F_{2m})\ge m+g_m+1=n/2+\Omega(n^{1/3})$ for all sufficiently large $m$. Combining them gives Theorem 1.4: at any fixed error $\varepsilon\le\varepsilon_0$, recovering $|x|$ has worst-case query complexity $n/2+\Theta(n^{1/3})$, so the optimal additive order beyond $n/2$ for Hamming weight recovery and for the worst case over symmetric functions is exactly $n^{1/3}$. The lower bound already bites at the first rung: for the $R=0$ member $H_{2m}(x)=\mathrm{PARITY}(x)\oplus\mathbf{1}[|x|\ge m]$, every algorithm using at most $m$ queries has worst-case success probability at most $1/2+O(1/\log m)$.
Load-bearing premise
Everything in the upper bound hangs on one step: the paper's own hybrid calculation in Section 4.4.5, which replaces the discrete walk by the continuous flow $\partial_t f=-\beta\,\partial_x f-\tfrac12\beta' f$ and claims an accumulated error of only $O(1/L^2+\log n/(L n^{1/3}))$; if that approximation breaks — a scenario the proof rules out only through its own derivative and boundary-distance estimates — the walk could stop far short of a near-maximum matching and the $n/2+O(n^{1/3})$ algorithm would collapse.
Editorial extensions
If this is right
- Exact Hamming weight, and with it every symmetric Boolean function, is computable in $n/2+O(n^{1/3})$ queries at any fixed constant error; thresholds, majority, and exact-count profiles all inherit the same bound.
- The explicit family $F_{2m}$ shows the $n/2$ threshold is provably breakable: some symmetric functions genuinely need $n/2+\Omega(n^{1/3})$ worst-case queries at constant error, settling the open existence question affirmatively.
- The two theorems together pin the worst-case cost of Hamming weight recovery at $n/2+\Theta(n^{1/3})$ for error $\varepsilon\le\varepsilon_0$, the first tight additive characterization of this natural task in the constant-error regime.
- Already at $R=0$, parity with a central threshold requires $m+1$ queries on $2m$ bits, and every $m$-query algorithm for it has success probability at most $1/2+O(1/\log m)$.
- For general, not necessarily symmetric, Boolean functions the additive gap between the $\Omega(n^{1/3})$ lower bound and the $O(\sqrt n)$ upper bound remains open; the authors observe that a function attaining $\Omega(\sqrt n)$ would have to be nonsymmetric.
Reading between the lines
- Because the walk analysis never uses the output profile, the same $n/2+O(n^{1/3})$ algorithm computes any function of the Hamming weight; a testable relaxation is to estimate $|x|$ only within a tolerance $t(n)$, expecting the overhead to shrink from $\Theta(n^{1/3})$ toward something smaller and revealing whether the cube root is tied to exact recovery or to the walk's residual bound.
- The quadratic pole spacing is the fine detail that makes the lower bound's mass estimate work, since the residue decay compensates the binomial coefficient growth; the same spacing idea may transfer to other counting problems proved by sum-of-squares witnesses, and a cheap test is whether linear spacing destroys the constant negative-mass fraction.
- For the open gap on non-symmetric functions, the symmetry reduction is the only place the argument requires each Hamming layer to carry identical weights; a witness whose weights are symmetric only on average would keep the residue structure while escaping that reduction, a natural route toward $n/2+\Omega(\sqrt n)$ matching the cost of full-input recovery.
Original abstract
The oracle-interrogation algorithm [van Dam, FOCS '98] computes every $n$-bit Boolean function with bounded error using $n/2+O(\sqrt n)$ quantum queries. In contrast, parity can be computed exactly using $\lceil n/2\rceil$ queries, but whether an additive overhead beyond $n/2$ is necessary for a single Boolean output has remained open. In this work, we construct an explicit family of symmetric Boolean functions requiring $n/2+\Omega(n^{1/3})$ quantum queries at a fixed positive constant error. We also give an algorithm that recovers the exact Hamming weight using $n/2+O(n^{1/3})$ quantum queries with bounded error, and therefore computes every symmetric Boolean function within the same query bound. Together, these results determine the optimal additive order for Hamming weight recovery and for the worst case over symmetric Boolean functions at sufficiently small constant error.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
The oracle-interrogation algorithm [van Dam, FOCS '98] computes every $n$-bit Boolean function with bounded error using $n/2+O(\sqrt n)$ quantum queries. In contrast, parity can be computed exactly using $\lceil n/2\rceil$ queries, but whether an additive overhead beyond $n/2$ is necessary for a single Boolean output has remained open. In this work, we construct an explicit family of symmetric Boolean functions requiring $n/2+\Omega(n^{1/3})$ quantum queries at a fixed positive constant error. We also give an algorithm that recovers the exact Hamming weight using $n/2+O(n^{1/3})$ quantum queries with bounded error, and therefore computes every symmetric Boolean function within the same query bound. Together, these results determine the optimal additive order for Hamming weight recovery and for the worst case over symmetric Boolean functions at sufficiently small constant error.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | The oracle-interrogation algorithm [van Dam, FOCS '98] computes every $n$-bit Boolean function with bounded error using $n/2+O(\sqrt n)$ quantum queries. | background 1.00 | 0.03 | 0.03 | asserted 1.00 |
| s1 | In contrast, parity can be computed exactly using $\lceil n/2\rceil$ queries, but whether an additive overhead beyond $n/2$ is necessary for a single Boolean output has remained open. | gap 0.97 | 0.05 | 0.03 | asserted 0.93 |
| s2 | In this work, we construct an explicit family of symmetric Boolean functions requiring $n/2+\Omega(n^{1/3})$ quantum queries at a fixed positive constant error. | result 0.87 | 0.97 | 0.58 | asserted 1.00 |
| s3 | We also give an algorithm that recovers the exact Hamming weight using $n/2+O(n^{1/3})$ quantum queries with bounded error, and therefore computes every symmetric Boolean function within the same query bound. | contribution 0.54 | 0.96 | 0.28 | asserted 1.00 |
| s4 | Together, these results determine the optimal additive order for Hamming weight recovery and for the worst case over symmetric Boolean functions at sufficiently small constant error. | interpretation 0.90 | 0.91 | 0.58 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:2611.09809 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.