  The goal in function property testing is to determine whether a black-box
Boolean function has a certain property or is epsilon-far from having that
property. The performance of the algorithm is judged by how many calls need to
be made to the black box in order to determine, with high probability, which of
the two alternatives is the case. Here we present two quantum algorithms, the
first to determine whether the function is linear and the second to determine
whether it is symmetric (invariant under permutations of the arguments). Both
require O(epsilon^{-2/3}) calls to the oracle, which is better than known
classical algorithms. In addition, in the case of linearity testing, if the
function is linear, the quantum algorithm identifies which linear function it
is. The linearity test combines the Bernstein-Vazirani algorithm and amplitude
amplification, while the test to determine whether a function is symmetric uses
projective measurements and amplitude amplification.
