Do animals have qualia?

if you disbelieve in cruelty to animals, you probably beleive they do.

If yes, what evolutionary advantage do they serve in animals?

High calorie food tastes sweet, potential poisons taste bitter, etc.

If no, how did this complex structure (of quantum microtubules or whatever else) suddenly appear?

Micortubules are not unqiuely human.