Deterministic optical quantum logic relies on a quantum process that alters the phase of a quantum optical state by p through interaction with only one photon. I describe an experiment where we measure a large conditional cross-phase modulation between a signal field, stored inside an atomic quantum memory, and a control photon that traverses a high finesse optical cavity containing the atomic memory. This approach avoids fundamental limitations associated with multimode effects for traveling optical photons. We measure a cross-phase shift of larger than p/3 between the retrieved signal and control photons and confirm entanglement production by extracting a positive concurrence. With a moderate improvement in cavity finesse, our system can reach a coherent phase shift of p at low loss, enabling deterministic and universal photonic quantum logic.