The Measurement Calculus

Paper information (formal version: 2007, JACM 54(2); early preprint: 2004) — Vincent Danos, Elham Kashefi, and Prakash Panangaden. arXiv:0704.1263; early version arXiv:quant-ph/0412135

Work

The measurement calculus uses commands for entanglement, measurement, and classical dependencies to express measurement-based quantum computation, especially one-way computation. The paper gives the calculus an operational and denotational semantics and studies standardizing rewrites, so measurement order and signal dependencies can be analyzed systematically.

Contributions

• A uniform programming syntax for measurement patterns.
• Operational and denotational semantics for the measurement calculus.
• Standardization rewrites that reorganize measurement and dependency structure while preserving meaning.
• A compositional, reason-friendly representation for measurement-based quantum computation.

Limits

The calculus primarily describes idealized measurement-based computation; its semantics does not automatically cover noise, hardware calibration, compilation cost, or device measurement latency. Standardization is not an automatic optimizer for every program or a correctness proof for hardware execution. Resource estimates and fault-tolerant implementation require additional models.

Connections

It lifts measurement and classical control from Quantum Circuits into a rewriteable program calculus, and can be compared with the commands and superoperator semantics of QPL. Compared with A Categorical Semantics of Quantum Protocols, it exposes program syntax and execution order more directly; compared with Dagger Compact Closed Categories and Completely Positive Maps, it focuses on a program representation for ideal measurement-based computation.

Original paper

Vincent Danos, Elham Kashefi, and Prakash Panangaden, The Measurement Calculus, Journal of the ACM 54(2) (2007). arXiv:0704.1263; early version arXiv:quant-ph/0412135