Quantum Algorithm For Distribution-free Junta Testing | Awesome Quantum Computing Papers

Quantum Algorithm For Distribution-free Junta Testing

Aleksandrs Belovs · Lecture Notes in Computer Science · 2019

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/\epsilon)), which constitutes a quadratic improvement. We also prove that there is no efficient quantum algorithm for this problem using quantum examples as opposed to quantum membership queries. This result was obtained independently from the (\tilde O(k/\epsilon)) algorithm for this problem by Bshouty.

Explore more on:
Quantum Algorithms
Similar Work
Loading…