Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0508124

An introduction to measurement based quantum computation

Richard Jozsa

Published Aug 17, 2005• 124 citations
arXivHTMLPDF

Abstract

In the formalism of measurement based quantum computation we start with a given fixed entangled state of many qubits and perform computation by applying a sequence of measurements to designated qubits in designated bases. The choice of basis for later measurements may depend on earlier measurement outcomes and the final result of the computation is determined from the classical data of all the measurement outcomes. This is in contrast to the more familiar gate array model in which computational steps are unitary operations, developing a large entangled state prior to some final measurements for the output. Two principal schemes of measurement based computation are teleportation quantum computation (TQC) and the so-called cluster model or one-way quantum computer (1WQC). We will describe these schemes and show how they are able to perform universal quantum computation. We will outline various possible relationships between the models which serve to clarify their workings. We will also discuss possible novel computational benefits of the measurement based models compared to the gate array model, especially issues of parallelisability of algorithms.

DOI
10.48550/arxiv.quant-ph/0508124

Related papers

Focus on Measurement-Based Quantum Information Processing

Terry Rudolph, Jian-Wei Pan

The last two decades have witnessed the rapid growth of quantum information processing as an active field of multidisciplinary science and technology. Tremendous theoretical and experimental progress has been made in quantum communication and quantum computation, and it seems clear that some of this progress will soon result in practical applications outside the laboratory. Quantum computation aims to build a quantum computer and to explore the origins and limits of quantum computing power. The original circuit model of a quantum computer, due to Deutsch, has a strong formal similarity with the circuit model of a classical computer. Both models depict a computation as processing via the wiring of a number of fiducial gates, each of which dynamically couples a small number of input (qu)bits in a controlled manner. In other words, unitary evolution is the basic mechanism of information processing in the circuit model of quantum computers. Starting with a given fixed state of many qubits, measurement based quantum computation (MBQC) processes information by applying a sequence of measurements to designated qubits in designated bases. This is remarkable, given the probabilistic nature of quantum measurement and the murky physical status of the dynamics of 'wavefunction collapse'. The final result of the computation is determined from the classical data of all the measurement outcomes. There exist two principle models: the teleportation based model and the 'one-way quantum computer' of 'cluster state computation'. The formalism of cluster states has proven to be a powerful way of describing the essential entanglement resources needed to perform quantum information processing. Unlike the circuit model, the MBQC models have no natural classical counterpart. There are a number of physical architectures for which measurements on the relevant systems are more easily performed than controlled unitary evolution. Moreover, it appears the MBQC models can offer novel computational benefits, especially regarding issues of fault-tolerance and parallelizability of algorithms. As a result, the theory of MBQC is now shaping the latest experimental proposals across the full spectrum of quantum information processing technologies. Naturally, understanding the scope of measurement based quantum computation is also yielding many insights into what is necessary (as opposed to merely sufficient) for us to harness the power of quantum computers. Quantum communication aims to offer efficient and secure ways of information exchange, directly based on quantum mechanics. Photons serve as natural information carriers, owing to their robustness against decoherence. A major problem for photonic communication systems is due to photon loss. It turns out that this difficulty can be overcome by the quantum repeater, a measurement-based technique. The basic idea is to divide the transmission channel into many segments and perform some quantum measurement on each segment. Additional measurement-based protocols and technologies have also been demonstrated to improve the quality of quantum communication, such as entanglement swapping and purification. The articles in this invited Focus Issue cover topics both in measurement-based quantum communication and computation, but the emphasis is given to quantum computation. A significant number of articles deal with the preparation of cluster states, the experimental realization of a one-way quantum computer, and the associated efficiency and benefits. We hope that you will find that some of these new results are of interest to you, and further hope that the issue will increase your interest in this interdisciplinary research field if you are a non-expert. Focus on Measurement-Based Quantum Information Processing Contents A proof-of-principle experiment of eliminating photon-loss errors in cluster states Wei-Bo Gao, Xiao-Qi Zhou, Jin Zhang, Tao Yang and Jian-Wei Pan Continuous variable multipartite entanglement and optical implementations of quantum communication networks Yimin Lian, Changde Xie and Kunchi Peng Generalized flow and determinism in measurement-based quantum computation Daniel E Browne, Elham Kashefi, Mehdi Mhalla and Simon Perdrix The entanglement of the four-photon cluster state C Schmid, N Kiesel, W Wieczorek and H Weinfurter Optical zeno gate: bounds for fault tolerant operation Patrick M Leung and Timothy C Ralph Towards experimental entanglement connection with atomic ensembles in the single excitation regime Julien Laurat, Chin-wen Chou, Hui Deng, Kyung Soo Choi, Daniel Felinto, Hugues de Riedmatten and H J Kimble Towards minimal resources of measurement-based quantum computation Simon Perdrix Experimental realization of a quantum game on a one-way quantum computer Robert Prevedel, Andre Stefanov, Philip Walther and Anton Zeilinger Fundamentals of universality in one-way quantum computation M Van den Nest, W Dur, A Miyake and H J Briegel Loss tolerant linear optical quantum memory by measurement-based quantum computing Michael Varnava, Daniel E Browne and Terry Rudolph Graph state generation with noisy mirror-inverting spin chains Stephen R Clark, Alexander Klein, Martin Bruderer and Dieter Jaksch One-way quantum computing in adecoherence-free subspace M S Tame, M Paternostro and M S Kim Cluster state preparation using gates operating at arbitrary success probabilities K Kieling, D Gross and J Eisert Topological fault-tolerance in cluster state quantum computation R Raussendorf, J Harrington and K Goyal Strategies for the preparation of large cluster states using non-deterministic gates Peter P Rohde and Sean D Barrett A repeat-until-success quantum computing scheme A Beige, Y L Lim and L C Kwek Efficient growth of complex graph states via imperfect path erasure Earl T Campbell, Joseph Fitzsimons, Simon C Benjamin and Pieter Kok Investigation of a single-photon source based on quantum interference T B Pittman, J D Franson and B C Jacobs Entanglement and local information access for graph states Damian Markham, Akimasa Miyake and Shashank Virmani The efficiencies of generating cluster states with weak nonlinearities Sebastien G R Louis, Kae Nemoto, W J Munro and T P Spiller A direct approach to fault-tolerance in measurement-based quantum computation via teleportation Marcus Silva, Vincent Danos, Elham Kashefi and Harold Ollivier Experimental ancilla-assisted qubit transmission against correlated noise T Yamamoto, R Nagase, J Shimamura, S K Ozdemir, M Koashi and N Imoto Terry Rudolph, Imperial College, London, UK Jian-Wei Pan, University of Science and Technology of China, Hefei, People's Republic of China and Universitat Heidelberg, Germany

