- Oggetto:
Foundational principles of reversible and quantum computing
- Oggetto:
Foundational principles of reversible and quantum computing
- Oggetto:
Academic year 2015/2016
- Course ID
- FPRQC2014
- Teacher
- Prof. Luca Luigi Paolini (Titolare del corso)
- Year
- 1° anno 2° anno 3° anno
- Type
- A scelta dello studente
- Credits/Recognition
- 2
- Course disciplinary sector (SSD)
- INF/01 - informatica
MAT/01 - logica matematica - Delivery
- Tradizionale
- Language
- Italiano
- Attendance
- Obbligatoria
- Type of examination
- Scritto
- Oggetto:
Sommario del corso
- Oggetto:
Course objectives
Mathematicians have studied algorithms and computation since ancient times, but the study of computability has not been systematically handled until the last century. A computing theory is a meta-mathematical description of the pervasive notion of calculus, i.e. of the notion of "mechanical manipulation of symbols".
The more successfully notion of computation is the classical one that borrows its main ingredients from the classical mechanics. However, physics has developed alternative models of mechanics (sometimes with limited aims) including probabilistic, reversible and quantum mechanics. All them suggest alternative models of computation.
Probabilistic computing is a non-deterministic model of computing. In it, computations evolve randomly and produce stochastic (according to some probability distribution) results. This kind of models is profitable when we look to problems looking for approximated solutions.
Reversible computing, in a general sense, means computing using reversible operations, that is, operations that can be easily and exactly reversed, or undone. When this kind of reversibility is maintained at the lowest level, in the physical mechanisms of operation of our bit-devices (such as transistors), it avoids dissipating the energy that is associated with the bits of information that are being manipulated. This can help to reduce the overall energy dissipation of computations, which can in turn increase battery life or processing speed in heat-limited systems.
Quantum computing is frontier research. The successful construction of a large-scale quantum computer may be some years away but, secure communication involving quantum cryptography has already been implemented. The amount of theoretical research and experimental developments in quantum computing grows rapidly. At the same time, interest grows within the science and technology community, especially in physics and theoretical computing.- Oggetto:
Program
- Classical Turing Machines and boolean circuits: revival and main results.
- Reversible Turing Machines and reversible circuits: introduction and main properties.
- Probabilistic Turing Machines and probabilistic circuits: introduction and main properties.
- Complex numbers and Hilbert's spaces: introduction to quantum computing.
- Quantum Turing Machines and quantum circuits: quantum registers, no-cloning theorem, observation, teleportation.
Suggested readings and bibliography
- Oggetto:
Il materiale del corso sarà fornito durante le lezioni. Nel seguito sono solo indicate alcune letture correlate che dovrebbero aiutare a individuare il contenuto del corso.
BOOKS:- Introduction to Reversible Computing, Kalyan S. Perumalla
- Quantum Computing for Computer Scientists, Noson S. Yanofsky and Mirco A. Mannucci
Extra interesting reading
- Reversible Computing, Alexis De Vos.
- Quantum Computing, Jozef Gruska.
- Logical Reversibility of Computation, Charles H. Bennett.
- Notes on Landauer's Principle, Reversible Computation, and Maxwell's Demon, Charles H. Bennett.
- Reversible Computing, Tommaso Toffoli.
- A Syntax for Linear Logic, Philip Wadler.
- A Functional Quantum Programming Language, Jonathan J. Grattage.
- NREVERSAL of Fortune --- The Thermodynamics of Garbage Collection, Henry G. Baker.
- From Reversible to Irreversible Computations, Alexander S. Green and Thorsten Altenkirch.
- Using Forth in an Investigation into Reversible Computation, Bill Stoddart.
- Quantum Theory, the Church-Turing Principle, and the Universal Quantum Computer, David Deutsch.
- Quantum Lambda Calculus, Peter Selinger and Benoit Valiron.
- Reversible Communicating Concurrent Systems, Vincent Danos and Jean Krivine.
- General Reversibility, Vincent Danos, Jean Krivine, and Pawel Sobocinski.
- A Structural Approach to Reversible Computation, Samson Abramsky.
- Reversible Combinatory Logic, Alessandra Di Pierro, Chris Hankin, and Herbert Wiklicky.
- Oggetto:
Note
The course will be held in October/November.
- Oggetto:
