10
$\begingroup$

Most quantum algorithms proposed, including Deutsch-Jozsa, Simon's, Bernstein-Vazirani etc, involve querying an oracle. If I understand correctly, the speedups depend on the oracle being efficiently constructible.

Recently, Bravyi et al proposed a quantum algorithm which essentially replaces the oracle in Bernstein-Vazirani with a grid-like 2D structure.

What are some other examples of non-oracular versions of famous oracular problems? Also, is it known that the oracles are always efficiently constructible for the famous cases I mentioned?

Improve this question
$\endgroup$
4
  • $\begingroup$ are non-oracular versions of these algorithms actually useful though? For D-J you cannot go around the need to compute $f(x)$ at some point, and the oracle doesn't need more than the ability to compute $f(x)$. Same goes for Simon's alg, just with different assumptions on $f$. In B-V the function is something like $a\cdot x+b$, which again is not hard to implement. $\endgroup$
    – glS ♦
    Commented Aug 18, 2019 at 18:38
  • 1
    $\begingroup$ Even more importantly, in all of these case, how would you even go in defining an "oracle-free" version of the problem? They are all algorithms of the form "figure out something about the given black-box operation", so if the operation is not given as an oracle I don't understand what problem remains to be solved $\endgroup$
    – glS ♦
    Commented Aug 18, 2019 at 18:38
  • 1
    $\begingroup$ @gIS: Certain 'oracle algorithms' could still provide a quantum advantage if you replace the oracle (which after all, is basically a slot saying "insert function of such-and-such a type here") with a subcircuit $C$ that actually computes a function. The 'oracle' algorithm then tells you the corresponding thing about $C$. It might allow a provable but small separation (as with Bravyi-Gosset-Koening) or it may provide a large improvement over known classical techniques (without necessarily being better than all possible classical algorithms), which is the situation with Shor's algorithm. $\endgroup$
    – Niel de Beaudrap
    Commented Aug 22, 2019 at 9:14
  • 2
    $\begingroup$ I think that this is a worthy – but hard – question. The fact that Bravyi-Gosset-Koening was one of the more interesting results in quantum complexity of the past few years demonstrates the value, but also the difficulty, of the problem. As I suggest above, Shor's algorithm technically fits the bill of a de-oraclised version of the Abelian Hidden Subgroup Problem (or perhaps Simon's algorithm): but this would have been a bit of a stretch for the spirit of the question (for instance, the aHSP was defined after Shor's result). An interesting new de-oraclised algorithm would be a strong result. $\endgroup$
    – Niel de Beaudrap
    Commented Aug 22, 2019 at 9:21

1 Answer 1

Reset to default
3
$\begingroup$

As mentioned above there is nothing called "Oracle free" algorithm.

Let's put this in simple words: Consider we are making a problem solving algorithm to solve the roots of a quadratic equation. Let the equation be $ax^2+bx+c$ and the algorithm finds the values of $x$ . Here the function to create $ax^2+bx+c$ acts as an oracle. You can put this oracle either in a different function using def() or you can directly add it to the main algorithm. Either way you have to use the oracle to find the solution. There is no use for a root finding algorithm without an oracle(that is you cannot find $x$ without $ax^2+bx+c$). It is the same case for all solution finding algorithms.

There are no "Oracle-free" algorithms, there are only different methods of defining an oracle.

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 and welcome to our community! We hope to see much more of you in the future. I've just made some edits which it might be worth it for you to take a look at :) $\endgroup$
    – user1271772 No more free time
    Commented Sep 1, 2021 at 2:39

Your Answer

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