Minimal resources for linear optical one-way computing

We address the question of how many maximally entangled photon pairs are needed in order to build up cluster states for quantum computing using the toolbox of linear optics. As the needed gates in dual-rail encoding are necessarily probabilistic with known optimal success probability, this question amounts to finding the optimal strategy for building up cluster states, from the perspective of classical control. We develop a notion of classical strategies, and present rigorous statements on the ultimate maximal and minimal use of resources of the globally optimal strategy. We find that this strategy - being also the most robust with respect to decoherence - gives rise to an advantage of already more than an order of magnitude in the number of maximally entangled pairs when building chains with an expected length of L=40, compared to other legitimate strategies. For two-dimensional cluster states, we present a first scheme achieving the optimal quadratic asymptotic scaling. This analysis shows that the choice of appropriate classical control leads to a very significant reduction in resource consumption.