Potential and limits to cluster-state quantum computing using probabilistic gates

We establish bounds to the necessary resource consumption when building up cluster states for one-way computing using probabilistic gates. Emphasis is put on state preparation with linear optical gates, as the probabilistic character is unavoidable here. We identify rigorous general bounds to the necessary consumption of initially available maximally entangled pairs when building up one-dimensional cluster states with individually acting linear optical quantum gates, entangled pairs, and vacuum modes. As the known linear optics gates have a limited maximum success probability, as we show, this amounts to finding the optimal classical strategy of fusing pieces of linear cluster states. A formal notion of classical configurations and strategies is introduced for probabilistic nonfaulty gates. We study the asymptotic performance of strategies that can be simply described, and prove ultimate bounds to the performance of the globally optimal strategy. The arguments employ methods of random walks and convex optimization. This optimal strategy is also the one that requires the shortest storage time, and necessitates the fewest invocations of probabilistic gates. For two-dimensional cluster states, we find, for any elementary success probability, an essentially deterministic preparation of a cluster state with quadratic, hence optimal, asymptotic scaling in the use of entangled pairs. We also identify a percolation effect in state preparation, in that from a threshold probability on, almost all preparations will be either successful or fail. We outline the implications on linear optical architectures and fault-tolerant computations.

Figure 1

Action of a fusion gate on the end qubits of two linear cluster states.

Figure 2

Diagram representing how parity check gate can be employed to realize a Bell state discriminating device.

Figure 3

An example of a tree of successive configurations under application of a strategy. Light boxes group configurations. We start with $N=4$. Dark boxes indicate where the strategy decided to apply a fusion gate. Possible outcomes are success (to the left) or failure (to the right), resulting in different possible future choices. The expected length of the final chain is ${\tilde{Q}}_M\left(4\right)=Q\left(4\right)=13∕8$.

Figure 4

The process of fusion of the largest can be represented as a tree similar to a random walk. Reflection occurs at the dashed line (the largest string is lost and replaced with an EPR pair). Time evolves from top to bottom, thus decreasing the number of EPR resources. The horizontal dimension represents the length of the largest string.

Figure 5

Expected length for the globally optimal strategy, for MODESTY (in this plot indistinguishable from the former), for GREED, its asymptotic performance, and the lower bound for STATIC, as functions of even number $N$ of initial EPR pairs. The inset shows GREED and MODESTY for small $N$, revealing the parity-induced steplike behavior.

Figure 6

Expected length for MODESTY, the optimal strategy (where known) a lower bound to the quality as in Theorem 6, but with $N_0=46$ (for better visualization), and the upper bound attained with the razor model as functions of the number of initial EPR pairs $N$.

Figure 7

Performance of the optimal strategy in the razor model ($R=2$ and 3), the full model $(R=N)$, and the upper bound attained with the $R=2$ razor model. The inset shows the convergence of the upper bound to the quality (based on the razor model with parameter $R$) vs the razor parameter $R=2,\dots ,10$ for $N=30$ together with the optimal value $Q\left(30\right)$.

Figure 8

The configuration space of the $R=2$ razor model is ${\mathbb{N}}_0\times {\mathbb{N}}_0$. Only the three actions $a$, $b$, and $c$ are available to reach the final configurations (exactly one EPR pair or GHZ state, or no chain at all), starting from the initial configuration that consists of $N$ EPR pairs.

Figure 9

A possible pattern of how to arrange $n+1$ linear clusters to build a two-dimensional cluster of width $n$. Fusion operations have to be applied at the black circles along the long linear cluster state. Free ends carrying spare overhead are shown as arrows.

Figure 10

The elementary linear optics tools for building two-dimensional structures from linear cluster chains. From top to bottom: a ${\sigma }_z$ measurement to remove unneeded nodes, a ${\sigma }_x$ measurement to create a redundancy encoded qubit in preparation of type-II fusion. The last figure shows the action of a fusion type-II attempt.