CS Paper Radar

Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method

Albert Lin, Han-Hsuan Lin

cs.CC quant-ph ·submitted 2026-09-09 07:01 UTC · v2
theory

Abstract

We study the two-weight decision version of quantum approximate counting: given oracle access to $x\in\{0,1\}^N$, distinguish $|x|=M$ from $|x|=M+Δ$ with success probability $1/2+ζ$. Using the multiplicative adversary method, we prove $Ω\left(\max\left\{ζ\sqrt{(N-M)(M+Δ)}/Δ,\sqrt{ζN/Δ}\right\}\right)$. The same parameter dependence follows from the polynomial-method characterization of the two-layer symmetric function by Podder, Yao, and Ye. Our contribution is a multiplicative-adversary derivation that tracks the progress produced by individual oracle queries. For the first term, after complementing the input if necessary, we assume $M+Δ\le N-M$. We use the Hamming-layer subspaces from the eigenspace method of Ambainis, Spalek, and de Wolf and compose their adjacent-layer unitary maps to relate the two nonadjacent promise layers. After fixing the queried coordinate, the analysis block-diagonalizes into four-dimensional subspaces. An exact calculation of the one-query progress ratio gives the first lower bound. The same estimate also implies $\left\|(I-\widehatΠ_{\mathrm{bad}})\lvertΨ^T\rangle\right\|^2=O\left(T^2Δ^2/((N-M)(M+Δ))\right)$ for the coherent input superposition used in the adversary argument. For the second term, we prove directly using a three-eigenvalue multiplicative adversary that unique OR on $n$ bits with success probability $1/2+ζ$ requires $Ω(\sqrt{ζn})$ queries, and then reduce unique OR to the two-weight counting problem.

Comment
18 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions

