That two photons pass each other undisturbed in free space is ideal for the faithful transmission of information, but prohibits an interaction between the photons. Such an interaction is, however, required for a plethora of applications in optical quantum information processing(1). The long-standing challenge here is to realize a deterministic photon-photon gate, that is, a mutually controlled logic operation on the quantum states of the photons. This requires an interaction so strong that each of the two photons can shift the other's phase by pi radians. For polarization qubits, this amounts to the conditional flipping of one photon's polarization to an orthogonal state. So far, only probabilistic gates(2) based on linear optics and photon detectors have been realized(3), because "no known or foreseen material has an optical nonlinearity strong enough to implement this conditional phase shift"(4). Meanwhile, tremendous progress in the development of quantum-nonlinear systems has opened up new possibilities for single-photon experiments(5). Platforms range from Rydberg blockade in atomic ensembles(6) to single-atom cavity quantum electrodynamics(7). Applications such as single-photon switches(8) and transistors(9,10), two-photon gateways(11), nondestructive photon detectors(12), photon routers(13) and nonlinear phase shifters(14-18) have been demonstrated, but none of them with the ideal information carriers: optical qubits in discriminable modes. Here we use the strong light-matter coupling provided by a single atom in a high-finesse optical resonator to realize the Duan-Kimble protocol(19) of a universal controlled phase flip (p phase shift) photon-photon quantum gate. We achieve an average gate fidelity of (76.2 +/- 3.6) per cent and specifically demonstrate the capability of conditional polarization flipping as well as entanglement generation between independent input photons. This photon-photon quantum gate is a universal quantum logic element, and therefore could perform most existing two-photon operations. The demonstrated feasibility of deterministic protocols for the optical processing of quantum information could lead to new applications in which photons are essential, especially long-distance quantum communication and scalable quantum computing.