

Regular Articles: New Paradigm toward Realizing Quantum Computers Measurementbased Quantum Computation and the Faulttolerant SystemAbstractQuantum computation provides us with a new form of information processing that surpasses current computer technology. In a new model of quantum computation, measurementbased quantum computation, the computation proceeds via simple measurements on previously prepared quantum entangled states. This model has attracted attention for its good potential for realizing quantum computers. This article reviews the basic concepts of measurementbased quantum computation and the elegant faulttolerant system called topological oneway quantum computation.
1. IntroductionThe principle of current information processing performed by computers and networks is based on the physics of classical electromagnetic dynamics. Information processing technology based on this principle has blossomed in the 20th century as electronics. Meanwhile, a new principle of physics, quantum dynamics, was discovered in the early 20th century for describing the world on the small scale: the scale of the smallest particles and subparticles. After a while, in the late 20th century, a new principle of information processing based on quantum physics started to be considered. As a result, groundbreaking information processing was found to be possible, such as efficient computation of prime factorization, unconditionally secure communication, and teleportation of quantum information [1]. However, quantum information processing is not easy to realize because the quantum states are difficult to manipulate precisely and are not stable for a long time; i.e., they easily decohere. A lot of study has been going on to achieve the breakthrough needed to realize quantum information processing. In this article, I review a new computational model for achieving quantum computers called measurementbased quantum computation. Section 2 describes the basic concepts and advantages of measurementbased quantum computation and compares it with the conventional computational model: the circuit model. Section 3 describes an important new faulttolerant system for quantum computation, topological quantum computing, that can be performed on the basis of the measurementbased quantum computation model in an elegant way. Section 4 describes research on measurementbased quantum computation at NTT laboratories. Section 5 mentions the outlook for future research. 2. Measurementbased quantum computationFrom the beginning of the study of quantum computation in around 1990, the realization of quantum computers has been considered on the basis of a standard computational model: the circuit model (Fig. 1). It has a few basic gates such as singlequbit (quantum bit) rotation gates and an important twoqubit interaction gate: the controlledNOT gate. The input state to the combination of the basic gates achieves universal quantum computation. However, one of the main difficulties in realizing quantum computers is how to make the controlledNOT gate. It is not easy to obtain an appropriate interaction between particles such as atoms or photons. To date, many experiments toward the controlledNOT gate have been performed.
A whole new paradigm for quantum computers started in around 2000. Researchers began to reconsider the computational model in order to utilize the unique features of quantum physics. They thought that there might be a completely different computational model for quantum computers than the one based on the idea of the classical circuit model because the physics is completely different from classical physics. The great feature of quantum states is the existence of entanglement. A breakthrough idea for utilizing entanglement for quantum computers was described by Gottesman and Chuang [2]. They proposed a new model of quantum gates that operate by means of quantum teleportation. Quantum teleportation is a quantum information transmission process that consumes the quantum entanglement in compensation for sending quantum information. We can obtain the output of a controlledNOT gate by operating quantum teleportation using a special entangled state (Fig. 2). The entangled state can be regarded as a computational resource for the quantum gate.
A more sophisticated computational model based on the teleportationbased gate is oneway quantum computation (Fig. 3) [3]. First, a special entangled state, called a cluster state, is prepared beforehand. After that, one only has to perform singlequbit measurement on the cluster state and one can then perform universal quantum computation, in which the entangled cluster state plays the roles of quantum gates and the information flow. The cluster state is a specific entangled state and it can be prepared before computation is started. The entanglement preparation is easier than computation because the target state is known beforehand. Actually, we can even utilize a nondeterministic gate having a low success probability in order to generate the entangled resource [4], [5]. Once the computational resource of the entanglement has been prepared, one only needs to perform singlequbit measurements; this is a very simple task compared with twoqubit interaction gates, so the new computational model significantly decreases the difficulty of realizing quantum computers.
3. Faulttolerant topological quantum computationWe also need to protect the quantum computing from decoherence and from the effects of several kinds of noise. Fortunately, error correction codes are available for quantum computing and we can perform faulttolerant quantum computing by applying an error correction procedure appropriately during computation. A wellknown faulttolerant system based on the circuit model used a quantum linear code and concatenated codes (Fig. 4) [6], [7]. A standard quantum linear code encodes a single qubit into several qubits. It can tolerate a single bitflip and phaseflip error, but if more than one error occurs in the encoded state, then the error correction does not work well. Concatenated coding solves this problem. It recursively uses the linear code as shown in Fig. 4. It provides greater error tolerance if the error rate per basic computational unit is less than a certain threshold. Reliable quantum computing can be executed by using code concatenation of sufficient depth with the error rate below the threshold. The threshold of faulttolerant systems based on the circuit model is known to be around 1% [7]. However, it is assumed here that any quantum gate can be achieved between widely separated particles, but the interaction between particles normally becomes weaker with increasing distance between particles. Thus, this assumption is unnatural from the physical viewpoint. Though we can rewrite the quantum gate between spatially separate particles into combinations of quantum gates between nearestneighbor sites, the number of consumed gates becomes larger in that case and the threshold of the faulttolerant system becomes significantly small.
Considering the shortage of concatenated codes for faulttolerant systems, elegant quantum codes treating physical nearestneighbor interactions were proposed [8]. They are called topological codes or surface codes; the name originates from the topological nature of the code. The important point is that a topological code uses only nearestneighbor interactions. This is a realistic scenario compared with the circuit model. An example of a twodimensional (2D) topological code, toric code, is shown in Fig. 5. The qubits are on the edges of the 2D lattice and entangled as a topological code state. In toric code, the qubits on the endpoints of the 2D lattice are identical to those at the other sides; that is, the 2D lattice is on the surface of a torus, which gives us the degrees of freedom for encoding logical qubits. The entangled code state can be prepared through the use of only nearestneighbor interactions and the errorchecking operations can also be operated by nearestneighbor interactions and singlesite measurements. The encoding size can be enlarged by expanding the lattice size. Toric code can also be rewritten on a square lattice with boundaries by constructing the equivalent for the hole of the torus and introducing the same topology. That makes it easier to prepare multiple logical qubits. Topological faulttolerant quantum computation is known to be possible in a 2D square lattice with nearestneighbor interactions during computation, where the obtained noise threshold is 0.75% [9]. Moreover, a special form of 3D cluster state becomes a resource of faulttolerant topological oneway quantum computation with noise threshold of 0.11% [10]. In this case, we can perform faulttolerant quantum computing with only singlequbit measurements after preparing the 3D cluster states. The thresholds can be improved by devising better encoding and decoding methods [11], [12]. Recently, the important realistic case of errors with a high loss rate [13] and of nondeterministic entangling gates [14], [15] have also been investigated.
4. NTT research on measurementbased quantum computationHere, I briefly describe research on measurementbased quantum computation at NTT Laboratories. In 2008, my colleagues and I experimentally demonstrated a simple scheme for generating a fourphoton entangled cluster state and basic operations for oneway quantum computing using the produced state [16]. We showed that the output state fidelities surpass classical bounds, which indicates that the entanglement in the produced state essentially contributes to the quantum operation. However, the obtained fidelities have not been sufficiently high for faulttolerant quantum computation. In order to perform quantum computing faulttolerantly, we must improve the gate fidelities experimentally. At the same time, it is important to improve the theory of faulttolerant quantum computing so that we can utilize realistic imperfect devices. For example, in linear optics, twoqubit gates are intrinsically nondeterministic owing to the linearity of the interaction [4], [17]. In other systems, it is also often the case that a large amount of error such as photon loss and detector inefficiency can be detected in heralded ways, and one can postselect successful events [16], [18]. In 2010, we proposed a scalable way to construct a 3D cluster state for faulttolerant topological oneway quantum computation using such nondeterministic twoqubit gates with a low success probability [14]. We showed that faulttolerant topological oneway quantum computation can be performed with a twoqubit gate success probability of less than 1/2 provided that the unheralded error probability of the twoqubit gate is sufficiently small. This work showed for the first time that realistic imperfect nondeterministic gates with a success probability of less than 1/2 can also be utilized for faulttolerant quantum computing. The other issue in measurementbased quantum computation, reducing the computational resources, is discussed in the second Regular Article [19], which treats a different model of measurementbased quantum computation. 5. Future outlookHaving reviewed the concepts and favorable features of measurementbased quantum computation and the faulttolerant system, I would like to mention the outlook for future research. On the theoretical side, an important task is to find a more realistic physical model for realizing measurementbased quantum computation. There have been studies for finding Hamiltonians whose ground states are universal resources for measurementbased quantum computation [20], [21]. On the experimental side, some demonstrations of measurementbased quantum computation have been performed [16], [18], [22]. However, a lot of problems remain to be overcome. The most important one is how to obtain scalability in quantum computers. For optical quantum computation, a new highefficiency singlephoton source is necessary [23]. A promising candidate for preparing a large entangled resource for measurementbased quantum computation is ultracold atomic gas in an optical lattice [24]. The important issue for future work on the optical lattice is singlesite addressing [25], [26]. Another important candidate is the use of solidstate artificial atoms such as quantum dots or dopants in solids for stationary qubits and the use of atomphoton interactions with cavity quantum electrodynamics for the quantum gates [27]. In conclusion, measurementbased quantum computation provides us with great features toward realizing quantum computers and has high potential for both theoretical and experimental research in the future. References