cs.CC quant-ph ·2026-11-06 ·Yuan Deng, Zihan Hao, Honghao Lin, Qipeng Liu, Vahab Mirrokni +2 more
similarity 0.71
Abstract · 57 pages, 2 figures

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+Ω(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.

0.27

An alternate proof of the QMA lower bound for set-size estimation

cs.CC quant-ph ·2026-11-16 ·Chinmay Nirkhe
theory similarity 0.70
Abstract · 5 pages

In the set-size estimation query task, a query algorithm decides whether an $N$-bit input has Hamming weight $\ge B$ or $\le A$ (with $\ge B$ as the yes instances and $\le A$ as the no instances). When $B = 2A$, this is sometimes called approximate counting. The query complexity for this problem with a quantum witness (i.e., $\mathsf{QMA}$ query bounds) was resolved by Aaronson, Kothari, Kretschmer, and Thaler (CCC 2020) and proved using Laurent polynomials. Here we give a morally similar but distinct proof of the lower bound using the polynomial method.

0.34

Distributional Variants of the Aaronson-Ambainis Conjecture

cs.CC quant-ph ·2026-09-28 ·Uma Girish, Kunal Mittal, Barak Nehoran, Ran Raz
similarity 0.68
Abstract

A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query algorithms. More precisely, the acceptance probability of any quantum query algorithm can be approximated, on average over uniformly random inputs, by a classical query algorithm, with only polynomial query overhead. The conjecture is central to understanding whether exponential quantum advantages for decision problems necessarily rely on additional structure. We study analogues of this conjecture under other natural input distributions and prove that they are all equivalent to the original uniform-distribution conjecture. We first consider the product distribution $μ_p$, where the input bits are independent Bernoulli variables with fixed bias $p$. We show that for every fixed $p \in (0, 1)$, quantum query algorithms under the $μ_p$ distribution admit polynomial-overhead classical simulations if and only if the same holds under the uniform distribution. Second, we consider the distribution $ν_p$ that is uniform over the slice of strings with Hamming weight $\lfloor pn \rfloor$ and prove a similar equivalence for the $ν_p$ distribution and the uniform distribution. The Aaronson-Ambainis conjecture is a stronger statement that implies the above-mentioned conjecture and is formulated in terms of bounded low-degree polynomials on the Boolean hypercube. It asserts that under the uniform distribution, any such polynomial with nonnegligible variance must have an influential variable. We formulate analogues of this conjecture, where the underlying distribution is a biased product distribution or a uniform distribution over a slice, and prove that all these variants are equivalent to the original Aaronson-Ambainis conjecture.

0.43

No Size-Preserving Amplification with Quantum Advice

cs.CC quant-ph ·2026-10-02 ·Shih-Han Hung, Han-Hsuan Lin
similarity 0.67
Abstract

Marriott and Watrous showed that quantum Merlin--Arthur games admit generic error reduction without increasing witness size [Computational Complexity, 2005]. In this work, we show that this state-size-preserving amplification property does not hold for polynomial-time quantum computation with quantum advice. In particular, we present decision problems for which even a vanishing additive error reduction requires longer advice. More precisely, for every polynomially bounded advice length $m(n)=ω(1)$ and every error bound $\varepsilon(n)$ that stays below $1/2$ by at least an inverse polynomial, there is a positive function $δ$ with $δ(n)=O\bigl(\min\{(\log m/m)^{1/4},\ \sqrt{\log m/m}\,/(1/2-\varepsilon(n))\}\bigr)$ such that $\mathsf{BQP}_{\varepsilon}/\mathsf{q}m \subsetneq \mathsf{BQP}_{\varepsilon + δ}/\mathsf{q}m$; for constant $\varepsilon$ the gap is $O(\sqrt{\log m/m})$. Here, $\mathsf{BQP}_\varepsilon/\mathsf{q}m$ is the class of languages recognizable with error at most $\varepsilon(n)$ by a polynomial-time quantum algorithm with an $m(n)$-qubit advice state that only depends on the input length $n$. We show this by proving a stronger separation $\mathsf{P}_{\varepsilon+δ}/\mathsf{r} m \not\subset \mathsf{BQP}_{\varepsilon}/\mathsf{q} m$, where $\mathsf{P}_{\varepsilon}/\mathsf{r}m$ is the class of languages recognizable with error at most $\varepsilon(n)$ by a deterministic polynomial-time algorithm with an $m(n)$-bit advice string sampled from a distribution that depends only on $n$.

0.28

Noisy Quantum Query Complexity via Fractional Block Sensitivity

cs.CC quant-ph ·2026-09-30 ·Mehil Agarwal, Shravas Rao, Fang Song
theory similarity 0.66
Abstract · 34 pages, LaTex, fixed typos, updated acknowledgement, fixed mathjax in abstract

We study quantum query complexity under several models of imperfect oracle access, and develop lower bounds through a common framework based on fractional block sensitivity ($\operatorname{fbs}$). For a negligent oracle that applies the correct query with probability $1-p$, we prove a lower bound in terms of $\operatorname{fbs}(f,0^n)$. We also show, perhaps surprisingly, that negligence need not destroy quantum speedups: any function $f$ can be transformed into a partial function $f'$ whose negligent query complexity essentially preserves the quantum query complexity of $f$. This gives partial functions with exponential quantum speedups even under negligent queries, and in particular rules out a general lower bound in terms of $\operatorname{fbs}(f)$ for partial functions in this model. For two other models, we obtain general lower bounds in terms of $\operatorname{fbs}(f)$ for all Boolean functions. For hybrid algorithms using $Q$ coherent and $C$ classical queries, we prove the tradeoff $C+Q^2=Ω(\operatorname{fbs}(f))$. For an IID dephasing noisy model where each query dephases the query-index register at rate $p$ independently, we prove $Ω\!\left(p\,\operatorname{fbs}(f)\right)$ queries are necessary. Finally, we introduce a broader family of time-varying dephasing models and identify a variational resource that is always lower bounded by $\operatorname{fbs}(f)$. Computing this resource reduces to a convex optimization problem, providing a simple way to derive lower bounds for new noise schedules. As applications, we recover the hybrid and IID dephasing bounds and determine the query complexity of unstructured search when the dephasing rate grows over time.

0.26

$\mathsf{BQP} \subseteq \mathsf{IP}$ Does Not Relativize

cs.CC quant-ph ·2026-09-22 ·Adam Bouland, Andrew Huang, Anand Natarajan, Itay Shalit, Avishay Tal
similarity 0.65
Abstract

We construct an oracle relative to which $\mathsf{BQP} \not\subseteq \mathsf{IP}$, resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson et al., our work also gives the first oracle separation between $\mathsf{IP}$ and $\mathsf{MIP}$, answering a question dating back to Fortnow's thesis. Our separation is based on the Forrelation problem, where given Boolean functions $f$ and $g$, the goal is to determine if $f$ is correlated with the Fourier spectrum of $g$. While this task is solvable by a query-efficient quantum algorithm, we show that it admits no classical interactive protocol with polynomial communication and a polynomial-query verifier. Our proof is based on (i) a new structural result showing how to approximate Avg-Max circuits (which are well-known to capture the power of interactive proofs in the oracular setting) by convex functions with small first and second derivatives and (ii) a novel analysis establishing that the Forrelation distribution suggested by Aaronson and Ambainis fools such functions. Our results imply that any prover-efficient classical interactive protocol for $\mathsf{BQP}$ must rely on non-relativizing techniques. This might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.

0.42

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

cs.CC quant-ph ·2026-10-17 ·Guoliang Xu, Haoran Zhang, Mengfan Wu, Songyao Xue, Mingke Liu
theory similarity 0.65
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.

0.06

Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

cs.CR quant-ph ·2026-10-05 ·Keshav Bhateja, Mehdi Esmaili, Atul Mantri
benchmark similarity 0.65
Abstract

Random circuit sampling experiments, the leading demonstrations of quantum computational advantage, are tested with the linear cross-entropy benchmark (XEB), which scores outcomes by their ideal probabilities. We study what a high XEB score certifies about an untrusted quantum device. In the quantum query model, we show that the honest sampler's ideal score acts as a Tsirelson bound for efficient devices and certified randomness. First, exceeding the ideal score by a constant requires $Ω(N^{1/3})$ queries for the Haar and Fourier oracle ensembles with $N$ outcomes, and this bound is tight; this proves an earlier conjecture for Haar-random states and extends it to Fourier sampling. Second, for Fourier sampling and for Haar-random states accessed through the canonical state-preparation oracle, the $n$-bit output of a device that makes polynomially many queries and scores within $o(1)$ of the ideal score has $n-O(\log n)$ bits of smooth min-entropy, even against an adversary who is entangled with the device and later learns the oracle; this is nearly optimal. As a corollary, sampling the collision distribution, which is proportional to the square of the ideal distribution, has query complexity $Θ(N^{1/3})$, and a coherent version of the same algorithm approximately prepares quantum Hadamard products of states with uniform amplitude magnitudes. Both lower bounds rest on progress measures that bound the excess over the ideal score and increase only slightly with each query. For Fourier sampling the measure is the norm of the coherent amplitudes for removing pairs in a purification of the random function, combining the polynomial method with the compressed oracle technique; for Haar-random states it is the square root of the average level in an expansion in Dirichlet orthogonal polynomials, controlled by an exact identity for the effect of one observation.

0.09