Sebastian Dörn and Thomas Thierauf
Abstract:
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 quasigroup 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.
(pdf-version)