Second, I posted a note to the arXiv this week called Impossibility of Succinct Quantum Proofs for Collision-Freeness<\/a>. Here’s the abstract:<\/p>\n We show that any quantum algorithm to decide whether a function f:[n]\u2192[n] is a permutation or far from a permutation must make \u03a9(n1\/3<\/sup>\/w) queries to f, even if the algorithm is given a w-qubit quantum witness in support of f being a permutation. This implies that there exists an oracle A such that SZKA<\/sup>\u2284QMAA<\/sup>, answering an eight-year-old open question of the author. Indeed, we show that relative to some oracle, SZK is not in the counting class A0<\/sub>PP defined by Vyalyi. The proof is a fairly simple extension of the quantum lower bound for the collision problem.<\/p><\/blockquote>\n This result is neither hard nor surprising, but it does more-or-less solve a problem that’s bothered me since grad school (and which I mentioned a couple months ago<\/a> on this blog) in a ridiculously simple-in-retrospect way, which is either nice or disappointing depending on how you look at it.<\/p>\n Third, some of you might have heard that the Carmel region in Israel recently suffered a terrible forest fire<\/a>, which destroyed about 30 million trees and killed 44 people, and which required the assistance of many countries to put out. Yesterday, after giving a talk at the Technion in Haifa, I had a chance to tour some of the fire damage. While we were on the hike, a torrential downpour started (which caught me without coat or umbrella)—if only the rain had come a few weeks earlier! Anyway, here are some photos:<\/p>\n
![\"\"](\"..\/..\/carmel1-sm.jpg\")
<\/a><\/p>\n![\"\"](\"..\/..\/carmel2-sm.jpg\")
<\/a><\/p>\n![\"\"](\"http:\/\/scottaaronson.blog\/carmel4-sm.jpg\")
<\/a><\/p>\n![\"\"](\"http:\/\/scottaaronson.blog\/carmel5-sm.jpg\")
<\/a><\/p>\n