  Heralded entangling quantum gates are an essential element for the
implementation of large-scale optical quantum computation. Yet, the
experimental demonstration of genuine heralded entangling gates with
free-flying output photons in linear optical system, was hindered by the
intrinsically probabilistic source and double-pair emission in parametric
down-conversion. Here, by using an on-demand single-photon source based on a
semiconductor quantum dot embedded in a micro-pillar cavity, we demonstrate a
heralded controlled-NOT (CNOT) operation between two single photons for the
first time. To characterize the performance of the CNOT gate, we estimate its
average quantum gate fidelity of ($87.8\pm1.2$)%. As an application, we
generated event-ready Bell states with a fidelity of ($83.4\pm2.4$)%. Our
results are an important step towards the development of photon-photon quantum
logic gates.
