  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.
