The Quantum Complexity of Group Testing

We present quantum query and time complexity bounds for group testing problems. For a set S and a binary operation on S, we consider the decision problem whether a groupoid, semigroup or quasi-group is a group. Our quantum algorithms for these problems improve the best known classical complexity bounds. We also present upper and lower bounds for testing associativity, distributivity and commutativity.