2026-08-15T16:33:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2362 2024-03-06T11:08:57Z ddc:004 open_access

Geometry of abstraction in quantum computation Pavlovic, Dusko Quantum algorithms categorical semantics Frobenius algebra classical structure Modern cryptography is based on various assumptions about computational hardness and feasibility. But while computability is a very robust notion (cf Church's Thesis), feasibility seems quite sensitive to the available computational resources. A prime example are, of course, quantum channels, which provide feasible solutions of some otherwise hard problems; but ants' pheromones, used as a computational resource, also provide feasible solutions of other hard problems. So at least in principle, modern cryptography is concerned with the power and availability of computational resources. The standard models, used in cryptography and in quantum computation, leave a lot to be desired in this respect. They do, of course, support many interesting solutions of deep problems; but besides the fundamental computational structures, they also capture some low level features of particular implementations. In technical terms of program semantics, our standard models are not *fully abstract*. (Related objections can be traced back to von Neumann's "I don't believe in Hilbert spaces" letters from 1937.) I shall report on some explorations towards extending the modeling tools of program semantics to develop a geometric language for quantum protocols and algorithms. Besides hiding the irrelevant implementation details, its abstract descriptions can also be used to explore simple nonstandard models. If the time permits, I shall describe a method to implement teleportation, as well as the hidden subgroup algorithms, using just abelian groups and relations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dusko Pavlovic 2010 Is Part Of Dagstuhl Seminar Proceedings, Volume 9311, Classical and Quantum Information Assurance Foundations and Practice (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.09311.2 urn:nbn:de:0030-drops-23623 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09311.2 eng https://creativecommons.org/licenses/by/4.0/legalcode