Universal fault-tolerant quantum computers require millions of qubits with low error rates. Since this technology is years ahead, noisy intermediate-scale quantum (NISQ) computation is receiving tremendous interest. In this setup, quantum reservoir computing is a relevant machine learning algorithm. Its simplicity of training and implementation allows to perform challenging computations on today's available machines. In this Letter, we provide a criterion to select optimal quantum reservoirs, requiring few and simple gates. Our findings demonstrate that they render better results than other commonly used models with significantly less gates and also provide insight on the theoretical gap between quantum reservoir computing and the theory of quantum states' complexity.