0
$\begingroup$

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$ bits 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 an oracle that encoded all the quantum speed ups we get?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.