The Topology of Quantum Algorithms

Abstract

We use a categorical topological semantics to examine the Deutsch-Jozsa, hidden subgroup and single-shot Grover algorithms. This reveals important structures hidden by conventional algebraic presentations, and allows novel proofs of correctness via local topological operations, giving for the first time a satisfying high-level explanation for why these procedures work. We also investigate generalizations of these algorithms, providing improved analyses of those already in the literature, and a new generalization of the single-shot Grover algorithm.

33 pages. Updated to match the final published article

References in corpus (1)

• POVMs and Naimark's theorem without sums

Cited by in corpus (19)

• The algebra of entanglement and the geometry of composition
• Infinite-dimensional Categorical Quantum Mechanics
• Mixed quantum states in higher categories
• Abstract structure of unitary oracles for quantum algorithms
• Fourier transforms from strongly complementary observables
• When Only Topology Matters
• Categorical Semantics for Schrödinger's Equation
• Fully graphical treatment of the quantum algorithm for the Hidden Subgroup Problem
• A Diagrammatic Approach to Information Transmission in Generalised Switches
• Picturing Counting Reductions with the ZH-Calculus
• Shaded Tangles for the Design and Verification of Quantum Programs (Extended Abstract)
• Quantum Algorithms and Oracles with the Scalable ZX-calculus
• Models of Quantum Algorithms in Sets and Relations
• Generalised Mermin-type non-locality arguments
• Shaded tangles for the design and verification of quantum circuits
• The Abstract Structure of Quantum Algorithms
• Graphical Methods in Device-Independent Quantum Cryptography
• CPM Categories for Galois Extensions
• Three-qubit Deutsch-Jozsa in measurement-based quantum computing