This occurs if and only if the matrices $Q^r$ and $Q^s$ are conjugate. This is the case if and only if these matrices are conjugate over the algebraic closure of $\mathbb{F}_p$. If $Q$ iis diagonalizable, then things are straightfoward: if its eigenvalues are $\alpha_1,\ldots,\alpha_n$ then $Q^r$ is conjugate to $Q^s$ if and only if $\alpha_1^r,\ldots,\alpha_n^r$ are a permutation of $\alpha_1^s,\ldots,\alpha_n^s$.
An interesting case is where the characteristic polynomial of $Q$ is irreducible over $\mathbb{F}_q=\mathbb{F}_{p^k}$. In this case the eigenvalues of $Q$ are $\alpha,\alpha^q,\alpha^{q^2},\ldots,\alpha^{q^{n-1}}$. Then $Q^r$ and $Q^s$ are conjugate if and only if $s\equiv q^i r$ (mod $t$) for some $i$ with $0\le i < n$ and where $t$ is the multiplicative order of $\alpha$ (and of $Q$).
When $Q$ is not diagonalizable, things get rather tedious. It's not too bad if $Q$ is invertible and $r$ and $s$ are not divisible by $p$. If $Q$ has a Jordan block of size $k$ with eigenvalue $\alpha$ then $Q^r$ also has a Jordan block of size $k$ with eigenvalue $\alpha^r$ as long as $r$ is coprime to $p$. If $Q$ is singular or $r$ is a multiple of $p$ then the Jordan block sizes of $Q^r$ might be different from those of $Q$. Tedium ensues :-)