Minimal resources for linear optical one-way computing

We address the question of how many maximally entangled photon pairs are needed 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 uses 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 with 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 significant reduction in resource consumption.