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.
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.
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 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 which is based on unitary operations. Among measurement-based quantum computation methods, the recently introduced one-way quantum computer 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: 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.
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.
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, 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.
This thesis considers various paradigms of quantum computation in an attempt to understand the nature of the underlying physics. A standard approach is to consider unitary computation on pure input states, such that the outcome of the computation is determined by single computational basis measurement on the output state. It has been shown that there exists equivalent models of computation, such as measurement based quantum computing (MBQC), which provide insight into the role of entanglement and measurement. Furthermore, constraining or relaxing available resources can directly impacts the power of the computation, allowing one to gauge their role in the process. Here, we first extend known constructions such as Matrix Product States, MBQC and the oneclean qubit model to a mixed state formalism, in an attempt to develop computational models where noise acting on the physical resources, as might be experienced in laboratory settings, may be mapped to logical noise on the computation. Next, we introduce Measurement-Based Classical Computing, an essentially classical model of computation, wherein the complexity hard wired into probability distributions generated via quantum means yields surprising non classical results. Finally, we consider postselection the ability to discard displeasing measurement outcomes and argue that it may be used in a tame way, which does not provide a dramatic increase in computational power. From here, we develop a new Hamiltonian, based on a circuit to Hamiltonian construction, presenting evidence of QMA-hardness.
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.