If you talk to the travellers in the taverns and give them 10 Denars, one of them will eventually give you the location of a Red Brotherhood base. The first base you learn about in that way has a Qualis gem in the chest in front of the cavern entrance. It's harder to defeat the Red Brotherhood than a regular bandit base but it's feasible.
Another way to get gems is to get a good relationship with the Noldor. Once they give you the secret location of their castle, you can participate in their tournaments (they take place in the first few days of the month). You can win a Qualis gem. I haven't tried that yet since I was constantly at war until now, but next time they hold their tournaments, I'm in. Judging by the difficulty of their training sessions, the odds of winning are low for me right now.
The other book merchant (the one who doesn't give you the location of the mines) turns Qualis gems into alchemical potions which give attribute and weapons skill increases. The first three potions raise attributes by 2 points (not intelligence though) and weapons skills by 20, from the fourth on it's only 1 attribute point and 10 weapons points.
