This paper takes a computational learning theory approach to a problem of linear systems identification. It is assumed that inputs are generated randomly from a known class consisting of linear combinations of k sinusoidals. The output of the system is classified at some single instant of time. The main result establishes that the number of samples needed for identification with small error and high probability, independently from the distribution of inputs, scales polynomially with n, the system dimension, and logarithmically with k.