3
$\begingroup$

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.