随机与量子查询复杂度之间近乎四次方的分离
A Nearly Quartic Separation Between Randomized and Quantum Query Complexity
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
该稿件构造全布尔函数，研究有界错误随机查询复杂度R(f)与量子查询复杂度Q(f)之间的差距。摘要表示，所构造例子排除了所有α<4的通用界R(f)=O((1+Q(f))^α)，说明已知四次上界的指数最优，并否证了此前猜测的三次界。两种复杂度均按最坏情况比特查询计数，每个输入错误率至多1/3。该手稿为AI产生，尚未经独立审查或同行评议，结论属作者声称。
- 构造全布尔函数，使随机与量子查询复杂度出现近乎四次方的分离。
- 排除α<4的通用界，表明已知四次上界指数最优并否证三次界猜想。
- 复杂度按最坏情况比特查询计数，每个输入错误率至多1/3。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We construct total Boolean functions with a nearly quartic separation between bounded-error randomized and quantum query complexity. Writing these complexities as $`\mathrm R(f)`$ and $`\mathrm Q(f)`$, the examples rule out every universal bound $`\mathrm R(f)=O((1+\mathrm Q(f))^\alpha)`$ with α < 4. Thus the known quartic upper bound has the optimal exponent, disproving the conjectured cubic bound. Both complexities count worst-case bit queries with error at most 1/3 on every input.
用户标记：未标记
固定编号：5dc4f8d9c06061b5
原文来源