Comments on: Low-hanging fruit from two conjoined trees

By: Scott

Scott — Tue, 22 Aug 2006 21:05:00 +0000

Luca: Yeah, if you want to separate BQP from SZK, you simply fix an oracle such that the promise is always satisfied. Of course you can also separate PromiseBQP from PromiseSZK.

By: Luca

Luca — Tue, 22 Aug 2006 20:44:00 +0000

Does this only separate promise-BPP from promise-SZK? Or do you just let the oracle tell you when the promise is satisfied and when it is not?

By: Scott

Scott — Tue, 22 Aug 2006 17:01:00 +0000

Andris: Yes, that’s the collision lower bound!

By: Anonymous

Anonymous — Tue, 22 Aug 2006 16:41:00 +0000

Can we prove the other direction? That SZK is not contained in BQP relative to an oracle.

Andris

By: Greg Kuperberg

Greg Kuperberg — Tue, 22 Aug 2006 14:49:00 +0000

Hi Scott. As it happens, I thought some about this problem on my plane flight to Madrid this week. I kept coming back to my “killer app” of oracular quantum languages. Namely, let the oracle be a source of random diagonal operators, and consider a linear-length alternation of these operators with Hadamard layers. Then we conjectured in our paper that any given input state, say ¦00…0>, goes to a nearly uniformly random pure state after even a small number of such layers. For definiteness, let’s take a linear number of layers.

Now choose a random tally language L, and condition the nth stage of the oracle so that ¦00…0> goes to itself when 0^n is in L. You can if you like condition ¦00…0> to go to an orthogonal state when 0^n is not in L, but this is not really necessary.

I will just be provocative and conjecture outright that this specific oracular language, which has obviously been designed to be in BQP, is not in PH, much less in AM. I think that it’s worth investigating. If you don’t like the probability theory involved, it would be worth simply writing down the necessary lemmas from probability that would have to hold if the example works.

By: Scott

Scott — Tue, 22 Aug 2006 09:35:00 +0000

Unfortunately, I think right now the best intuition is: “We can do search in BQP (for the Exit vertex) on graphs that look like the two conjoined trees!”

It’s clear that, if you want to find an arbitrary marked vertex, that’s at least as hard as Grover search. So search is only going to be possible on graphs with an Exit vertex that plays some distinguished role.

In the case of the conjoined trees, the intuition is that because of interference, a quantum walk on this graph looks exactly like a quantum walk on a line of length 2n+1, with a “defect” in the middle corresponding to where the random cycle is. The Childs et al. paper explains this pretty well if you’re interested.

By: Andy D

Andy D — Tue, 22 Aug 2006 02:51:00 +0000

Is there a non-quantum intuition about the kinds of graph search we can expect to do in BQP using the quantum-walk paradigm?