Free Quantum Computing

Abstract

Quantum computing improves substantially on known classical algorithms for various important problems, but the nature of the relationship between quantum and classical computing is not yet fully understood. This relationship can be clarified by free models, that add to classical computing just enough physical principles to represent quantum computing and no more. Here we develop an axiomatisation of quantum computing that replaces the standard continuous postulates with a small number of discrete equations, as well as a free model that replaces the standard linear-algebraic model with a category-theoretical one. The axioms and model are based on reversible classical computing, isolate quantum advantage in the ability to take certain well-behaved square roots, and link to various quantum computing hardware platforms. This approach allows combinatorial optimisation, including brute force computer search, to optimise quantum computations. The free model may be interpreted as a programming language for quantum computers, that has the same expressivity and computational universality as the standard model, but additionally allows automated verification and reasoning.

32 pages

References in corpus (11)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Efficient classical simulation of slightly entangled quantum computations
• Contextuality supplies the magic for quantum computation
• Interacting Quantum Observables: Categorical Algebra and Diagrammatics
• Boson Sampling from Gaussian States
• Automated optimization of large quantum circuits with continuous parameters
• Physics without Determinism: Alternative Interpretations of Classical Physics
• The elusive source of quantum effectiveness
• Number-Theoretic Characterizations of Some Restricted Clifford+T Circuits
• Symmetries in Reversible Programming: From Symmetric Rig Groupoids to Reversible Programming Languages
• With a Few Square Roots, Quantum Computing is as Easy as Π