New Journal of Physics•Jun 29, 2007•2 citations

Fault-tolerant measurement-based quantum computing

Debbie Leung

Introduction In the standard model of quantum computation [D95], some simple quantum state is prepared and evolved by a partially ordered set of unitary gates, and finally is measured in the computation basis. Up until the late 1990s, transformations that deviate from unitarity were commonly associated with irreversibility, and thus incoherence and harm induced in the quantum data of interest. However, this viewpoint was challenged by three notable results: (1) teleportation [BBC+93], (2) syndrome measurements [S95, S96e], and (3) the fault-tolerant Toffoli and π/8-gate constructions [S96b, BMP+99]. In these schemes, well-designed measurements project the quantum data of interest onto a subspace of the original ambient space for each outcome, up to some known unitary transformation that is either reversible (and harmless) or intended. Subsequently, researchers found many useful error-correction procedures and unitary gates that rely heavily on measurements. Two “measurement models” of quantum computation were proposed in the early 2000s that make extreme use of measurements. In the cluster model [RB01], any quantum computation can be performed by applying a partially time-ordered set of single-qubit measurements on a certain entangled state. The state must be of appropriate size, but is otherwise independent of the computation. The related graph state model [RBB03] uses an initial state that depends on the computation itself. In the seemingly different teleportation-based model [N03, L01a, L04], any quantum computation can be implemented by applying one- or two-qubit nondemolition measurements on an arbitrary initial state, so as to “teleport” each gate in the simulated circuit.

