Лекция 7. Универсальность квантовых схем

На этой Лекции мы продолжили обсуждать свойства квантовых схем. Прежде всего, мы поговорили более подробно об измерениях: произвольные недеструктивные и/или запутывающие измерения можно свести при помощи анцилл и унитарных вентилей к деструктивным измерениям вычислительного базиса. Затем, мы обсудили простейшие протоколы квантовой коммуникации: передачу классической информации по квантовому каналу, генерацию запутанности при помощи квантового канала, сверхплотное кодирование и квантовую телепортацию. Мы обсудили принцип отложенного измерения: измерения над кубитом всегда можно “отложить” до конца вычисления, используя квантовый контроль. В частности, благодаря этому принципу можно свести любую классическую схему к унитарной квантовой схеме. Мы также доказали универсальность набора произвольных однокубитных вентилей и $C\mathrm{NOT}$. Наконец, мы ввели определение класса $\mathtt{BQP}$ языков, эффективно разрешимых при помощи квантовых схем.