1
$\begingroup$

It is my understanding, based on this question that problems solved on quantum computers with oracles don’t make any statements about BQP in relation to other complexity classes.

The fallacy is in the construction of the algorithm. It uses an oracle. That oracle computes something using the function in a very specific way. So the statement is really "if we compute using this oracle, then we can prove that separation".

So how do we make statements about BQP then? Almost all quantum algorithms input some sort of oracle. Grover’s algorithm inputs an oracle $U |x \rangle = (-1)^{f(x)} |x\rangle$. Shor’s algorithm inputs $U |y \rangle = |ay \; mod \; N\rangle$.

Does this mean that factoring isn’t actually in BQP (or functionBQP) as we know? If so, how could we prove or disprove this claim.

Improve this question
$\endgroup$
1
  • $\begingroup$ The input for the matrix factorization is a number $n$. I didn't check the details, but Shor's paper describes how to construct the circuit for given $n$ (and some other values). $\endgroup$
    – Dmitry
    Mar 16 at 17:58

1 Answer 1

Reset to default
1
$\begingroup$

Shor's algorithm does not use an oracle. The input is a number $n$ to be factored. $U$ is not an oracle; it is a computation that is done by the algorithm (akin to a subroutine).

Improve this answer
$\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.