The measurement calculus
The measurement calculus
复制标题
DOI：
10.1145/1219092.1219096
复制
发表时间：
2004-12
期刊：
影响因子：
--
通讯作者：
V. Danos;E. Kashefi;P. Panangaden
中科院分区：
文献类型：
--
作者：
V. Danos;E. Kashefi;P. Panangaden
基于测量的量子计算已从物理界出现，作为一种新的量子计算方法，其中测量概念是计算的主要驱动力。这与基于统一操作的更传统的电路模型形成鲜明对比。在基于测量的量子计算方法中，最近引入的单向量子计算机[Raussendorf and Briegel 2001]脱颖而出。我们开发了单向量子计算机基础的严格数学模型，并为程序提供了混凝土语法和操作语义，我们称之为模式，以及这些模式的代数，这些模式源自e notational语义。更重要的是，我们为在本地和构图上介绍了关于这些模式的演算。我们提出了一个重写理论，并证明了一般标准化定理，该定理允许所有模式以语义上等效的标准形式。标准化具有深远的后果：一种基于一开始就执行所有纠缠的新物理体系结构，通过公开测量和表达理论的依赖性结构来并行化。此外，我们将其他几种基于测量的模型形式化，例如传送，相位和Pauli模型，并呈现它们的组成嵌入到单向模型中。这使我们能够将为单向模型开发的所有理论传输到这些模型。这表明我们开发的框架对基于测量的计算有一般影响，而不仅仅是对单向量子计算机的特殊影响。
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.