2021/09/06 by Robert Rand, Aarthi Sundaram, Kartik Singhal +1 · 2 citations
Computer Science · Physics and Astronomy · #cs.LO #cs.ET #cs.PL #quant-ph
paper · pdf · doi:10.4204/eptcs.340.14
published as EPTCS 340, 2021, pp. 279-290 · In Proceedings QPL 2020, arXiv:2109.01534. arXiv admin note: substantial text overlap with arXiv:2101.08939
arxiv created 2021/09/06 · arxiv updated 2021/09/07
The Heisenberg representation of quantum operators provides a powerful technique for reasoning about quantum circuits, albeit those restricted to the common (non-universal) Clifford set H, S and CNOT. The Gottesman-Knill theorem showed that we can use this representation to efficiently simulate Clifford circuits. We show that Gottesman's semantics for quantum programs can be treated as a type system, allowing us to efficiently characterize a common subset of quantum programs. We also show that it can be extended beyond the Clifford set to partially characterize a broad range of programs. We apply these types to reason about separable states and the superdense coding algorithm.