Andris

]]>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.

]]>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.

]]>