2
$\begingroup$

I am a physicist getting acquainted with one of the typical constructs for formulation and analysis of quantum algorithms (such as search problems or query complexity models), namely the "oracle function". As far as I understand, the oracle is a quantum black-box entity which computes the quantity to be analyzed. For example, in a qubit circuit formulation of a universal quantum computer the oracle is a deterministically computed Boolean function (correct me here if I'm wrong).

My question is:

  • Is quantum oracle implementation overhead counted when the computational complexity of specific/well-known algorithms is compared to alternatives?

Examples: deterministic Deutsch-Jozsa algorithm algorithm is exponentially faster than a classical counterpart only if the implementation of the unknown function $f$ requires less than $2^n$ classical "steps'' (including obtaining the guarantee that $f$ is either partial or constant). A stochastic example: collapse of the Grover algorithm speedup by a faulty oracle with an arbitrary small but constant failure probability.

Why do one care: Of course, one can alsways say that we look just at the non-oracle part or count only the number of queries etc. But any talk of quantum speedup has any chance of empirical relevance only if the overhead for implementation of all of the quantum parts of the construction is taken into account (if it is trivial/constant - no problem). In other words, I find it meaningful to compare quantum algorithms only after they are "fully compiled'' onto (at least hypothetically) realizable classically-driven hardware (e.g., universal set of gates plus as many qubits as one needs - but we'll count all the time & memory required).

My question is probably fairly typical for a non-expert, perhaps I just got confused by some less sophisticated introductions to quantum computation. Please deconfuse me.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ When we say Deutsch-Jozsa is exponentially faster than its classical counterpart, we're usually talking about query complexity which is relative to queries to the oracle. So your comment that its speedup comes from the implementation of the Oracle itself doesn't make sense in that context (or I miss understood your point). It sounds like you're talking about a different complexity model than that of query complexity. Query complexity is typically what we look at with Oracle-based quantum algorithms. So maybe the short answer to your question is, "no it's not counted." $\endgroup$
    – Logan Mayfield
    Mar 1, 2013 at 20:58
  • 1
    $\begingroup$ I think this is relevant to what you're thinking about: Aaronson: Doing My Oracle Duty $\endgroup$
    – Logan Mayfield
    Mar 1, 2013 at 21:13
  • $\begingroup$ @LoganMayfield Thanks for an extremely relevant link! That explains that uncoditional speedups are a known to exist only in "relativized world" (with oracles). $\endgroup$
    – Slaviks
    Mar 2, 2013 at 7:35

2 Answers 2

Reset to default
1
$\begingroup$

As pointed out by Logan Mayfield, Scott Aaronson's blogpost on the topic completely resolves my question. Oracles is a fundamental tool for rigorous investigation of computational complexity classes,

“bring out the latent strengths” of one class over another class.

The root cause of my concerns was that little (as far as I understand - nothing) can be proven unconditionally about quantum speedups in the unrelativized (compiled to physical hardware) world. Of course, this obstacle does not diminish the power of the oracle framework as a major tool enabling progress in quantum computation theory, including the celebrated example of Shor's algorithm.

Personally, it is a consolation to learn from Scott that

This [relativized vs. unrelatized complexity] is an absolutely crucial distinction that trips up just about everyone when they’re first learning quantum computing.

Improve this answer
$\endgroup$
0
$\begingroup$

If you have a circuit which implements a function on a classical computer, then you can implement that function on a quantum computer with only small overhead (a factor of 2 I think). So in that sense, there is not much oracle overhead. Grover's algorithm for finding a needle in a haystack calls the oracle $O(\sqrt{N})$ times and the classical sequential "Is the needle here? How about here?" search calls the oracle $O(N)$ times. So there is a quantum speedup for Grover versus the classical sequential search even if the quantum oracle runs twice as slow as the classical one.

However, one then has to consider whether the classical sequential search was in fact the fastest way to do it. In the case of an oracle that is implemented using a polynomial size circuit, if P=NP then there would be a $\textrm{polylog}(N)$ time algorithm to find the needle in the haystack. To prove that there is no better way that sequential search in general, you need to construct something like a random oracle, which ends up not being efficient to build.

A separate but related issue is that in the context of query complexity one only considers the number of times the oracle is queried, and not the complexity of the intermediate operations. Considering these intermediate operations, Grover's algorithm actually takes $O(\log(N)\sqrt{N})$ time in addition to the $O(\sqrt{N})$ oracle queries, which isn't really all that bad. The general hidden subgroup problem, if I recall correctly, has a rather low query complexity but known algorithms make use of unitary operations that are exponentially difficult to implement. So in this case the quantum algorithm is not so practical.

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.