Theory of Computing
-------------------
Title     : Quantum Algorithm for Monotonicity Testing on the Hypercube
Authors   : Aleksandrs Belovs and Eric Blais
Volume    : 11
Number    : 16
Pages     : 403-412
URL       : https://theoryofcomputing.org/articles/v011a016

Abstract
--------

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