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?

  • $\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 Aug 18 '19 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 Aug 18 '19 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 Aug 22 '19 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 Aug 22 '19 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.