Low-hanging fruit from two conjoined trees
Alright, I can give an oracle relative to which BQP is not in SZK, thereby knocking off one of the Ten Most Annoying Questions in Quantum Computing.
It’s a forehead-slapper. Just take the problem from the paper Exponential algorithmic speedup by quantum walk by Andrew Childs et al. Here the oracle encodes an exponentially large graph, consisting of two binary trees conjoined at the leaves by a random cycle:
(I hope Childs et al. will forgive me for swiping their graphic.)
Each vertex is labeled by a random string, and given the label of a vertex, the oracle tells us the labels of its neighbors. Then, given the label of the Entrance vertex, the problem is to decide (let’s say) whether the label of the Exit vertex starts with a 1 or a 0.
Childs et al. proved that this oracle problem is in BQP but not in BPP. Intuitively, any classical random walk on the graph will get stuck for an exponentially long time in the enormous middle region, but because of interference effects, a quantum walk will tunnel right through to the Exit vertex with 1/polynomial probability.
Now, it’s easy to generalize their proof that the problem is not in BPP, to show that it’s not in SZK. One way to see this is that, for a prover to convince a verifier of the solution, the prover will (basically) have to reveal where the Exit vertex is, thereby violating the zero-knowledge property. Another way to see it is that, if we consider the Sahai-Vadhan characterization of SZK in terms of the Statistical Difference problem, then neither of the two distributions we’re comparing will depend non-negligibly on the Exit vertex.
Disappointingly, this solution is way too trivial to publish, and almost too trivial even to blog. On the other hand, so far I’ve been unable to extend the solution to get an oracle relative to which BQP is not in AM. Every variant of the problem I’ve come up with is in AM intersect coAM, sometimes for non-obvious reasons. Anyone want to help me?
Follow
Comment #1 August 21st, 2006 at 8:51 pm
Is there a non-quantum intuition about the kinds of graph search we can expect to do in BQP using the quantum-walk paradigm?
Comment #2 August 22nd, 2006 at 3:35 am
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.
Comment #3 August 22nd, 2006 at 8:49 am
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.
Comment #4 August 22nd, 2006 at 10:41 am
Can we prove the other direction? That SZK is not contained in BQP relative to an oracle.
Andris
Comment #5 August 22nd, 2006 at 11:01 am
Andris: Yes, that’s the collision lower bound! 🙂
Comment #6 August 22nd, 2006 at 2:44 pm
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?
Comment #7 August 22nd, 2006 at 3:05 pm
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.