We study how heralded qubit losses during the preparation of a two-dimensional cluster state, a universal resource state for one-way quantum computation, affect its computational power. Above the percolation threshold we present a polynomial-time algorithm that concentrates a universal cluster state, using resources that scale optimally in the size of the original lattice. On the other hand, below the percolation threshold, we show that single qubit measurements on the faulty lattice can be efficiently simulated classically. We observe a phase transition at the threshold when the amount of entanglement in the faulty lattice directly relevant to the computational power changes exponentially.
We study how heralded qubit losses during the preparation of a two-dimensional cluster state, a universal resource state for one-way quantum computation, affect its computational power. Above the percolation threshold we present a polynomial-time algorithm that concentrates a universal cluster state, using resources that scale optimally in the size of the original lattice. On the other hand, below the percolation threshold, we show that single qubit measurements on the faulty lattice can be efficiently simulated classically. We observe a phase transition at the threshold when the amount of entanglement in the faulty lattice directly relevant to the computational power changes exponentially.
In this paper, we build a framework allowing for a systematic investigation of the fundamental issue: ' Which quantum states serve as universal resources for measurement-based (one-way) quantum computation? ' We start our study by re-examining what is exactly meant by 'universality' in quantum computation, and what the implications are for universal one-way quantum computation. Given the framework of a measurement-based quantum computer, where quantum information is processed by local operations only, we find that the most general universal one-way quantum computer is one which is capable of accepting arbitrary classical inputs and producing arbitrary quantum outputs—we refer to this property as CQ-universality. We then show that a systematic study of CQ-universality in one-way quantum computation is possible by identifying entanglement features that are required to be present in every universal resource. In particular, we find that a large class of entanglement measures must reach its supremum on every universal resource. These insights are used to identify several families of states as being not universal, such as one-dimensional (1D) cluster states, Greenberger–Horne–Zeilinger (GHZ) states, W states, and ground states of non-critical 1D spin systems. Our criteria are strengthened by considering the efficiency of a quantum computation, and we find that entanglement measures must obey a certain scaling law with the system size for all efficient universal resources. This again leads to examples of non-universal resources, such as, e.g. ground states of critical 1D spin systems. On the other hand, we provide several examples of efficient universal resources, namely graph states corresponding to hexagonal, triangular and Kagome lattices. Finally, we consider the more general notion of encoded CQ-universality, where quantum outputs are allowed to be produced in an encoded form. Again we provide entanglement-based criteria for encoded universality. Moreover, we present a general procedure to construct encoded universal resources.
We show that the usefulness of the thermal state of a specific spin-lattice model for measurement-based quantum computing exhibits a transition between two distinct ``phases''---one in which every state is a universal resource for quantum computation, and another in which any local measurement sequence can be simulated efficiently on a classical computer. Remarkably, this transition in computational power does not coincide with any phase transition, classical, or quantum in the underlying spin-lattice model.
We investigate which entanglement resources allow universal measurement-based quantum computation via single-qubit operations. We find that any entanglement feature exhibited by the 2D cluster state must also be present in any other universal resource. We obtain a powerful criterion to assess the universality of graph states by introducing an entanglement measure which necessarily grows unboundedly with the system size for all universal resource states. Furthermore, we prove that graph states associated with 2D lattices such as the hexagonal and triangular lattice are universal, and obtain the first example of a universal nongraph state.
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.
We examine cluster states transformed by stochastic local operations and classical communication, as a resource for deterministic universal computation driven strictly by projective measurements. We identify circumstances under which such states in one dimension constitute resources for random-length single-qubit rotations, in one case quasideterministically ($N\ensuremath{-}U\ensuremath{-}N$ states) and in another probabilistically ($B\ensuremath{-}U\ensuremath{-}B$ states). In contrast to the cluster states, the $N\ensuremath{-}U\ensuremath{-}N$ states exhibit spin correlation functions that decay exponentially with distance, while the $B\ensuremath{-}U\ensuremath{-}B$ states can be arbitrarily locally pure. A two-dimensional square $N\ensuremath{-}U\ensuremath{-}N$ lattice is a universal resource for quasideterministic measurement-based quantum computation. Measurements on cubic $B\ensuremath{-}U\ensuremath{-}B$ states yield two-dimensional cluster states with bond defects, whose connectivity exceeds the percolation threshold for a critical value of the local purity.
Universal quantum computation can be achieved by simply performing single-qubit measurements on a highly entangled resource state. Resource states can arise from ground states of carefully designed two-body interacting Hamiltonians. This opens up an appealing possibility of creating them by cooling. The family of Affleck-Kennedy-Lieb-Tasaki (AKLT) states are the ground states of particularly simple Hamiltonians with high symmetry, and their potential use in quantum computation gives rise to a new research direction. Expanding on our prior work [T.-C. Wei, I. Affleck, and R. Raussendorf, Phys. Rev. Lett. 106, 070501 (2011)], we give a detailed analysis to explain why the spin-3/2 AKLT state on a two-dimensional honeycomb lattice is a universal resource for measurement-based quantum computation. Along the way, we also provide an alternative proof that the 1D spin-1 AKLT state can be used to simulate arbitrary one-qubit unitary gates. Moreover, we connect the quantum computational universality of 2D random graph states to their percolation property and show that these states whose graphs are in the supercritical (i.e., percolated) phase are also universal resources for measurement-based quantum computation.