Лекция 2. Вычислительная сложность схем и симуляция

На этой Лекции мы окидываем вглядом ряд вопросов вокруг понятия вычислительной мощности квантовых схем. Прежде всего, мы поговорили о простейших протоколах квантовой коммуникации: о распределении квантовой запутанности, о квантовой телепортации и о протоколе сверхплотного кодирования. Другим важным примером является протокол однокубитной телепортации. Некоторый набор операций называется универсальным, если при его помощи можно собрать схему, реализующая произвольную функцию в соответствующем классе. Обсуждаются некоторые универсальные словари для классических, обратимых и квантовых схем. Дано обсуждение общего определения классов сложности $\mathrm{BPP}$ и $\mathrm{BQP}$ и сформулирован вопрос об их равенстве. Введены понятия о симуляции схем: слабой симуляцией называется задача построения случайной величины, воспроизводящей статистику измерений в квантовой схеме; сильной симуляцией называется задача вычисления точного значения вероятности данного исхода. Простейшими методами сильной симуляции являются методы симуляции по Шрёдингеру и по Фейнману. Задача сведения слабой симуляции к сильной сводится к задаче построения выборки из распределения, а сведение сильной симуляции к слабой эквивалентно задаче статистического оценивания.