  We consider online algorithms with respect to the competitive ratio. Here, we
investigate quantum and classical one-way automata with non-constant size of
memory (streaming algorithms) as a model for online algorithms. We construct
problems that can be solved by quantum online streaming algorithms better than
by classical ones in a case of logarithmic or sublogarithmic size of memory,
even if classical online algorithms get advice bits. Furthermore, we show that
a quantum online algorithm with a constant number of qubits can be better than
any deterministic online algorithm with a constant number of advice bits and
unlimited computational power.
