Fetching the paper…
Reading the bibliography…
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.
Testing monotonicity
O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samorodnitsky · 2000
Earlier work this paper cites.
Quantum amplitude amplification and estimation
G. Brassard, P. Høyer, M. Mosca, and A. Tapp · 2002
Earlier work this paper cites.
Monotonicity testing over general poset domains
E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, and A. Samorodnitsky · 2002
Earlier work this paper cites.
Negative weights make adversaries stronger
P. Høyer, T. Lee, and R. Špalek · 2007
Earlier work this paper cites.
Classical and quantum algorithms for exponential congruences
W. van Dam and I. E. Shparlinski · 2008
Earlier work this paper cites.
B. W. Reichardt · 2009
Earlier work this paper cites.
Monotonicity testing and shortest-path routing on the cube
J. Briët, S. Chakraborty, D. García-Soriano, and A. Matsliah · 2010
Earlier work this paper cites.
Quantum query complexity of state conversion
T. Lee, R. Mittal, B. W. Reichardt, R. Špalek, and M. Szegedy · 2011
Earlier work this paper cites.
Learning-graph-based quantum algorithm for k k -distinctness
A. Belovs · 2012
Cited alongside, same era.
Span programs for functions with constant-sized 1-certificates
A. Belovs · 2012
Cited alongside, same era.
Span programs and quantum algorithms for s t st -connectivity and claw detection
A. Belovs and B. W. Reichardt · 2012
Cited alongside, same era.
Quantum counterfeit coin problems
K. Iwama, H. Nishimura, R. Raymond, and J. Teruyama · 2012
Cited alongside, same era.
Span-program-based quantum algorithm for evaluating formulas
B. W. Reichardt and R. Špalek · 2012
Improved quantum query algorithms for triangle finding and associativity testing
T. Lee, F. Magniez, and M. Santha · 2013
Later among the works it cites.
A survey of quantum property testing
A. Montanaro and R. de Wolf · 2013
Later among the works it cites.
Quantum algorithms for learning symmetric juntas via the adversary bound
A. Belovs · 2014
Later among the works it cites.
Boolean function monotonicity testing requires (almost) n 1 / 2 n^{1/2} non-adaptive queries
X. Chen, A. De, R. A. Servedio, and L.-Y. Tan · 2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Super-polynomial quantum speed-ups for Boolean evaluation trees with hidden structure
B. Zhan, S. Kimmel, and A. Hassidim · 2012
Cited alongside, same era.
A o ( n ) o(n) monotonicity tester for boolean functions over the hypercube
D. Chakrabarty and C. Seshadhri · 2013
Cited alongside, same era.
X. Chen, R. A. Servedio, and L.-Y. Tan · 2014
Later among the works it cites.
Analysis of boolean functions
R. O’Donnell · 2014
Later among the works it cites.
On monotonicity testing and boolean isoperimetric type theorems
S. Khot, D. Minzer, and M. Safra · 2015
Closest in time.