Question: Is there an infinite sequence of primes $\{q_i\}_{i=1}^{\infty}$ that is not too sparse ( $q_n =O(poly(n))$ for a fixed polynomial) for which it is true that for every $k$ there is an $N(k)$ so that if $n>N$ then there is a prime $p$ in the interval $[q^{1/k}-o(q^{1/k}),q^{1/k})$ that is a quadratic residue modulo $q$? (by $o(q^{1/k})$ I mean does there exist an function that belongs to the class $o(q^{1/k})$ for which such a statement holds?) (Does the question become easier if we ask for a non-residue?)

Motivation: I need dense, regular, $C_{2k}$-free non bipartite graphs that are good expanders. There are constructions of dense, regular, $C_{2k}$-free graphs that are good expanders by Margulis and independently by Lubotzky, Phillips and Sarnak. These constructions depend on two primes, $p$ and $q$ and they give a suitable graph if $p$ is a quaratic residue modulo $q$, and an almost suitable but bipartite graph when $p$ is a quadratic non-residue.

Additional information: If we do not need $p$ to be a quadratic residue, bounds between consecutive primes does the job.

Edit: I realized that i accidentally posed a harder than necessary problem. For my purposes it is enough to have one such sequence for every $k$, and even the polynomial $poly(n)$ can depend on $k$.