Experimental nonlinear sign shift for linear optics quantum computation

We have realized the nonlinear sign shift operation for photonic qubits. This operation shifts the phase of two photons reflected by a beam splitter using an extra single photon and measurement. We show that the conditional phase shift is (1.05+/-0.06)pi in clear agreement with theory. Our results show that, by using an ancilla photon and conditional detection, nonlinear optical effects can be implemented using only linear optical elements. This experiment represents an essential step for linear optical implementations of scalable quantum computation.