RUS  ENG
Full version
SEMINARS

Quantum computation
February 7, 2024 13:10, Steklov Mathematical Institute, Room 430 (8 Gubkina) + Zoom


Lecture 1. What is computation?

V. I. Yashin


https://youtu.be/zSV29tUlxqk

Abstract: We discussed in general terms what can be considered computation. We will assume that computation is the evolution of some system that can be used to solve problems. Following Church's thesis, we will study bit strings and some set (dictionary) of possible operations (gates) on them, taking them as physical systems describing classical computation. Classical Boolean circuits are compositions of basic operations, and if the dictionary is rich enough (universal), one can express any Boolean function as a Boolean circuit. However, in bad cases such an expression may require a large number of operations.


© Steklov Math. Inst. of RAS, 2024