2
$\begingroup$

Can the Bernstein-Vazirani algorithm be applied to a remote classical function? As in, a function we are not able to set up an oracle for and is completely classical?

$\endgroup$
2
  • 2
    $\begingroup$ Hi! Welcome to QCSE. Can you edit your posting to consider only one question per post? That helps the community to focus. To me the first question is a little broad and unclear, but the second one is pretty reasonable, and I’d consider focusing on that one for now. You can always ask more than one question with different posts- just don’t go overboard. $\endgroup$ Apr 23, 2022 at 2:28
  • $\begingroup$ Ok I added resolved to the first, I would remove but there is already answer to the first. Thank you though! $\endgroup$
    – Random
    Apr 23, 2022 at 19:03

1 Answer 1

1
$\begingroup$

The answer is no. The Bernstein-Vazirani algorithm requires that the use of a quantum oracle that is structured based on the problem’s parameters - namely, the string $s$.

The classical strategy we can use in the classical oracle case is to simply call the function $n$ times (where $n$ in the number of bits needed to represent $s$), each time with a different bit set to $1$, while all other bits are set to $0$. This is different than in the quantum case, where we only need one query to the oracle.

$\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.