# Why is Shor's algorithm in $BPP^{BQNC}$ when needing to uncompute subprocedure call?

Why is Shor's algorithm in $BPP^{BQNC}$? It's true the quantum Fourier transform is in $BPP^{BQNC}$, but the algorithm needs to call a number theoretic function f which has period p which is a factor of n. f is computed by exponentiation by squaring, but the important thing is it has to be uncomputed reversibly. Doesn't the reversibility requirement place it out of BPP even though it superficially looks like it belongs there?

• Why should the reversibility requirement place it out of BPP? Do you mean out of BQNC? – Peter Shor Dec 27 '13 at 17:30