segunda-feira, 28 de maio de 2012

ICMC promove minicurso Quantum Logic and Quantum Computing

O Instituto de Ciências Matemáticas e de Computação (ICMC), da USP em São Carlos, promove o minicurso Quantum Logic and Quantum Computing, a ser ministrado por Benoit Dherin. O minicurso será realizado às sextas-feiras, no período de 1 a 22 de junho, das 15h às 17h, na sala 5-103. 

As inscrições são gratuitas, e devem ser feitas até 31 de maio por meio do envio da ficha de inscrição preenchida para o e-mail

Link para a ficha de inscrição:

Descrição do curso

This mini-course will introduce quantum logic and quantum computing in the unifying framework of symmetric monoidal categories and their associated graph- ical calculous, which is related to many other areas of mathematics: Feynman graphs, Penrose string diagrams, Runge-Kutta methods tree combinatorics, topo- logical quantum field tangles...

This graphical calculous was formalized by Joyal and Street in [8]. Roughly, the idea is that the intricate composition of morphisms in a symmetric monoidal cate- gory can be represented in terms of graphs, and categorical axioms can interpreted in terms of topological transformations between these graphs.

In logic, propositions are represented by the objects of a certain category and the logical implications between them are represented by its morphisms. In com- puting, the objects represent the inputs and outputs and the morphisms the al- gorithms linking them. The quantum circuits that are at the base of quantum computing are examples of this graphical calculous underlying compositions of morphisms in symmetric monoidal categories.

A goal of this mini-course is to analyze, in terms of this graphical machinery, Schor’s quantum algorithm that beats any known classical algorithm at decom- posing an integer into its prime factors.

This mini-course will heavily draw on the works of Jauch and Piron on the foundations of quantum mechanics ([7, 9]), Baez and Stay on the relationships between topology, physics and computing ([4]), and Abramsky and collaborators on the categorical structure underlying quantum mechanics and logic ([1], [2], and [3]) .

Click here for the syllabus.


  • Lecture 1 (5/1/12): Physical proprieties and logic. Symmetric monoidal categories: definitions and examples. Abstract description of physical sys- tems in terms of property lattices, which we interpret as special monoidal categories: definition of lattices, property lattices as quotient of question lattices, underlying logical structure. Main examples: the lattice of sub-sets of a set (classical), the lattice of closed subspaces of a Hilbert space (quantum). States as atoms, Observables as lattices morphisms. Abstract characterization of quantum and classical lattices. We will follow chapters one and two of [9].
  • Lecture 2 (5/15/12): Physical processes and algorithms. Abstract de- scription of processes as morphisms and states as objects of a symmetric monoidal category. Graphical representation in terms of string diagrams. Example: the category of finite Hilbert spaces and the category of relations. Quantum processes and dagger categories. Reinterpretation of the morphisms of a symmetric monoidal categories as algorithms and its ob- jects as input/output. This will be a rough summary of the ideas contained in [2] and [4].
  • Lecture 3 (5/22/12): Qubits and quantum circuits. Bird-eye view of the quantum mechanic formalism: reversible and irreversible processes, super- position and entanglement of states. The quantum 2-dimensitional system and the qubit. Computational basis. Quantum register, quantum gates and quantum circuits. Universal gates. Bell state and the teleportation protocol. Comparison with the formalism developped earlier. This will be a quick summary of chapter three of [5].
  • Lecture 4 (5/29/12): An example of a quantum algorithm. Notion of algorithm complexity. The factorization in primes problem and Shor’s quantum algorithm to solve it. Efficiency comparison between the classical and quantum versions of the algorithm. We will follow the exposition given in [5] and see how the formalism developped earlier can shed some light on the algorithm.

  • [1] S. Abramsky and R. Duncan, A categorical quantum logic, Math. Structures Com- put. Sci. 16 (2006), 469–489.
  • [2] S. Abramsky and B. Coecke, Categorical quantum mechanics, Handbook of Quan- tum Logic and Quantum Structures—Quantum logic, Elsevier (2009).
  • [3] S. Abramsky and N. Tzevelekos, Introduction to categories and categorical logic, New Structures for Physics, Lecture Notes in Phys. 813 (2011).
  • [4] J. Baez and M. Stay, Physics, topology, logic and computation: a Rosetta Stone. New Structures for Physics, Lecture Notes in Phys. 813 (2011).
  • [5] G. Benenti, G. Casti, and G. Strini, Principles of Quantum Computation and Information, Volume 1: Basic concepts, World Scientific (2004).
  • [6] B. Coecke, Kindergarten quantum mechanics, Quantum Theory: Reconsideration of Foundations, AIP Conf. Proc. 810, Amer. Inst. Phys., (2006), 81–98.
  • [7] J. Jauch, Foundations of Quantum Mechanics, Addison-Wesley Publishing Co. (1968).
  • [8] A. Joyal and R. Street, The geometry of tensor calculus I, Adv. Math. 88 (1991), 55–112.
  • [9] C. Piron, Mécanique Quantique, Bases et Applications, Presses Polytechniques et Universitaires Romandes, Lausanne (1998).

Seção de Eventos do ICMC
Tel. (16) 3373-9146