Laboratory of Mathematical Logic at PDMI

Вторник, 28 марта, комната 412. Начало в 15:00.

Докладчик: Э. А. Гирш.

КВАНТОВЫЕ ВЫЧИСЛЕНИЯ С ТОЧКИ ЗРЕНИЯ ТЕОРИИ СЛОЖНОСТИ
Определяется класс вычислительных задач BQP (по аналогии с BPP). определение не несет "физической" терминологии, но охватывает все свойства квантовых вычислений. рассматривается место этого класса в общей картине сложностных классов.
Основной источник: L.Fortnow "One complexity theorist's view of quantum computing" (http://xxx.lanl.gov/abs/quant-ph/0003035)