  In this paper we consider what can be computed by a user interacting with a
potentially malicious server, when the server performs polynomial-time quantum
computation but the user can only perform polynomial-time classical (i.e.,
non-quantum) computation. Understanding the computational power of this model,
which corresponds to polynomial-time quantum computation that can be
efficiently verified classically, is a well-known open problem in quantum
computing. Our result shows that computing the order of a solvable group, which
is one of the most general problems for which quantum computing exhibits an
exponential speed-up with respect to classical computing, can be realized in
this model.
