Efficient Construction of High-Dimensional Cluster State

We present a scheme for efficiently constructing high-dimensional cluster state using probabilistic entangling quantum gates. It is shown that the required computational overhead scales efficiently both with 1/p and n even if all the entangling quantum gates only succeed with an arbitrary small probability, where p is the success probability of the entangling quantum gate and n is the number of qubits in the computation.