1
$\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$ 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?

$\endgroup$

4 Answers 4

2
$\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$
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$
0
$\begingroup$

Yes. BQP has problems that are complete for BQP. So, an oracle for any BQP-complete problem suffices.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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