The future optical switched wavelength division multiplexed (WDM) networks will require all optical wavelength conversion to avoid contention in a node when two signals on the same wavelength are being switched to the same output fiber. These future networks will also employ advanced modulation formats in order to increase the capacity of optical networks. In order to perform wavelength conversion operations on advanced modulation formats, a coherent nonlinear process, such as four-wave mixing (FWM), is required to preserve the amplitude and phase information. The phase noise transfer problem has crucial significance for the exploitation of FWM-based wavelength converters for advanced modulation formats because the phase noise transfer degrades the overall system performance. In this work, the required optical signal to noise ratio (OSNR) and laser phase noise (linewidth) limits are calculated via Monte Carlo simulations for the wavelength conversion of advanced modulation formats including DQPSK and M-QAM. Due to the sensitivity of M-QAM signals with respect to phase noise, the conversion performance is investigated using two different decision-directed phase-locked loop carrier phase recovery algorithms. In order to develop a validated numerical model for all-optical wavelength conversion of advanced modulation formats, the required OSNR versus pump linewidth at two values of bit error rate (BER) of 10-3 and 10-4 for DQPSK, 16-QAM and 64-QAM are reported for degenerate and non-degenerate FWM. With these calculations, the performance of wavelength conversion of advanced modulation formats will be guaranteed by selecting lasers with linewidths below these linewidth limits. As a next step of this work, All-optical wavelength conversion of Nyquist-WDM Superchannel using FWM in an SOA based on advanced modulation formats such as DQPSK, 16 and 64- QAM are demonstrated.