Similar matrices in $\mathbb{Z}/n\mathbb{Z}$

Yes, they are similar. They have the same characteristic polynomial, which is $x^3+x=x(x+1)^2$. So, each of them is similar to$$\begin{bmatrix}0&0&0\\0&1&0\\0&0&1\end{bmatrix}\text{ or to }\begin{bmatrix}0&0&0\\0&1&1\\0&0&1\end{bmatrix}.$$But you can easily check that, both for $P$ and for $Q$, the eigenspace associateed with the eignvalue $1$ is $1-$ dimensional. Therefore, they are both similar to the second of the two matrices mentioned above, and so they are similar to each other.