Measurement-based quantum computation (MBQC) relies on entangled graph states, yet existing remote state preparation (RSP) protocols prepare only separable states, requiring subsequent entangling gates on the remote server. Here, we introduce Remote Graph State Preparation (RGSP), a framework that prepares arbitrary graph states directly from a single high-dimensional photonic qudit. By encoding multiple qubits and their graph connectivity into the photon's structured phase profile, RGSP can reduce or, for small computations, completely eliminate the need for server-side entangling operations among qubits. We show that under a reasonable noise model the resulting state fidelity is independent of the graph topology. Under cumulative fiber phase drift, we demonstrate that this fidelity is significantly enhanced by a ``highest-weight-first'' mode reordering strategy. Finally, we show that RGSP enables reduced-SWAP universal blind quantum computing on arbitrary topologies, reducing qubit overhead e.g., for a six-qubit Quantum Fourier Transform from
420 RSP qubits with a standard brickwork topology to
48 RSP qubits. These results establish RGSP as a resource-efficient, topology-invariant primitive for quantum-secured cloud computing.
The graph state formalism is a useful abstraction of entanglement. It is used in some multipartite purification schemes and it adequately represents universal resources for measurement-only quantum computation. We focus in this paper on the complexity of graph state preparation. We consider the number of ancillary qubits, the size of the primitive operators, and the duration of preparation. For each lexicographic order over these parameters we give upper and lower bounds for the complexity of graph state preparation. The first part motivates our work and introduces basic notions and notations for the study of graph states. Then we study some graph properties of graph states, characterizing their minimal degree by local unitary transformations, we propose an algorithm to reduce the degree of a graph state, and show the relationship with Sutner sigma-game. These properties are used in the last part, where algorithms and lower bounds for each lexicographic order over the considered parameters are presented.