Cambridge University Press eBooks•Sep 5, 2013•0 citations

Physical Realization of Measurement Based Quantum Computation

Muhammad Kashif, Saif M. Al-Kuwari

Quantum computers, leveraging the principles of quantum mechanics, hold the potential to surpass classical computers in numerous applications, with implications across various domains. Besides the well-known gate model, Measurement-based Quantum Computation (MBQC) is another promising computational approach to achieve universal quantum computation. In MBQC, large ensembles of qubits are prepared in a highly entangled cluster state, forming the basis for executing quantum computations through sequential measurements. Cluster states are realized using both continuous variables (CV) and discrete variables (DV) techniques. In the CV-based methods, Frequency Domain Multiplexing (FDM), Time Domain Multiplexing (TDM), Spatial Domain Multiplexing (SDM), and hybrid schemes are employed. This paper thoroughly discusses and compares these approaches, elucidating their strengths and limitations. Additionally, the generation of photonic cluster states in DV is explored and some recent results are reported. Some recent state-of-the-art advancements in photonic and superconducting qubits entanglement, which can potentially serve as cluster states, are also presented. Finally, we highlight the approach that exhibits the most promising characteristics for achieving efficient cluster state realization in the context of MBQC.

arXiv:2301.03022•IEEE Access•Jan 1, 2023•10 citations

Extended Measurement Calculus

Vincent Danos A, Elham Kashefi, Prakash Panangaden +1 more

Measurement-based quantum computation (MBQC) has emerged as a new approach to quantum computation where the notion of measurement is the main driving force of computation. This is in contrast with the more traditional circuit model that takes unitary operations as fundamental. Among measurement-based quantum computation methods the recently introduced one-way quantum computer stands out as basic and fundamental. The key idea is to start from an entangled state and then use measurements and one-qubit unitaries, which may be dependent on the outcomes of measurements, to guide the computation. The main point is that one never has to perform unitaries on more than one qubit at a time after the initial preparation of an entangled state. The “programs” that one writes in this model are traditionally called “patterns.” In this chapter, we develop a rigorous mathematical model underlying measurement-based quantum computation. We give syntax, operational semantics, denotational semantics, and an algebra of programs derived from the denotational semantics. We also present a rewrite theory and prove a general standardization theorem that allows all programs to be put in a semantically equivalent standard form. Standardization has far-reaching consequences: a new physical architecture based on performing all the entanglement in the beginning, parallelization by exposing the dependency structure of measurements, and expressiveness theorems. We use our general measurement calculus not just to formalize the one-way model but also several other measurement-based models, e.g., Teleportation, Phase, and Pauli models, and present compositional embeddings of them into and from the one-way model.

Cambridge University Press eBooks•Nov 30, 2009•38 citations

1-qubit versus 2-qubit measurement based quantum computing

Vincent Danos A, Elham Kashefi, Prakash Panangaden

We present a comprehensive and universal quantum computing model based on 2-qubit measurements (TQC), which embeds trivially in a model based on 1-qubit measurements known as the one-way model (1WQC). One inherits through this embedding a calculus whereby each TQC computing pattern can be put in a standard form where entanglement is done first, then measurement, then local corrections.

•Jan 1, 2005•3 citations

Quantum computing via measurements only

Robert Raussendorf, Hans J. Briegel

