Quantum speedup and categorical distributivity

DOI10.1007/978-3-642-38164-5_9MaRDI QIDQ4922077zbMATH OpenOpenAlexFDO

Authors

Publication date 28 May 2013

Published in Computation, Logic, Games, and Quantum Foundations. The Many Facets of Samson Abramsky (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.3025

zbMATH Keywords

category theorycoherencedistributivitymonoidal tensorsquantum computingShor's algorithm

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: This paper studies one of the best known quantum algorithms - Shor's factorisation algorithm - via categorical distributivity. A key aim of the paper is to provide a minimal set of categorical requirements for key parts of the algorithm, in order to establish the most general setting in which the required operations may be performed efficiently. We demonstrate that Laplaza's theory of coherence for distributivity provides a purely categorical proof of the operational equivalence of two quantum circuits, with the notable property that one is exponentially more efficient than the other. This equivalence also exists in a wide range of categories. When applied to the category of finite dimensional Hilbert spaces, we recover the usual efficient implementation of the quantum oracles at the heart of both Shor's algorithm and quantum period-finding generally; however, it is also applicable in a much wider range of settings.

Recommendations

• Topological structure of quantum algorithms
• Abstract structure of unitary oracles for quantum algorithms
• Geometry of abstraction in quantum computation
• Quantum algorithms for algebraic problems
• Categorical quantum circuits

Cites work

• A single quantum cannot be cloned
• Algebra and Coalgebra in Computer Science
• Algebraically compact functors
• Braided tensor categories
• Coherence for categories with associativity, commutativity and distributivity
• Duality for groups
• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 195199 (Why is no real title available?)
• scientific article; zbMATH DE number 3385869 (Why is no real title available?)
• Introduction to distributive categories
• Introduction to extensive and distributive categories
• Natural deduction and coherence for weakly distributive categories
• Quantum circuit oracles for abstract machine computations
• Quantum fan-out is powerful
• Quantum measurements without sums
• The geometry of tensor calculus. I

Cited in

(1)

• Abstract structure of unitary oracles for quantum algorithms

This page was built for publication: Quantum speedup and categorical distributivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4922077)