Quantum Algorithm for Monotonicity Testing on the Hypercube
classification
🪐 quant-ph
cs.DS
keywords
varepsilonalgorithmfunctionimprovementmonotonequantumacceptsbest
Add this Pith Number to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{HNWTG6FW}
Prints a linked pith:HNWTG6FW badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
In this note, we develop a bounded-error quantum algorithm that makes $\tilde O(n^{1/4}\varepsilon^{-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/\sqrt{n}$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.