# Quantum Algorithm for Monotonicity Testing on the Hypercube

arXiv: https://arxiv.org/abs/1503.02868 · HTML: https://mlsanity.com/paper/1503.02868/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2015.

## Built on by (most cited first, 1 of 1)

- [Testing classical properties from quantum data](https://mlsanity.com/paper/2411.12730/) (2024)

## Abstract (arXiv)

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.