  Quantum information science addresses how uniquely quantum mechanical
phenomena such as superposition and entanglement can enhance communication,
information processing and precision measurement. Photons are appealing for
their low noise, light-speed transmission and ease of manipulation using
conventional optical components. However, the lack of highly efficient optical
Kerr nonlinearities at single photon level was a major obstacle. In a
breakthrough, Knill, Laflamme and Milburn (KLM) showed that such an efficient
nonlinearity can be achieved using only linear optical elements, auxiliary
photons, and measurement. They proposed a heralded controlled-NOT (CNOT) gate
for scalable quantum computation using a photonic quantum circuit to combine
two such nonlinear elements. Here we experimentally demonstrate a KLM CNOT
gate. We developed a stable architecture to realize the required four-photon
network of nested multiple interferometers based on a displaced-Sagnac
interferometer and several partially polarizing beamsplitters. This result
confirms the first step in the KLM `recipe' for all-optical quantum
computation, and should be useful for on-demand entanglement generation and
purification. Optical quantum circuits combining giant optical nonlinearities
may find wide applications across telecommunications and sensing.
