The Qudit ZH-Calculus: Generalised Toffoli+Hadamard and Universality
arXiv:2307.10095 · doi:10.4204/EPTCS.384.9
Abstract
We introduce the qudit ZH-calculus and show how to generalise all the phase-free qubit rules to qudits. We prove that for prime dimensions d, the phase-free qudit ZH-calculus is universal for matrices over the ring Z[e^2(pi)i/d]. For qubits, there is a strong connection between phase-free ZH-diagrams and Toffoli+Hadamard circuits, a computationally universal fragment of quantum circuits. We generalise this connection to qudits, by finding that the two-qudit |0>-controlled X gate can be used to construct all classical reversible qudit logic circuits in any odd qudit dimension, which for qubits requires the three-qubit Toffoli gate. We prove that our construction is asymptotically optimal up to a logarithmic term. Twenty years after the celebrated result by Shi proving universality of Toffoli+Hadamard for qubits, we prove that circuits of |0>-controlled X and Hadamard gates are approximately universal for qudit quantum computing for any odd prime d, and moreover that phase-free ZH-diagrams correspond precisely to such circuits allowing post-selections.
arXiv commentIn Proceedings QPL 2023, arXiv:2308.15489
References in corpus (24)
- Elementary gates for quantum computation
- Qudits and high-dimensional quantum computing
- Interacting Quantum Observables: Categorical Algebra and Diagrammatics
- Fault-Tolerant Quantum Computation with Higher-Dimensional Systems
- Universal Quantum Computation with Metaplectic Anyons
- Phase Gadget Synthesis for Shallow Circuits
- ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity
- The algebra of entanglement and the geometry of composition
- Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits
- Hypergraph Simplification: Linking the Path-sum Approach to the ZH-calculus
- Qufinite ZX-calculus: a unified framework of qudit ZX-calculi
- Qutrit Dichromatic Calculus and Its Universality
- Qutrit ZX-calculus is Complete for Stabilizer Quantum Mechanics
- AKLT-states as ZX-diagrams: diagrammatic reasoning for quantum states
- The Qupit Stabiliser ZX-travaganza: Simplified Axioms, Normal Forms and Graph-Theoretic Simplification
- Quantum Machine Learning using the ZXW-Calculus
- Light-Matter Interaction in the ZXW Calculus
- When Only Topology Matters
- A non-anyonic qudit ZW-calculus
- An Algebraic Axiomatisation of ZX-calculus
- Well-tempered ZX and ZH Calculi
- Complete ZX-calculi for the stabiliser fragment in odd prime dimensions
- On a recipe for quantum graphical languages
- Optimal Synthesis of Multi-Controlled Qudit Gates