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/0506070 · Electronic Notes in Theoretical Computer Science

Distributed Measurement-based Quantum Computation

Vincent Danos, Ellie D’Hondt, Elham Kashefi, Prakash Panangaden

Published Mar 1, 2007• 36 citations
arXivHTMLPDF

Abstract

We develop a formal model for distributed measurement-based quantum computations, adopting an agent-based view, such that computations are described locally where possible. Because the network quantum state is in general entangled, we need to model it as a global structure, reminiscent of global memory in classical agent systems. Local quantum computations are described as measurement patterns. Since measurement-based quantum computation is inherently distributed, this allows us to extend naturally several concepts of the measurement calculus [V. Danos, E. Kashefi and P. Panangaden, The measurement calculus (2004), arXiv:quant-ph/0412135], a formal model for such computations. Our goal is to define an assembly language, i.e. we assume that computations are well-defined and we do not concern ourselves with verification techniques. The operational semantics for systems of agents is given by a probabilistic transition system, and we define operational equivalence in a way that it corresponds to the notion of bisimilarity. With this in place, we prove that teleportation is bisimilar to a direct quantum channel, and this also within the context of larger networks.

DOI
10.1016/j.entcs.2006.12.012

Related papers

The measurement calculus

Vincent Danos, Elham Kashefi, Prakash Panangaden

Measurement-based quantum computation has emerged from the physics community 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 is based on unitary operations. Among measurement-based quantum computation methods, the recently introduced one-way quantum computer [Raussendorf and Briegel 2001] stands out as fundamental. We develop a rigorous mathematical model underlying the one-way quantum computer and present a concrete syntax and operational semantics for programs, which we call patterns , and an algebra of these patterns derived from a denotational semantics. More importantly, we present a calculus for reasoning locally and compositionally about these patterns. We present a rewrite theory and prove a general standardization theorem which allows all patterns 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. Furthermore we formalize several other measurement-based models, for example, Teleportation, Phase and Pauli models and present compositional embeddings of them into and from the one-way model. This allows us to transfer all the theory we develop for the one-way model to these models. This shows that the framework we have developed has a general impact on measurement-based computation and is not just particular to the one-way quantum computer.

arXiv:0704.1263•Journal of the ACM•Apr 1, 2007•234 citations

Extended Measurement Calculus

Vincent Danos, 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•44 citations

Reasoning about quantum knowledge

Ellie D’Hondt, Prakash Panangaden

We construct a formal framework for investigating epistemic and temporal notions in the context of distributed quantum computation. While we rely on structures developed earlier, we stress that our notion of quantum knowledge makes sense more generally in any agent-based model for distributed quantum systems. Several arguments are given to support our view that an agent's possibility relation should not be based on the reduced density matrix, but rather on local classical states and local quantum operations. In this way, we are able to analyse distributed primitives such as superdense coding and teleportation, obtaining interesting conclusions as to how the knowledge of individual agents evolves. We show explicitly that the knowledge transfer in teleportation is essentially classical, in that eventually, the receiving agent knows that its state is equal to the initial state of the sender. The relevant epistemic statements for teleportation deal with this correlation rather than with the actual quantum state, which is unknown throughout the protocol.

arXiv:quant-ph/0507176•Jul 19, 2005•3 citations

Relations among quantum processes: bisimilarity and congruence

Marie Lalire

Full formal descriptions of algorithms making use of quantum principles must take into account both quantum and classical computing components, as well as communications between these components. Moreover, to model concurrent and distributed quantum computations and quantum communication protocols, communications over quantum channels that move qubits physically from one place to another must also be taken into account. Inspired by classical process algebras, which provide a framework for modelling cooperating computations, a process algebraic notation is defined. This notation provides a homogeneous style for formal descriptions of concurrent and distributed computations comprising both quantum and classical parts. Based upon an operational semantics that makes sure that quantum objects, operations and communications operate according to the postulates of quantum mechanics, an equivalence is defined among process states considered as having the same behaviour. This equivalence is a probabilistic branching bisimulation. From this relation, an equivalence on processes is defined. However, it is not a congruence because it is not preserved by parallel composition.

arXiv:quant-ph/0603274•Mathematical Structures in Computer Science•Jun 1, 2006•58 citations

QUANTUM PROGRAMMING

Ellie D’Hondt

The goal of this text is to advertise the need and support the development of quantum programming paradigms. By this we mean that we are essentially interested in an exploration of the expressiveness of quantum computations. We advocate that the history and evolution of classical programming paradigms is an essential learning ground and source of inspiration in establishing quantum programming paradigms. To clarify this we start with a historical explanation of the early development classical programming paradigms. Next we argue that quantum programming currently occurs at best at the level of assembly language. In particular we reason that the measurement calculus is the only suitable candidate for assembly-level quantum computations, giving an overview of its syntax, features and applications. We also provide a short overview of related work in quantum programming languages, which should further convince the reader of the uniqueness of the measurement calculus as a formal model. Since there is much activity in the area of distributed quantum computations we also explain where we are at in paradigm development for this type of computations. In particular we put forward as associated assembly language the distributed measurement calculus, again giving an overview of its syntax, features, applications and related work. We conclude with some ideas on how to move to higher-level quantum programming languages, in particular by focusing on correlations as the main driving force behind computations in arbitrary computing environments. This article is not technical, nor it is intended to be. The aim, rather, is to provide the reader with a general feel for the subject and to support our claims by example, while at the same time giving references to more specialised articles for the interested reader.

