← 研踪 PaperTrailarXiv:2611.21994 · v1
An alternate proof of the QMA lower bound for set-size estimation
首次提交 2026-11-17 07:26
版本更新 2026-11-17 07:26
雷达观测 2026-11-18 19:43
摘要
In the set-size estimation query task, a query algorithm decides whether an -bit input has Hamming weight or (with as the yes instances and as the no instances). When , this is sometimes called approximate counting. The query complexity for this problem with a quantum witness (i.e., 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.
作者备注:5 pages
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-17 07:26 · 最新观测版本
An alternate proof of the QMA lower bound for set-size estimation
In the set-size estimation query task, a query algorithm decides whether an -bit input has Hamming weight or (with as the yes instances and as the no instances). When , this is sometimes called approximate counting. The query complexity for this problem with a quantum witness (i.e., 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.
查看此版本解读 →查看此版本原文 ↗