  It has been demonstrated that the optimal sensitivity achievable with
Greenberger-Horne-Zeilinger states is the same as that with uncorrelated probes
in the frequency estimation in the presence of uncorrelated Markovian dephasing
[S. F. Huelga, et al., Phys. Rev. Lett. 79, 3865 (1997)]. Here, we extend this
issue by examining the optimal frequency sensitivities achievable by the use of
ancilla-assisted strategy, which has been proposed recently for robust phase
estimation. We present the ultimate frequency sensitivities bounded by the
quantum Fisher information for a general case in the presence of Markovian
covariant phase noises, and the optimal measurement observables that can
saturate the theoretical sensitivity bounds. We also demonstrate the
effectiveness of the ancilla-assisted strategy for preserving frequency
sensitivities suffering from specific physically ground noises.
