Proof for the SHA3 claim that 256 bit security is "post-quantum sufficient"? On page 14 of "Keccak and the SHA-3 Standardization" (February 6, 2013) it says:


  
  Instantiation of a sponge function
  
  the permutation KECCAK-f
  7 permutations: b → {25,50,100,200,400,800,1600}
  Security-speed trade-offs using the same permutation, e.g.,
  
  SHA-3 instance: r = 1088 and c = 512
  permutation width: 1600
  security strength 256: post-quantum sufficient
  Lightweight instance: r = 40 and c = 160
  permutation width: 200
  security strength 80: same as SHA-1
  
  
  


(note: emphasis mine)

Since I regard quantum cryptography to be currently walking in it's child-shoes, with a high potential of evolving substantially during the upcoming years, I just have to ask: What exactly is the base for the KECCAK claim that a security strength of 256 bits is "post-quantum sufficient"?
Well, cryptographers have been contemplating a post-quantum world for some time now.

Quantum computing, although in its infancy as far as real-life computers go, has been studied in a theoretical sense for a quite a while. Shor's algorithm was published 19 years ago; Grover's, 17 years ago. These are the two most-famous quantum algorithms, I think, but the field goes back further than that: according to Wikipedia, the field was born somewhere in the 1980s. 

The point is that even though quantum computing hasn't produced a usable, useful real-life quantum computer yet, it has been considered for quite a long while now. So while huge breakthroughs are still very possible, it's likely that researchers have exhausted all of the easy lines of attack. Further, since it doesn't seem that in the last 16 years any new, cryptography-threatening quantum attacks have surfaced (at least, none that I am aware of), it seems relatively safe to talk about post-quantum strength. 

More to the point, the real threat against hash functions in a post-quantum world would be Grover's algorithm. Using Grover's algorithm, mounting a brute-force preimage search on an $n$-bit random oracle has time $O\left(2^{n/2}\right)$. 

Although direct application of asymptotic bounds is rather imprecise, this would lead to a preimage attack in time $2^{128}$ for a 256-bit (preimage-resistant) hash function. This is still secure, and I think this is what the authors were intending when they said "post-quantum sufficient." For more information, see the question What security does Keccak offer against quantum attacks, specifically Grover's algorithm?.