Informatics Report Series


Report   

EDI-INF-RR-1165


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:The Measurement Calculus
Authors: Vincent Danos ; Elham Kashefi ; Prakash Panandagen
Date:Apr 2004
Publication Title:Journal of ACM
Publisher:ACM
Publication Type:Journal Article Publication Status:Published
Volume No:54 (2)
DOI:10.1145/1219092.1219096 ISBN/ISSN:0004-5411
Abstract:
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 for 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 exampled, Teleportation, Phase and Pauli models and present compoisitional 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.
Links To Paper
No links available
Bibtex format
@Article{EDI-INF-RR-1165,
author = { Vincent Danos and Elham Kashefi and Prakash Panandagen },
title = {The Measurement Calculus},
journal = {Journal of ACM},
publisher = {ACM},
year = 2004,
month = {Apr},
volume = {54 (2)},
doi = {10.1145/1219092.1219096},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh