  Scalability of flying photonic quantum systems in generating quantum
entanglement offers a potential for implementing large-scale fault-tolerant
quantum computation, especially by means of measurement-based quantum
computation (MBQC). However, existing protocols for MBQC inevitably impose a
polynomial overhead cost in implementing quantum computation due to geometrical
constraints of entanglement structures used in the protocols, and the
polynomial overhead potentially cancels out useful polynomial speedups in
quantum computation. To implement quantum computation without this
cancellation, we construct a protocol for photonic MBQC that achieves as low as
poly-logarithmic overhead, by introducing an entanglement structure for
low-overhead qubit permutation. Based on this protocol, we design a
fault-tolerant photonic MBQC protocol that can be performed by experimentally
tractable homodyne detection and Gaussian entangling operations combined with
the Gottesman-Kitaev-Preskill (GKP) quantum error-correcting code, which we
concatenate with the $7$-qubit code. Our fault-tolerant protocol achieves the
threshold $7.8$ dB in terms of the squeezing level of the GKP code,
outperforming $8.3$ dB of the best existing protocol for fault-tolerant quantum
computation with the GKP surface code. Thus, bridging a gap between theoretical
progress on MBQC and photonic experiments towards implementing MBQC, our
results open a new way towards realization of a large class of quantum speedups
including those polynomial.
