Among the various approaches to quantum computing, all-optical architectures are especially promising due to the robustness and mobility of single photons. However, the creation of the two-photon quantum logic gates required for universal quantum computing remains a challenge. Here we propose a universal two-qubit quantum logic gate, where qubits are encoded in surface plasmons in graphene nanostructures, that exploits graphene's strong third-order nonlinearity and long plasmon lifetimes to enable single-photon-level interactions. In particular, we utilize strong two-plasmon absorption in graphene nanoribbons, which can greatly exceed single-plasmon absorption to create a "square-root-of-swap" that is protected by the quantum Zeno effect against evolution into undesired failure modes. Our gate does not require any cryogenic or vacuum technology, has a footprint of a few hundred nanometers, and reaches fidelities and success rates well above the fault-tolerance threshold, suggesting that graphene plasmonics offers a route towards scalable quantum technologies.