In this blog post, I tackle my perplexity at what seems to be a common practice of using quantum oracles without worrying about their time-complexity.

Am I the only quantum computer programmer worried about this? Is there some important point that I’m missing?

This being a blog post, I’ve tried to be as introductory and pedagogical as possible. Since I wanted to use Latex intensively, I’ve put the core of this post in this pdf document. (Feb 14, 2009: Inspired by the excellent blog comments below by Scott Aaronson, I have updated the core pdf to version 2)

### Like this:

Like Loading...

*Related*

rr: Yes, it’s obvious that almost all quantum oracles on n qubits require exponential circuit size. (The same is true of almost all classical oracles, btw.) Just like negative and complex numbers for 16th-century mathematicians, oracles are a

successful fiction: that is, an initially “unphysical”-looking abstraction that we introduce, not because we feel like it, but because we’ve learned through long experience that it helps a great deal in understanding the things we care about directly.If you have an algorithm that calls an oracle (like the period-finding part of Shor’s algorithm), then to run that algorithm in the real world, of course you need an efficient implementation of the oracle. In the case of Shor’s algorithm, such an implementation happily exists (namely the repeated-squaring algorithm for modular exponentiation). In the case of Grover’s algorithm, the implementation might be (for example) the checking function for an NP-complete problem. For other quantum algorithms (like Simon’s algorithm), we don’t still know any efficient implementation of the oracle—or at least, none that wouldn’t let us solve the problem in a much easier way than by running the quantum algorithm. But those algorithms have still proved to be extremely useful for understanding quantum computing. Recall that Simon’s algorithm played a crucial role in leading to the discovery of Shor’s algorithm!

Another crucial role of oracles is to point out the

limitationsof existing proof techniques (i.e., “since I can exhibit an oracle relative to which this bizarre thing happens, any proof that itdoesn’thappen will have to use the fact that in the real world, no such oracle exists”).Comment by Scott Aaronson — February 9, 2009 @ 11:53 pm

I think what bothers me is twofold:

(1)I don’t object to the use of oracles. But if one uses them, one should make clear whether they are of exponential(NB) complexity or not. Often I see people claim that an algorithm is efficient because it queries an oracle polynomial(NB) times, but further analysis shows that their oracle has exponential(NB) complexity. Such an algorithm isn’t really efficient, is it?

(2)In a classical computer, when using an algebraically specified function, x^2 say, one doesn’t have to load a table of x^2 for all x. Instead one loads the algebraic information that the function is x^2, and one evaluates x^2 at those few x where one needs to know it. Loading the algebraic information has constant complexity, loading a table has exponential complexity. Implementing an oracle that takes |0>|x> to |x^2>|x> is like loading a full table of x^2 for all x. Why don’t quantum algorithms use an algebraic approach?

Comment by rrtucci — February 10, 2009 @ 5:19 pm

rr, you’re completely wrong that mapping |x⟩|0⟩ to |x⟩|x^2⟩ is like loading a table full of x^2. You do it in superposition, so it takes no more time than computing x^2 once.

And as for reading papers with oracles—if you just read what the papers actually say, and don’t interpret them as saying something they don’t say (e.g. that the oracles can be implemented efficiently), you’re less likely to be disappointed later on. 🙂

Comment by Scott Aaronson — February 10, 2009 @ 6:25 pm

Interesting. Can you please say more on how one maps |x>|0> to |x>|x^2> efficiently. What quantum circuit are you thinking of?

Comment by rrtucci — February 10, 2009 @ 7:57 pm

You must be joking—this is one of the basic steps in pretty much every quantum algorithm, including Shor’s. You’ve seriously never seen it? Look, you agree that x^2 can be computed

classicallyin polynomial time? Well then, you can also map |x> to |x>|x^2> coherently, using Bennett’s uncomputing trick: first apply the reversible circuit C that maps |x> to |x>|g_x>|x^2>, where g_x is some garbage depending on x. Then CNOT |x^2> into a separate register (to save it), and finally apply C^-1 to uncompute |g_x> and one of the copies of |x^2>. The end result is |x>|x^2>, as desired. Of course, applying this circuit to a superposition of |x>’s will result in a superposition of |x>|x^2>’s, by linearity.Comment by Scott Aaronson — February 11, 2009 @ 2:03 am

It seems that what you are saying is that quantum oracles that take |x>|0> to |x>|f(x)>, where f(x) is a polynomial in x, have (exact) efficient circuits. Also quantum oracles with functions f(x) that can be approximated by a polynomial have approximate efficient circuits.

In general, if we know how to compute f(x) efficiently, then there is an efficient circuit for the quantum oracle. But quantum oracles with an arbitrary f(x) that does not fit this description may not have efficient circuits. (For example, the oracle in Farhi et al NAND formula algorithm cannot in general be fitted by a polynomial) Would you agree with this summary, or am I still missing something?

Comment by rrtucci — February 11, 2009 @ 3:54 am

By the way, thanks for recommending the movie Wall-E in your blog. Fantastic movie. You see, my prodigious brain is absorbing complexity theory from your blog like a sponge.

Comment by rrtucci — February 11, 2009 @ 4:16 am

Yes, I agree with your summary. But Farhi et al.’s NAND-tree algorithm was a bad example for you to have chosen! For games like chess, we

dohave reasonably-efficient algorithms to compute an evaluation of a given board position (which corresponds to “querying the oracle”). So the Farhi et al. algorithm would really, actually, literally give a polynomial speedup over the known classical algorithms when applied to games like chess.Comment by Scott Aaronson — February 11, 2009 @ 4:43 am

Perplexity is to intractability as complexity is to clarity.

Comment by Martin Musatov — December 7, 2014 @ 12:14 am

Do you worry at all about Quantum time plus complexity as it relates to one of a very few possible Quantum Time Minus Complexity Oracles?

Comment by Martin Michael Musatov — January 24, 2015 @ 1:18 am

I don’t worry at all. Sorry Martin, I’m a physicist who knows very little about complexity theory. Try asking Scott Aaronson (and don’t try your old trick of posting P=NP proofs in other people’s blogs)

Comment by rrtucci — January 24, 2015 @ 1:34 am