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.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.

arXiv:2109.02197Electronic Proceedings in Theoretical Computer ScienceSep 6, 202110 citations

Analysis of quantum programs

Mingsheng Ying

Elsevier eBooksJan 1, 20242 citations

Static Analysis of Quantum Programs via Gottesman Types

Robert W. Rand, Aarthi Sundaram, Kartik Singhal +1 more

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 apply this primarily towards tracking entanglement in programs, showing how superdense coding and GHZ circuits entangle and disentangle qubits and how to safely dispose of ancillae. We demonstrate the efficiency of our typechecking algorithm both for simple deductions and those involving entanglement and measurement.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 apply this primarily towards tracking entanglement in programs, showing how superdense coding and GHZ circuits entangle and disentangle qubits and how to safely dispose of ancillae. We demonstrate the efficiency of our typechecking algorithm both for simple deductions and those involving entanglement and measurement.

Jan 22, 20211 citation

Analysis of quantum programs

Mingsheng Ying

Elsevier eBooksJan 1, 201615 citations

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 apply this primarily towards tracking entanglement in programs, showing how superdense coding and GHZ circuits entangle and disentangle qubits and how to safely dispose of ancillae. We demonstrate the efficiency of our typechecking algorithm both for simple deductions and those involving entanglement and measurement.