Quantum emitter-based schemes for the generation of photonic graph states offer a promising, resource efficient methodology for realizing distributed quantum computation and communication protocols on near-term hardware. We present a heralded scheme for making photonic graph states that is compatible with the typically poor photon collection from state-of-the-art coherent quantum emitters. We demonstrate that the construction time for large graph states can be polynomial in the photon collection efficiency, as compared to the exponential scaling of current emitter-based schemes, which assume deterministic photon collection. The additional overhead to achieve this advantage consists of an extra spin system plus one additional spin-spin entangling gate per photon added to the graph. While the proposed scheme enables the generation of graph states for arbitrary applications, we show how it can be further simplified for the specific task of measurement-based computation, leading to significantly higher rates and removing the need for photonic memory in certain computations. As an example use-case of our scheme, we construct a protocol for secure two-party computation that can be implemented efficiently on current hardware. Estimates of the fidelity to produce graph states used in the computation are given, based on current trapped ion experimental benchmarks.
