Geometry of abstraction in quantum computation

Dusko Pavlovic

    Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

    35 Downloads (Pure)


    Quantum algorithms are sequences of abstract operations, per­ formed on non-existent computers. They are in obvious need of categorical semantics. We present some steps in this direction, following earlier contribu­ tions of Abramsky, Goecke and Selinger. In particular, we analyze function abstraction in quantum computation, which turns out to characterize its clas­ sical interfaces. Intuitively, classical data can be recognized as just those data that can be manipulated using variables, i.e. copied, deleted, and abstracted over. A categorical framework of polynomial extensions provides a convenient language for specifying quantum algorithms, with a clearly distinguished clas­ sical fragment, familiar from functional programming. As a running example, we reconstruct Simon's algorithm, which is a sim­ ple predecessor of Shor's quantum algorithms for factoring and discrete loga­ rithms. The abstract specification in the framework of polynomial categories displays some of the fundamental program transformations involved in devel­ oping quantum algorithms, and points to the computational resources, whether quantum or classical, which are necessary for the various parts of the execution. The relevant resources are characterized as categorical structures. They are normally supported by the standard Hilbert space model of quantum mechan­ ics, but in some cases they can also be found in other, nonstandard models. We conclude the paper by sketching an implementation of Simon's algorithm using just abelian groups and relations.
    Original languageEnglish
    Title of host publicationMathematical foundations of information flow
    Subtitle of host publicationClifford Lectures Information Flow in Physics, Geometry, and Logic and Computation, March 12-15, 2008, Tulane University, New Orleans, Louisiana
    EditorsSamson Abramsky, Michael Mislove
    PublisherAmerican Mathematical Society
    ISBN (Electronic)978-0-8218-9006-6
    ISBN (Print)978-0-8218-4923-1
    Publication statusPublished - 2012
    EventClifford lectures on Information Flow in Physics, Geometry, Logic and Computation 2008 - Tulane University, New Orleans, United States
    Duration: 12 Mar 200815 Mar 2008

    Publication series

    NameProceedings of symposia in applied mathematics
    PublisherAmerican Mathematical Society


    ConferenceClifford lectures on Information Flow in Physics, Geometry, Logic and Computation 2008
    Country/TerritoryUnited States
    CityNew Orleans


    Dive into the research topics of 'Geometry of abstraction in quantum computation'. Together they form a unique fingerprint.

    Cite this