  We study the exact open system dynamics of single qubit gates during a
measurement-based quantum computation considering non-Markovian environments.
We obtain analytical solutions for the average gate fidelities and analyze it
for amplitude damping and dephasing channels. We show that the average fidelity
is identical for the X-gate and Z-gate and that neither fast application of the
projective measurements necessarily implies high gate fidelity, nor slow
application necessarily implies low gate fidelity. Indeed, for highly
non-Markovian environments, it is of utmost importance to know the best time to
perform the measurements, since a huge variation in the gate fidelity may occur
given this scenario. Furthermore, we show that while for the amplitude damping
the knowledge of the dissipative map is sufficient to determine the best
measurement times, i.e. the best times in which measures are taken, the same is
not necessarily true for the phase damping. To the later, the time of the set
of measures becomes crucial since a phase error in one qubit can fix the phase
error that takes place in another.
