Metraipolis › archive › dc_e1237d9b8509

Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method — arXiv:2609.09804

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.09804
License (as archived): CC0-1.0
Archived: 2026-10-16T11:18:16.132Z
SHA-256 of the archived text: 978d18fadc3eafdd6e17093b04e3d6890ef5ecbb3aac78a6747cd2c18b10bec8
Stable URL of this page: https://metraipolis.com/documento/dc_e1237d9b8509

How to cite

Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method — arXiv:2609.09804 — arXiv (en), https://arxiv.org/abs/2609.09804 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e1237d9b8509 (Metraipolis archive dc_e1237d9b8509, sha256 978d18fadc3eafdd6e17093b04e3d6890ef5ecbb3aac78a6747cd2c18b10bec8)

BibTeX

@misc{dce1237d9b8509,
  title = {Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method — arXiv:2609.09804},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.09804},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e1237d9b8509; sha256 978d18fadc3eafdd6e17093b04e3d6890ef5ecbb3aac78a6747cd2c18b10bec8},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.09804. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-10 in cs.CC).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.09804 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T10:56:42.344Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).