Quantum Algorithm for Distribution-Free Junta Testing
Quantum Algorithm for Distribution-Free Junta Testing
复制标题
用于无分发 Junta 测试的量子算法
DOI：
10.1007/978-3-030-19955-5_5
复制
发表时间：
2019
影响因子：
3.6
通讯作者：
Aleksandrs Belovs
中科院分区：
文献类型：
--
作者：
Aleksandrs Belovs
受Chen，Liu，Serverdio，Sheng，and Xie（STOC'18）最近经典的无分布junta测试器的启发，我们构造了一个复杂度为O（k/\vareps）\）的量子测试器，这构成了二次改进。
Inspired by a recent classical distribution-free junta tester by Chen, Liu, Serverdio, Sheng, and Xie (STOC’18), we construct a quantum tester for the same problem with complexity \(O(k/\varepsilon )\), which constitutes a quadratic improvement.