Volume 11 (2015)
Article 16 pp. 403-412
[Note]
Quantum Algorithm for Monotonicity Testing on the Hypercube
Received: March 24, 2015
Revised: July 16, 2015
Published: December 29, 2015
Revised: July 16, 2015
Published: December 29, 2015
Keywords: Boolean functions, quantum query complexity, property testing, monotonicity
Categories: quantum computing, algorithms, Boolean functions, query complexity, quantum query complexity, property testing, monotone functions, note
ACM Classification: F.2.2, F.1.3, G.1.6
AMS Classification: 68Q17, 52C07, 11H06, 11H31, 05B40
Abstract: [Plain Text Version]
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}$.
Licensed under a Creative Commons Attribution License (CC-BY)