  We show that semiclassical formulas such as the Gutzwiller trace formula can
be implemented on a quantum computer more efficiently than on a classical
device. We give explicit quantum algorithms which yield quantum observables
from classical trajectories, and which alternatively test the semiclassical
approximation by computing classical actions from quantum evolution. The gain
over classical computation is in general quadratic, and can be larger in some
specific cases.
