We investigate all-optical switching and wavelength conversion based on ultrafast nonlinearities in a multi-quantum-well semiconductor optical amplifier. We present a rate equation model that accounts for two-photon absorption, free-carrier absorption, self- and cross phase modulation, carrier heating, spectral, spatial hole burning and self- and cross polarization modulation. We demonstrate optical AND gate operation using a semiconductor optical amplifier placed in an asymmetric March-Zehnder interferometer and we show that the gate can be operated using 800 fJ optical pulses with duration of 200 fs. We also investigate wavelength conversion based on ultrafast nonlinear polarization rotation. We found a conversion efficiency of 12 dB for control pulse energies of 10 pJ.