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.

$\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, 2023 at 17:58

1 Answer 1

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).

$\endgroup$

Your Answer

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

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