Towards Optimal Separations between Quantum and Randomized Query Complexities
Towards Optimal Separations between Quantum and Randomized Query Complexities
复制标题
实现量子和随机查询复杂性之间的最佳分离
DOI：
10.1109/focs46700.2020.00030
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Avishay Tal
中科院分区：
文献类型：
--
作者：
Avishay Tal
查询模型提供了一个具体的设置，其中量子算法被证明优于随机算法。 Bernstein-Vazirani、Simon、Aaronson 和其他人提出了部分布尔函数，这些函数可以通过量子算法计算，与随机类似物相比，查询次数要少得多。迄今为止，量子和随机查询复杂度之间 $O(1)$ 与 $\sqrt{N}$ 的分离仍然是最先进的（其中 $N$ 是输入长度），留下了 $O(1)$ 与 $N^{1/2+\Omega(1)}$ 分离是否可能的问题？对于这个问题我们的回答是肯定的。我们的分离问题是 Aaronson-Ambainis k 重关系问题的变体。我们展示了我们的变体：1）可以通过量子算法来解决，对输入进行 $2^{O(k)}$ 查询。 2) 任意随机算法至少需要 $\widetilde{\Omega}(N^{2(k-1)/(3k-1)})$ 次查询。对于任何常数 $\epsilon > 0$，这给出了部分布尔函数的量子和随机查询复杂性之间的 $O(1)$ 与 $N^{1/2-\epsilon}$ 分离。我们的证明是傅里叶分析的，并使用经典决策树傅里叶谱的新界限，这可能具有独立的意义。展望未来，我们推测傅里叶界限可以以精确的方式进一步改进，并表明这种推测的界限意味着部分布尔函数的量子和随机查询复杂性之间的最佳 $O(1)$ 与 $N^{1-\epsilon}$ 分离。
The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantum algorithms making much fewer queries compared to their randomized analogs. To date, separations of $O(1)$ vs. $\sqrt{N}$ between quantum and randomized query complexities remain the state-of-the-art (where $N$ is the input length), leaving open the question of whether $O(1)$ vs. $N^{1/2+\Omega(1)}$ separations are possible? We answer this question in the affirmative. Our separating problem is a variant of the Aaronson-Ambainis k-fold Forrelation problem. We show that our variant: 1)Can be solved by a quantum algorithm making $2^{O(k)}$ queries to the inputs. 2)Requires at least $\widetilde{\Omega}(N^{2(k-1)/(3k-1)})$ queries for any randomized algorithm. For any constant $\epsilon > 0$, this gives a $O(1)$ vs. $N^{1/2-\epsilon}$ separation between the quantum and randomized query complexities of partial Boolean functions. Our proof is Fourier analytical and uses new bounds on the Fourier spectrum of classical decision trees, which could be of independent interest. Looking forward, we conjecture that the Fourier bounds could be further improved in a precise manner, and show that such conjectured bounds imply optimal $O(1)$ vs. $N^{1-\epsilon}$ separations between the quantum and randomized query complexities of partial Boolean functions.
第二傅立叶级伪随机发生器及其在具有奇偶校验门的 AC0 中的应用
DOI：
--
发表时间：
2019
期刊：
(ITCS
影响因子：
--
作者：
Chattopadhyay, Eshan;Hatami, Pooya;Lovett, Shachar;Tal, Avishay
通讯作者：
Tal, Avishay
Oracle BQP 和 PH 分离
DOI：
10.1145/3313276.3316315
发表时间：
2019
期刊：
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019
影响因子：
--
作者：
Raz, Ran;Tal, Avishay
通讯作者：
Tal, Avishay