.png){kind=icon}
.png){kind=icon}
Return
Hadamard-Pi: Equational Quantum Programming
.png){kind=icon}
PRE
AI
DOI：10.1145/3776647.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Quantum computing offers advantages over classical computation, yet the precise features that set the two apart remain unclear. In the standard quantum circuit model, adding a 1-qubit basis-changing gate-commonly chosen to be the Hadamard gate-to a universal set of classical reversible gates yields computationally universal quantum computation. However, the computational behaviours enabled by this addition are not fully characterised. We give such a characterisation by introducing a small quantum programming language extending the universal classical reversible programming language Pi with a single primitive corresponding to the Hadamard gate. The language comes equipped with a sound and complete categorical semantics that is specified by a purely equational theory. Completeness is shown by means of a novel finite presentation, and a corresponding synthesis algorithm, for the groups of orthogonal matrices with entries in the ring Z [ 1 1 root 1 root 2 1 root 2].
Keywords:
Quantum computing
reversible computing
Hadamard gate
quantum circuit
rig category
orthogonal group
Journal
P
IF:
2.8
Papers:
308
Citations:
4.7K