We present a systematic comparison of different methods of fidelity estimation of a linear optical quantum controlled-Z gate implemented by two-photon interference on a partially polarizing beam splitter. We have utilized a linear fidelity estimator based on the Monte Carlo sampling technique as well as a non-linear estimator based on maximum likelihood reconstruction of a full quantum process matrix. In addition, we have also evaluated lower bound on quantum gate fidelity determined by average quantum state fidelities for two mutually unbiased bases. In order to probe various regimes of operation of the gate we have introduced a tunable delay line between the two photons. This allowed us to move from high-fidelity operation to a regime where the photons become distinguishable and the success probability of the scheme significantly depends on input state. We discuss in detail possible systematic effects that could influence the gate fidelity estimation.