Are there any cases where quantum has given insight for classical algorithms? To be more specific, has it ever happened that we've made some kind of significant improvement to a classical algorithm or problem as a result of some "trick" or insight gained from looking at quantum algorithms?
There is at least one example that I can remember, but there are probably more that I am not aware of.

Recently, Maarten Van den Nest and Wolfgang Dürr found a  new classical algorithm (arXiv:1304.2879) to approximate certain types of partition functions (of 3-body classical Ising models on two-dimensional lattices.  Their algorithm is completely classical, but several connections to quantum physics are employed in the design (read below). The algorithm was found to be exponentially faster than previously known algorithms that solve the same problem, at the time of writing*.

*I am ignorant of whether better classical or quantum algorithms have been found a posteriori.

So, there are at least two quantum ingredients used in the design of the VdND algorithm. On the one hand, the authors use a classical-quantum connection between classical Ising models and topological quantum systems (precisely, some color codes). On the other hand, the authors use classical techniques to simulate quantum systems in the derivation of the algorithm: in their proof, they first write a small quantum algorithm for the problem of interest; then, the authors show how to simulate the former quantum  algorithm efficiently on a classical computer, obtaining a classical algorithm (this is rather remarkable, in my view).