Strong nonlinear interactions between photons enable logic operations for both classical and quantum-information technology. Unfortunately, nonlinear interactions are usually feeble and therefore all-optical logic gates tend to be inefficient. A quantum emitter deterministically coupled to a propagating mode fundamentally changes the situation, since each photon inevitably interacts with the emitter, and highly correlated many-photon states may be created . Here we show that a single quantum dot in a photonic-crystal waveguide can be utilized as a giant nonlinearity sensitive at the single-photon level. The nonlinear response is revealed from the intensity and quantum statistics of the scattered photons, and contains contributions from an entangled photon-photon bound state. The quantum nonlinearity will find immediate applications for deterministic Bell-state measurements and single-photon transistors and paves the way to scalable waveguide-based photonic quantum-computing architectures.