•Dec 1, 2011•0 citations

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
We develop a formal model for distributed measurement-based quantum computations, adopting an agent-based view, such that computations are described locally where possible. Because the network quantum state is in general entangled, we need to model it as a global structure, reminiscent of global memory in classical agent systems. Local quantum computations are described as measurement patterns. Since measurement-based quantum computation is inherently distributed, this allows us to extend naturally several concepts of the measurement calculus [V. Danos, E. Kashefi and P. Panangaden, The measurement calculus (2004), arXiv:quant-ph/0412135], a formal model for such computations. Our goal is to define an assembly language, i.e. we assume that computations are well-defined and we do not concern ourselves with verification techniques. The operational semantics for systems of agents is given by a probabilistic transition system, and we define operational equivalence in a way that it corresponds to the notion of bisimilarity. With this in place, we prove that teleportation is bisimilar to a direct quantum channel, and this also within the context of larger networks.
Measurement-based quantum computation has emerged from the physics community 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 is based on unitary operations. Among measurement-based quantum computation methods, the recently introduced one-way quantum computer [Raussendorf and Briegel 2001] stands out as fundamental. We develop a rigorous mathematical model underlying the one-way quantum computer and present a concrete syntax and operational semantics for programs, which we call patterns , and an algebra of these patterns derived from a denotational semantics. More importantly, we present a calculus for reasoning locally and compositionally about these patterns. We present a rewrite theory and prove a general standardization theorem which allows all patterns 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. Furthermore we formalize several other measurement-based models, for example, Teleportation, Phase and Pauli models and present compositional embeddings of them into and from the one-way model. This allows us to transfer all the theory we develop for the one-way model to these models. This shows that the framework we have developed has a general impact on measurement-based computation and is not just particular to the one-way quantum computer.
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.
We construct a formal framework for investigating epistemic and temporal notions in the context of distributed quantum computation. While we rely on structures developed earlier, we stress that our notion of quantum knowledge makes sense more generally in any agent-based model for distributed quantum systems. Several arguments are given to support our view that an agent's possibility relation should not be based on the reduced density matrix, but rather on local classical states and local quantum operations. In this way, we are able to analyse distributed primitives such as superdense coding and teleportation, obtaining interesting conclusions as to how the knowledge of individual agents evolves. We show explicitly that the knowledge transfer in teleportation is essentially classical, in that eventually, the receiving agent knows that its state is equal to the initial state of the sender. The relevant epistemic statements for teleportation deal with this correlation rather than with the actual quantum state, which is unknown throughout the protocol.
Full formal descriptions of algorithms making use of quantum principles must take into account both quantum and classical computing components, as well as communications between these components. Moreover, to model concurrent and distributed quantum computations and quantum communication protocols, communications over quantum channels that move qubits physically from one place to another must also be taken into account. Inspired by classical process algebras, which provide a framework for modelling cooperating computations, a process algebraic notation is defined. This notation provides a homogeneous style for formal descriptions of concurrent and distributed computations comprising both quantum and classical parts. Based upon an operational semantics that makes sure that quantum objects, operations and communications operate according to the postulates of quantum mechanics, an equivalence is defined among process states considered as having the same behaviour. This equivalence is a probabilistic branching bisimulation. From this relation, an equivalence on processes is defined. However, it is not a congruence because it is not preserved by parallel composition.
The goal of this text is to advertise the need and support the development of quantum programming paradigms. By this we mean that we are essentially interested in an exploration of the expressiveness of quantum computations. We advocate that the history and evolution of classical programming paradigms is an essential learning ground and source of inspiration in establishing quantum programming paradigms. To clarify this we start with a historical explanation of the early development classical programming paradigms. Next we argue that quantum programming currently occurs at best at the level of assembly language. In particular we reason that the measurement calculus is the only suitable candidate for assembly-level quantum computations, giving an overview of its syntax, features and applications. We also provide a short overview of related work in quantum programming languages, which should further convince the reader of the uniqueness of the measurement calculus as a formal model. Since there is much activity in the area of distributed quantum computations we also explain where we are at in paradigm development for this type of computations. In particular we put forward as associated assembly language the distributed measurement calculus, again giving an overview of its syntax, features, applications and related work. We conclude with some ideas on how to move to higher-level quantum programming languages, in particular by focusing on correlations as the main driving force behind computations in arbitrary computing environments. This article is not technical, nor it is intended to be. The aim, rather, is to provide the reader with a general feel for the subject and to support our claims by example, while at the same time giving references to more specialised articles for the interested reader.
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