Scholarlink

<p>While it is known that there is at most a polynomial separationbetween quantum query complexity and the polynomial degree fortotal functions, the precise relationship between the two is not clear forpartial functions. In this paper, we demonstrate an exponential separationbetween exact polynomial degree and approximate quantum querycomplexity for a partial Boolean function. For an unbounded alphabetsize, we have a constant versus polynomial separation.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

  • 期刊论文

  • 发表日期：

    2025年10月3日

查看全文
  • Andris Ambainis,
  • Aleksandrs Belovs

摘要

While it is known that there is at most a polynomial separationbetween quantum query complexity and the polynomial degree fortotal functions, the precise relationship between the two is not clear forpartial functions. In this paper, we demonstrate an exponential separationbetween exact polynomial degree and approximate quantum querycomplexity for a partial Boolean function. For an unbounded alphabetsize, we have a constant versus polynomial separation.