Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Quantum computers can solve certain problems faster than classical computers e.g factoring numbers.
and this is because quantum computers can do a fourier transform on $n$ qubits in $O(n^2)$ time as opposed to $O(n2^n)$ time.
We can usually reduce time complexities by pretending that we can do some thing faster - introducing oracle's that can solve a problem instantly.
Is there a constant time oracle that encodes all the quantum speed ups we get?
Vacuous answer: because $\text{BPP}^\text{BQP} = \text{BQP}$, giving a computer access to a $\text{BQP}$ oracle makes it equivalent to a quantum computer at solving decision problems in polynomial time. This is sort of like saying "if your computer has access to a quantum computer, then you have access to a quantum computer" but it does meet the criteria in your question.
Also, quantum computers can't do a Fourier transform on $2^n$ bits in $O(n^2)$ time. Quantum computers can apply a Fourier transform to the state vector of $n$ qubits in $O(n^2)$ time. It's not at all the same thing.
Technically, the main differences between classical and quantum algorithms are super-position and entanglement that make the concept of oracle in quantum algorithms. As these two are only meaningful in quantum mechanics, you can't have that oracle with the same cost as the quantum algorithms, in classical algorithms.
Yes. BQP has problems that are complete for BQP. So, an oracle for any BQP-complete problem suffices.
Let me add to the previous questions that BQP capture the power of quantum computers for decision problems, but there are other algorithmic tasks to consider. It is a reasonable conjecture that equipping a BPP computer with an oracle for BQP complete problems does not enable performing quantum sampling (or even just boson sampling). And perhaps this conjecture remains true if you equip it with a PH oracle as well!.
It seems likely that equipping a classical computer with quantum sampling powers give it full BQP power. I don't know about other algorithmic tasks for quantum computers that leads to interesting complexity classes, e.g. even more powerful than quantum sampling.
