Someone argues: "Simon's algorithm solves its hidden-period problem with quantum…
PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms
Quantum Information and Technology, Ch What quantum computers can compute efficiently
Problem
Someone argues: "Simon's algorithm solves its hidden-period problem with O(n) quantum queries against Ω(2n/2) classical queries. This is an exponential gap, and it holds no matter what the oracle computes internally, so it proves that quantum computers are exponentially faster than classical computers in general, that is, BPP=BQP as classes of ordinary, oracle-free problems."
((a)) Say what Simon's separation actually establishes, stating it precisely.
((b)) Explain why the argument's final step, from the oracle separation to an unrelativised BPP=BQP, is not valid, using the fact quoted about oracles relative to which P=NP and others relative to which P=NP.