  The state complexity of a finite(-state) automaton intuitively measures the
size of the description of the automaton. Sakoda and Sipser [STOC 1972, pp.
275--286] were concerned with nonuniform families of finite automata and they
discussed the behaviors of the nonuniform complexity classes defined by such
families of finite automata having polynomial-size state complexity. In a
similar fashion, we introduce nonuniform state complexity classes using
nonuniform families of quantum finite automata empowered by the flexible use of
garbage tapes. We first present general inclusion and separation relationships
among nonuniform state complexity classes of various one-way finite automata,
including deterministic, nondeterministic, probabilistic, and quantum finite
automata having polynomially many inner states. For two-way quantum finite
automata equipped with flexible garbage tapes, we show a close relationship
between the nonuniform state complexity of the family of such polynomial-size
quantum finite automata and the parameterized complexity class induced by
logarithmic-space quantum computation assisted by polynomial-size advice. We
further establish a direct connection between space-bounded quantum computation
with quantum advice and quantum finite automata whose transitions are dictated
by superpositions of transition tables.
