  Quantum memory for flying optical qubits is a key enabler for a wide range of
applications in quantum information science and technology. A critical figure
of merit is the overall storage-and-retrieval efficiency. So far, despite the
recent achievements of efficient memories for light pulses, the storage of
qubits has suffered from limited efficiency. Here we report on a quantum memory
for polarization qubits that combines an average conditional fidelity above 99%
and an efficiency equal to (68$\pm$ 2)%, thereby demonstrating a reversible
qubit mapping where more information is retrieved than lost. The qubits are
encoded with weak coherent states at the single-photon level and the memory is
based on electromagnetically-induced transparency in an elongated laser-cooled
ensemble of cesium atoms, spatially multiplexed for dual-rail storage. This
implementation preserves high optical depth on both rails, without compromise
between multiplexing and storage efficiency. Our work provides an efficient
node for future tests of quantum network functionalities and advanced photonic
circuits.
