  The realization of strong photon-photon interactions has presented an
enduring challenge across photonics, particularly in quantum computing, where
two-photon gates form essential components for scalable quantum information
processing (QIP). While linear-optic schemes have enabled probabilistic
entangling gates in spatio-polarization encoding, solutions for many other
useful degrees of freedom remain missing. In particular, no two-photon gate for
the important platform of frequency encoding has been experimentally
demonstrated, due in large part to the additional challenges imparted by the
mismatched wavelengths of the interacting photons. In this article, we design
and implement the first entangling gate for frequency-bin qubits, a
coincidence-basis controlled-NOT (CNOT), using line-by-line pulse shaping and
electro-optic modulation. We extract a quantum gate fidelity of $0.91 \pm 0.01$
via a novel parameter inference approach based on Bayesian machine learning,
which enables accurate gate reconstruction from measurements in the two-photon
computational basis alone. Our CNOT imparts a single-photon frequency shift
controlled by the frequency of another photon---an important capability in
itself---and should enable new directions in fiber-compatible QIP.
