  Photonic interconnects between quantum processing nodes are likely the only
way to achieve large-scale quantum computers and networks. The bottleneck in
such an architecture is the interface between well-isolated quantum memories
and flying photons. We establish high-fidelity entanglement between remotely
separated trapped atomic qubit memories, mediated by photonic qubits stored in
the timing of their pulses. Such time-bin encoding removes sensitivity to
polarization errors, enables long-distance quantum communication, and is
extensible to quantum memories with more than two states. Using a
measurement-based error detection process and suppressing a fundamental source
of error due to atomic recoil, we achieve an entanglement fidelity of 97% and
show that fidelities beyond 99.9% are feasible.
