I'm not sure it's useful anymore to point to quantum computers and say: 'Hey! You're not getting all your function evaluations back....so they're weak'. I feel this leads to misconceptions about quantum computing as well. You have to remember, the tensor product of N qubits is an exponentially expanding space...and the functions DO get evaluated in that space, the trick being you have to extract a JOINT property of the function evaluations, rather than the result of each one individually. Let's be clear, even with this caveat, the potential of quantum computing is enormous. I've personally read Kalai's papers and in my opinion, his objections boil down to 'it's just too good to be true'....but hey...we'll see :)