Skip to content
Preprint

Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method

Sep 2026 · 0 citations · 21 references
Physics Computer Science

TL;DR

A multiplicative-adversary derivation that tracks the progress produced by individual oracle queries and proves that unique OR on bits with success probability $1/2+\zeta$ requires $\Omega(\sqrt{\zeta n})$ queries, and reduces unique OR to the two-weight counting problem.

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+\Delta$ with success probability $1/2+\zeta$. Using the multiplicative adversary method, we prove $\Omega\left(\max\left\{\zeta\sqrt{(N-M)(M+\Delta)}/\Delta,\sqrt{\zeta N/\Delta}\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+\Delta\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{\Pi}_{\mathrm{bad}})\lvert\Psi^T\rangle\right\|^2=O\left(T^2\Delta^2/((N-M)(M+\Delta))\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+\zeta$ requires $\Omega(\sqrt{\zeta n})$ queries, and then reduce unique OR to the two-weight counting problem.

View source

Similar papers

Preprint Sep 2026

Quantum Approximate Counting with Bernoulli Oracles

An upper bound of $\tilde{O}\!\big(\frac{\rho}}{\Delta\epsilon}+\frac{1}{\Delta\sqrt{\epsilon}}\big)$ queries is proved for quantum counting with bounded-error oracles, achieving a quadratic speedup over the classical sample complexity.

Chen Gao, Yong-Zhen Xu, Lvzhou Li · 0 citations
Preprint Oct 2026

Optimal query complexity for fractional quantum evolution

The argument reduces any $N$-query circuit to the approximation of $e^{it\theta}$ by a trigonometric polynomial with degree bounded by $O(N)$ by a trigonometric polynomial with degree bounded by $O(N)$ together with Remez inequality to establish a matching lower bound for arbitrary query algorithms.

A. Liu, Adam Wesołowski, Jayne Thompson et al. · 0 citations
Preprint Aug 2026

Provable Quantum-Classical Separation for Continuous Gibbs Sampling

We prove the first quantum-classical separation for a sampling problem over a continuous domain. For a class of Gibbs states $p\propto e^{-\beta E}$ on the torus $\mathbb{T}^d$ with smooth ($s$-Gevrey) potential and barrier amplitude $\alpha=e^{\beta\Delta}$, where $\Delta = \max E-\min E$, every classical algorithm qu...

Enrico Olivucci, Mariia Sobchuk, Sehmimul Hoque et al. · 1 citation
Preprint Oct 2026

Quantum Advantage for Two-Party Differential Privacy

We introduce information-theoretically private quantum protocols for two-party Hamming distance when both parties must output the same estimate. Classically, for input length $n$, information-theoretic protocols require $\Omega(\sqrt{n})$ error under pure differential privacy and $\Omega(\sqrt{n}/\log n)$ error under s...

Daniel Alabi, Emil T. Khabiboulline · 0 citations
Preprint Aug 2026

Near-Optimal Mixedness Testing with Pauli Measurements

We consider a fundamental problem of \emph{mixedness testing}: Given $n$ copies of an $N$-qubit state $\rho$, determine whether $\rho = \mathbb{I}_d/d$ or $\|\rho-\mathbb{I}_d/d\|_1 \geq \varepsilon$ with high probability, where $d = 2^N$. In particular, we focus on performing this task in the practical setting of sing...

Jayadev Acharya, Abhilash Dharmavarapu, Yu-Han Liu et al. · 1 citation
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

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