A quantum computer promises efficient processing of certain computational tasks that are intractable with classical computer technology. While basic principles of a quantum computer have been demonstrated in the laboratory, scalability of these systems to a large number of qubits, essential for practical applications such as the Shor algorithm, represents a formidable challenge. Most of the current experiments are designed to implement sequences of highly controlled interactions between selected particles (qubits), thereby following models of a quantum computer as a (sequential) network of quantum logic gates. Here we propose a different model of a scalable quantum computer. In our model, the entire resource for the quantum computation is provided initially in form of a specific entangled state (a so-called cluster state) of a large number of qubits. Information is then written onto the cluster, processed, and read out form the cluster by one-particle measurements only. The entangled state of the cluster thus serves as a universal substrate for any quantum computation. Cluster states can be created efficiently in any system with a quantum Ising-type interaction (at very low temperatures) between two-state particles in a lattice configuration.

arXiv:quant-ph/0010033•Oct 7, 2000•57 citations
In the formalism of measurement based quantum computation we start with a given fixed entangled state of many qubits and perform computation by applying a sequence of measurements to designated qubits in designated bases. The choice of basis for later measurements may depend on earlier measurement outcomes and the final result of the computation is determined from the classical data of all the measurement outcomes. This is in contrast to the more familiar gate array model in which computational steps are unitary operations, developing a large entangled state prior to some final measurements for the output. Two principal schemes of measurement based computation are teleportation quantum computation (TQC) and the so-called cluster model or one-way quantum computer (1WQC). We will describe these schemes and show how they are able to perform universal quantum computation. We will outline various possible relationships between the models which serve to clarify their workings. We will also discuss possible novel computational benefits of the measurement based models compared to the gate array model, especially issues of parallelisability of algorithms.
The last two decades have witnessed the rapid growth of quantum information processing as an active field of multidisciplinary science and technology. Tremendous theoretical and experimental progress has been made in quantum communication and quantum computation, and it seems clear that some of this progress will soon result in practical applications outside the laboratory. Quantum computation aims to build a quantum computer and to explore the origins and limits of quantum computing power. The original circuit model of a quantum computer, due to Deutsch, has a strong formal similarity with the circuit model of a classical computer. Both models depict a computation as processing via the wiring of a number of fiducial gates, each of which dynamically couples a small number of input (qu)bits in a controlled manner. In other words, unitary evolution is the basic mechanism of information processing in the circuit model of quantum computers. Starting with a given fixed state of many qubits, measurement based quantum computation (MBQC) processes information by applying a sequence of measurements to designated qubits in designated bases. This is remarkable, given the probabilistic nature of quantum measurement and the murky physical status of the dynamics of 'wavefunction collapse'. The final result of the computation is determined from the classical data of all the measurement outcomes. There exist two principle models: the teleportation based model and the 'one-way quantum computer' of 'cluster state computation'. The formalism of cluster states has proven to be a powerful way of describing the essential entanglement resources needed to perform quantum information processing. Unlike the circuit model, the MBQC models have no natural classical counterpart. There are a number of physical architectures for which measurements on the relevant systems are more easily performed than controlled unitary evolution. Moreover, it appears the MBQC models can offer novel computational benefits, especially regarding issues of fault-tolerance and parallelizability of algorithms. As a result, the theory of MBQC is now shaping the latest experimental proposals across the full spectrum of quantum information processing technologies. Naturally, understanding the scope of measurement based quantum computation is also yielding many insights into what is necessary (as opposed to merely sufficient) for us to harness the power of quantum computers. Quantum communication aims to offer efficient and secure ways of information exchange, directly based on quantum mechanics. Photons serve as natural information carriers, owing to their robustness against decoherence. A major problem for photonic communication systems is due to photon loss. It turns out that this difficulty can be overcome by the quantum repeater, a measurement-based technique. The basic idea is to divide the transmission channel into many segments and perform some quantum measurement on each segment. Additional measurement-based protocols and technologies have also been demonstrated to improve the quality of quantum communication, such as entanglement swapping and purification. The articles in this invited Focus Issue cover topics both in measurement-based quantum communication and computation, but the emphasis is given to quantum computation. A significant number of articles deal with the preparation of cluster states, the experimental realization of a one-way quantum computer, and the associated efficiency and benefits. We hope that you will find that some of these new results are of interest to you, and further hope that the issue will increase your interest in this interdisciplinary research field if you are a non-expert. Focus on Measurement-Based Quantum Information Processing Contents A proof-of-principle experiment of eliminating photon-loss errors in cluster states Wei-Bo Gao, Xiao-Qi Zhou, Jin Zhang, Tao Yang and Jian-Wei Pan Continuous variable multipartite entanglement and optical implementations of quantum communication networks Yimin Lian, Changde Xie and Kunchi Peng Generalized flow and determinism in measurement-based quantum computation Daniel E Browne, Elham Kashefi, Mehdi Mhalla and Simon Perdrix The entanglement of the four-photon cluster state C Schmid, N Kiesel, W Wieczorek and H Weinfurter Optical zeno gate: bounds for fault tolerant operation Patrick M Leung and Timothy C Ralph Towards experimental entanglement connection with atomic ensembles in the single excitation regime Julien Laurat, Chin-wen Chou, Hui Deng, Kyung Soo Choi, Daniel Felinto, Hugues de Riedmatten and H J Kimble Towards minimal resources of measurement-based quantum computation Simon Perdrix Experimental realization of a quantum game on a one-way quantum computer Robert Prevedel, Andre Stefanov, Philip Walther and Anton Zeilinger Fundamentals of universality in one-way quantum computation M Van den Nest, W Dur, A Miyake and H J Briegel Loss tolerant linear optical quantum memory by measurement-based quantum computing Michael Varnava, Daniel E Browne and Terry Rudolph Graph state generation with noisy mirror-inverting spin chains Stephen R Clark, Alexander Klein, Martin Bruderer and Dieter Jaksch One-way quantum computing in adecoherence-free subspace M S Tame, M Paternostro and M S Kim Cluster state preparation using gates operating at arbitrary success probabilities K Kieling, D Gross and J Eisert Topological fault-tolerance in cluster state quantum computation R Raussendorf, J Harrington and K Goyal Strategies for the preparation of large cluster states using non-deterministic gates Peter P Rohde and Sean D Barrett A repeat-until-success quantum computing scheme A Beige, Y L Lim and L C Kwek Efficient growth of complex graph states via imperfect path erasure Earl T Campbell, Joseph Fitzsimons, Simon C Benjamin and Pieter Kok Investigation of a single-photon source based on quantum interference T B Pittman, J D Franson and B C Jacobs Entanglement and local information access for graph states Damian Markham, Akimasa Miyake and Shashank Virmani The efficiencies of generating cluster states with weak nonlinearities Sebastien G R Louis, Kae Nemoto, W J Munro and T P Spiller A direct approach to fault-tolerance in measurement-based quantum computation via teleportation Marcus Silva, Vincent Danos, Elham Kashefi and Harold Ollivier Experimental ancilla-assisted qubit transmission against correlated noise T Yamamoto, R Nagase, J Shimamura, S K Ozdemir, M Koashi and N Imoto Terry Rudolph, Imperial College, London, UK Jian-Wei Pan, University of Science and Technology of China, Hefei, People's Republic of China and Universitat Heidelberg, Germany
Introduction In the standard model of quantum computation [D95], some simple quantum state is prepared and evolved by a partially ordered set of unitary gates, and finally is measured in the computation basis. Up until the late 1990s, transformations that deviate from unitarity were commonly associated with irreversibility, and thus incoherence and harm induced in the quantum data of interest. However, this viewpoint was challenged by three notable results: (1) teleportation [BBC+93], (2) syndrome measurements [S95, S96e], and (3) the fault-tolerant Toffoli and π/8-gate constructions [S96b, BMP+99]. In these schemes, well-designed measurements project the quantum data of interest onto a subspace of the original ambient space for each outcome, up to some known unitary transformation that is either reversible (and harmless) or intended. Subsequently, researchers found many useful error-correction procedures and unitary gates that rely heavily on measurements. Two “measurement models” of quantum computation were proposed in the early 2000s that make extreme use of measurements. In the cluster model [RB01], any quantum computation can be performed by applying a partially time-ordered set of single-qubit measurements on a certain entangled state. The state must be of appropriate size, but is otherwise independent of the computation. The related graph state model [RBB03] uses an initial state that depends on the computation itself. In the seemingly different teleportation-based model [N03, L01a, L04], any quantum computation can be implemented by applying one- or two-qubit nondemolition measurements on an arbitrary initial state, so as to “teleport” each gate in the simulated circuit.
Quantum computers, leveraging the principles of quantum mechanics, hold the potential to surpass classical computers in numerous applications, with implications across various domains. Besides the well-known gate model, Measurement-based Quantum Computation (MBQC) is another promising computational approach to achieve universal quantum computation. In MBQC, large ensembles of qubits are prepared in a highly entangled cluster state, forming the basis for executing quantum computations through sequential measurements. Cluster states are realized using both continuous variables (CV) and discrete variables (DV) techniques. In the CV-based methods, Frequency Domain Multiplexing (FDM), Time Domain Multiplexing (TDM), Spatial Domain Multiplexing (SDM), and hybrid schemes are employed. This paper thoroughly discusses and compares these approaches, elucidating their strengths and limitations. Additionally, the generation of photonic cluster states in DV is explored and some recent results are reported. Some recent state-of-the-art advancements in photonic and superconducting qubits entanglement, which can potentially serve as cluster states, are also presented. Finally, we highlight the approach that exhibits the most promising characteristics for achieving efficient cluster state realization in the context of MBQC.
Measurement-based quantum computation (MBQC) has emerged as a new approach to quantum computation where the notion of measurement is the main driving force of computation. This is in contrast with the more traditional circuit model that takes unitary operations as fundamental. Among measurement-based quantum computation methods the recently introduced one-way quantum computer stands out as basic and fundamental. The key idea is to start from an entangled state and then use measurements and one-qubit unitaries, which may be dependent on the outcomes of measurements, to guide the computation. The main point is that one never has to perform unitaries on more than one qubit at a time after the initial preparation of an entangled state. The “programs” that one writes in this model are traditionally called “patterns.” In this chapter, we develop a rigorous mathematical model underlying measurement-based quantum computation. We give syntax, operational semantics, denotational semantics, and an algebra of programs derived from the denotational semantics. We also present a rewrite theory and prove a general standardization theorem that allows all programs to be put in a semantically equivalent standard form. Standardization has far-reaching consequences: a new physical architecture based on performing all the entanglement in the beginning, parallelization by exposing the dependency structure of measurements, and expressiveness theorems. We use our general measurement calculus not just to formalize the one-way model but also several other measurement-based models, e.g., Teleportation, Phase, and Pauli models, and present compositional embeddings of them into and from the one-way model.
A quantum computer promises efficient processing of certain computational tasks that are intractable with classical computer technology. While basic principles of a quantum computer have been demonstrated in the laboratory, scalability of these systems to a large number of qubits, essential for practical applications such as the Shor algorithm, represents a formidable challenge. Most of the current experiments are designed to implement sequences of highly controlled interactions between selected particles (qubits), thereby following models of a quantum computer as a (sequential) network of quantum logic gates. Here we propose a different model of a scalable quantum computer. In our model, the entire resource for the quantum computation is provided initially in form of a specific entangled state (a so-called cluster state) of a large number of qubits. Information is then written onto the cluster, processed, and read out form the cluster by one-particle measurements only. The entangled state of the cluster thus serves as a universal substrate for any quantum computation. Cluster states can be created efficiently in any system with a quantum Ising-type interaction (at very low temperatures) between two-state particles in a lattice configuration.