Quantum Algorithm for Monotonicity Testing on the Hypercube

Abstract

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

6 pages

References in corpus (12)

• Quantum Amplitude Amplification and Estimation
• Negative weights make adversaries stronger
• Quantum query complexity of state conversion
• Span-program-based quantum algorithm for evaluating formulas
• A Survey of Quantum Property Testing
• Learning-Graph-Based Quantum Algorithm for k-distinctness
• Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure
• New algorithms and lower bounds for monotonicity testing
• Quantum Counterfeit Coin Problems
• Classical and Quantum Algorithms for Exponential Congruences
• Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
• Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries