Quantum Algorithm for Monotonicity Testing on the Hypercube

Abstract

In this note, we develop a bounded-error quantum algorithm that makes $\tilde{O}(n^{1/4}{\epsilon }^{-1/2})$ queries to a Boolean function $f$, accepts a monotone function, and rejects a function that is $\epsilon$-far from being monotone. This gives a super-quadratic improvement compared to the best known randomized algorithm for all $\epsilon =o(1)$. The improvement is cubic when $\epsilon =1/\sqrt{n}$.

6 pages

References in corpus (4)

• Learning-Graph-Based Quantum Algorithm for k-distinctness
• New algorithms and lower bounds for monotonicity testing
• Classical and Quantum Algorithms for Exponential Congruences
• Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries