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:
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?