Before revision:  We show that languages not in QSG admit a reduction from the prefix problem for a cyclic group, so that they require \Omega(log n  / log log n ) operations in the worst case;
After revision:  We show that languages not in QSG admit a reduction from the prefix problem for a cyclic group, so that they require \Omega / log log n ) operations in the worst case;