License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09311.2
URN: urn:nbn:de:0030-drops-23623
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2362/
Go to the corresponding Portal

Pavlovic, Dusko

Geometry of abstraction in quantum computation

pdf-format:
09311.PavlovicDusko.Paper.2362.pdf (0.2 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{pavlovic:DagSemProc.09311.2,
  author =	{Pavlovic, Dusko},
  title =	{{Geometry of abstraction in quantum computation}},
  booktitle =	{Classical and Quantum Information Assurance Foundations and Practice},
  pages =	{1--28},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9311},
  editor =	{Samual L. Braunstein and Hoi-Kwong Lo and Kenny Paterson and Peter Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2010/2362},
  URN =		{urn:nbn:de:0030-drops-23623},
  doi =		{10.4230/DagSemProc.09311.2},
  annote =	{Keywords: Quantum algorithms, categorical semantics, Frobenius algebra, classical structure}
}

Keywords: Quantum algorithms, categorical semantics, Frobenius algebra, classical structure
Collection: 09311 - Classical and Quantum Information Assurance Foundations and Practice
Issue Date: 2010
Date of publication: 06.01.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI