Quantum Algorithm for Monotonicity Testing on the Hypercube

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