Классические и квантовые вычисления

Нам потребуются также операторы с несколькими управляющими q-битами:

(7.2)

Пример 7.1. Пусть . Тогда , а (элемент Тоффоли).

Теперь построим элемент Тоффоли, используя преобразования двух q-битов. Для начала найдем пару операторов, удовлетворяющих следующему соотношению . Например, годится такая пара:

Поясним геометрический смысл этой конструкции. Унитарная группа действует на трехмерном евклидовом пространстве. Чтобы описать это действие, заметим, что эрмитовы матрицы с нулевым следом образуют трехмерное евклидово пространство: скалярное произведение задается формулой , ортонормированный базис образуют матрицы Паули,

Унитарный оператор действует на этом пространстве так: . Можно доказать (см.[8, 11.12]), что описанное действие задает изоморфизм , где -- подгруппа фазовых сдвигов, а -- группа поворотов в трехмерном пространстве (т.е. группа ортогональных преобразований с детерминантом, равным ).

При этом действии соответствует поворот вокруг оси на , соответствует поворот вокруг на , а соответствует поворот вокруг на .

На рис. рис. 7.1 изображено графическое представление схемы, вычисляющей элемент Тоффоли с помощью операторов , и . Последний -- это управляемый двумя битами фазовый сдвиг (умножение на ). Проверим эту схему. Пусть на вход подается вектор , где , . Если , то к будет применен оператор , т.е. и в третьем q-бите переставляются. Если же хотя бы один из управляющих битов равен 0, то к будет применен тождественный оператор. Это и есть действие элемента Тоффоли.

Рисунок 7.1.

С помощью элемента Тоффоли можно реализовать любую перестановку базисных векторов (с использованием дополнительной памяти).

Покажем, как реализовать оператор для любого , действуя только на пары q-битов. Для этого также потребуется дополнительная память. Будем строить оператор , действующий в пространстве q-битов и удовлетворяющий условию



(Предостережение: это условие не означает, что .)

Существует обратимая схема размера , вычисляющая произведение входных битов (с мусором); графически она представлена на рис. рис. 7.2 (сверху обозначено число битов в каждом из выделенных фрагментов памяти).

Рисунок 7.2.

На рис. 7.3 показано, как с помощью схемы и оператора с одним управляющим q-битом построить оператор . Мы применяем схему , а затем -- обратную схему , после чего все вспомогательные биты возвращаются в исходное состояние. В промежутке самой верхней линии соответствует бит со значением . Его мы и используем для управления оператором , действующим на самой нижней линии. Другим способом можно записать как .



Рисунок 7.3.

Действие можно описать так: на подпространстве, порожденном векторами и , действует оператор , а на ортогональном дополнении к этому подпространству -- тождественный оператор. Наша следующая задача: реализовать оператор, который устроен так же, но нетривиальное действие осуществляется на подпространстве, натянутом на произвольную пару базисных векторов. Пусть мы хотим реализовать произвольный оператор в подпространстве, натянутом на базисные векторы и , где , , . Пусть -- такая перестановка, что , . Тогда нужный нам оператор представляется в виде . (Напомним, что -- оператор, соответствующий перестановке .)

Итак, на парах базисных векторов мы можем действовать произвольно. Пока все использованные схемы имели размер , так что построенные действия реализуются эффективно. Следующая часть неэффективна. Имеет место следующая лемма.

Лемма 7.1. Любая унитарная матрица в пространстве может быть представлена в виде произведения матриц вида

Заметим, что в нашем случае , так что получаем представление в виде произведения экспоненциального большого числа базисных операторов.

Тема 7.2 Приближенная реализация

Теперь перейдем к конечным базисам. В этом случае возможно только приближенное представление операторов произведениями базисных. Чтобы определить приближенную реализацию, нам потребуется норма на пространстве операторов.

На пространстве состояний есть норма . Она, как и любая норма, по определению удовлетворяет следующим условиям:

(7.3)

(7.4)

(7.5)

Введем теперь норму на пространстве операторов. Пусть -- пространство с нормой. Пространство операторов, действующих на нем, можно представить как (изоморфизм задается матричным представлением ).

Определение 7.2. Норма оператора (так называемая операторная норма\, вообще говоря, есть и другие) равна

Заметим, что -- наибольшее собственное число оператора .

Эта норма обладает всеми перечисленными выше свойствами нормы, а кроме того, еще несколькими специфическими:

(7.6)

(7.7)

(7.8)

Доказательства этих свойств нормы получаются непосредственно из определения и оставляются в качестве упражнения.

Дадим теперь определение приближенной реализуемости. Если искомый оператор -- , то его приближенная реализация будет обозначаться .

Определение 7.3. Оператор представляет оператор с точностью , если .

У этого определения есть два замечательных свойства. Во-первых, если мы имеем произведение нескольких операторов , каждый из которых имеет свое приближение с точностью , то произведение этих приближений приближает с точностью ( ошибки накапливаются линейно ):

Достаточно рассмотреть пример с двумя операторами:

В этой выкладке последнее равенство справедливо благодаря унитарности операторов. (Если рассматривать неунитарные операторы, то ошибки приближения могут накапливаться гораздо быстрее, например, экспоненциально.)

Замечание 7.1. Всякая модель, претендующая на решение сложных задач какими-то реальными физическими процессами, должна обязательно изучаться на предмет устойчивости к ошибкам приближения. (В реальной жизни параметры любого физического процесса можно задать лишь с некоторой точностью.) В частности, вычисление с экспоненциальным накоплением ошибок почти заведомо бесполезно с практической точки зрения.

Второе свойство понятия " представляет с точностью " мы сформулируем в более общем контексте.

Определение 7.4. Оператор приближается в расширенном смысле оператором с точностью , если для любого из выполнено

(7.9)

Сформулируем это определение еще одним способом. Введем оператор , который действует по правилу . Оператор не унитарный, но изометричный. Условие из последнего определения можно переписать так

(7.10)

Рассуждение про накопление ошибок проходит и в этом случае (что, конечно, следует проверить).

Справедливо следующее утверждение: если приближает (в расширенном смысле) с точностью , то приближает с той же точностью . Это следует из того, что для унитарных операторов . Умножая выражение под нормой в (7.10) слева на , а справа -- на , получим следствие из неравенства (7.10): .

Определение 7.5. Будем называть базис полным, если любой унитарный оператор можно с любой точностью представить в расширенном смысле квантовой схемой в базисе .

Теорема 7.2. (см. [4]). Базис , где

является полным. (Такой базис будем называть стандартным.)

Доказательство этой теоремы следует из решения задач 7.5-7.9.

Замечание 7.2. Если убрать из базиса квантовый элемент Тоффоли, он перестает быть полным. Однако многие важные вычисления можно делать и в таком усеченном базисе. В частности, как будет видно в дальнейшем, схемы, исправляющие ошибки, можно реализовать без элемента Тоффоли.

Можно оценить сложность реализации оператора в этом базисе. Если , то можно реализовать этот оператор с точностью квантовой схемой в базисе размера . Если матричные элементы заданы в двоичной записи, то эта схема строится по с помощью некоторого алгоритма примерно за то же время (множители и степени полинома могут отличаться). Идея построения такого алгоритма легко усматривается из задач 7.1 и 7.11.

Задачи

Докажите, что все операторы на одном q-бите в сочетании с оператором образуют полный базис. Решение должно быть достаточно эффективным: должен существовать алгоритм, который строит схему, реализующую произвольный оператор на q-битах, за время .

Докажите свойства операторной нормы(7.6-7.8).

Пусть операторы приближают в расширенном смысле операторы с точностью , . Докажите, что оператор приближает в расширенном смысле оператор с точностью .

Пусть оператор приближает в расширенном смысле оператор с точностью . Докажите, что существует оператор , точно представляющий в расширенном смысле, т.е. выполняется равенство

и такой, что .

Пусть унитарный оператор удовлетворяет условию . Постройте реализующую схему размера в базисе , использующую оператор один раз.

Пусть -- некоммутирующие элементы группы -- повороты на углы, несоизмеримые с . Докажите, что группа, порожденная и , образует всюду плотное подмножество в .

Пусть -- унитарное пространство размерности . Рассмотрим подгруппу -- стабилизатор одномерного подпространства, порожденного некоторым единичным вектором . Пусть -- произвольный унитарный оператор, не сохраняющий подпространство . Докажите, что множество операторов порождает всю группу .

(Заметим, что в условии этой задачи и можно профакторизовать по подгруппе фазовых сдвигов ).

Докажите, что операторы из стандартного базиса порождают всюду плотное множество в .

Докажите, что фазовые сдвиги можно реализовать в стандартном базисе, используя напрокат дополнительные q-биты.

Докажите, что отрицание и элемент Дойча , где , -- иррациональное, образуют полный базис для квантового вычисления.

Докажите, что любой оператор , действующий на одном q-бите, может быть приближенно реализован в расширенном смысле с точностью схемой размера в стандартном базисе, и есть полиномиальный алгоритм построения этой схемы по описанию .

Эта задача довольно сложна, к ее решению лучше приступать после знакомства с разделами 11 и 12 и решения задачи 12.3 (квантовое преобразование Фурье). Предлагаемый путь решения является достаточно изощренным. В статье [4] был использован более прямой (но тоже неочевидный) подход, при котором получается схема размера .



Лекция №8

Тема 8.1: Определение квантового вычисления. Примеры

Пока мы описали работу квантового компьютера. Теперь пора определить, когда эта работа приводит к решению интересующей нас задачи. Определение будет похоже на определение вероятностного вычисления.

Пусть есть функция . Рассмотрим квантовую схему, работающую с битами: . Неформально говоря, эта схема вычисляет , если после применения к начальному состоянию , мы, "посмотрев" на первые битов, с большой вероятностью "увидим" . (Остальные q-биты могут содержать произвольный мусор.)

Нужно только оговорить, что такое эта вероятность. Слова "посмотрев" и "увидим" в точном смысле означают, что производится измерение значений соответствующих q-битов. В результате измерения могут получаться разные ответы, каждому соответствует своя вероятность. Ниже (раздел 9) этот вопрос рассматривается подробно. Для того, чтобы дать определение квантового вычисления функции , достаточно (не вдаваясь в обсуждение физических объяснений этого факта) принять следующее: вероятность получения базисного состояния, при измерении состояния равна

(8.1)

Нас интересует вероятность того, что компьютер закончит работу в состоянии вида , где -- любое.

Определение 8.1. Схема вычисляет , если для любого выполнено

алгоритм квантовый компьютер вычисление

где -- некоторое фиксированное число, меньшее . (Обратите внимание, что и состоят из разного количества битов, хотя суммарная длина и одинакова и равна .)

Как и для вероятностных вычислений, выбор несущественен, поскольку можно запустить несколько экземпляров схемы независимо и выбрать тот результат, который получается чаще всего. Из оценки, приведенной в лекции 3, следует, что для уменьшения вероятности неудачи в раз нужно взять экземпляров схемы . Выбор самого частого результата реализуется классической схемой, использующей функцию голосования (она равна 1, когда более половины ее аргументов равны 1, и равна 0 в противном случае). Функция реализуется в полном базисе схемой размера , так что потеря эффективности при уменьшении вероятности неудачи в раз задается множителем .

Задача 8.1. Докажите, что приведенное рассуждение является корректным в квантовом случае: функция реализована в виде обратимой схемы, на вход которой подаются выходные q-биты копий схемы .

Тема 8.2 Квантовый поиск: алгоритм Гровера

Итак, мы имеем определение квантового вычисления. Теперь можно заняться сравнением эффективности классического и квантового вычисления. Во введении упоминались три основных примера, для которых квантовое вычисление оказывается, по-видимому, эффективнее классического. Мы начнем с того из них, в котором квантовое вычисление заведомо эффективнее (хотя ускорение лишь "полиномиальное").

Дадим определение универсальной переборной задачи в классической и квантовой постановке.

Пусть имеется устройство (см. рисунок), которое по входам и определяет значение некоторого предиката . Нас интересует предикат . Это похоже на определение класса NP, но сейчас нам недоступна внутренняя структура устройства, вычисляющего предикат . В таких условиях на классическом компьютере значение предиката нельзя вычислить быстрее, чем за шагов, где -- количество битов в записи .

Оказывается, что на квантовом компьютере можно вычислить значение предиката и даже найти , на котором выполнено , за время . Получены также и нижние оценки, показывающие, что в этой постановке квантовые устройства дают лишь полиномиальное ускорение по сравнению с классическими.

В квантовой постановке задача выглядит так. Вход по-прежнему классический, но сам "черный ящик" -- квантовое устройство, и вход (варианты ответа) мы будем считать квантовым. Поэтому наш оракул (или "черный ящик") задает оператор , действующий по правилу

Нужно вычислить значение и найти "ответ" (при котором выполнен ).

Результаты, о которых уже упоминалось, формулируются так (см.[31, 48]): существуют две константы и такие, что есть схема размера , решающая задачу для любого предиката ; а для любой схемы размера существует предикат , при котором задача не решается на этой схеме (т.е. схема дает неправильный ответ с вероятностью ).

Мы разберем упрощенную постановку: считаем, что "ответ" существует и единствен, обозначим его через ; нужно найти . Схема, которую мы для этого построим, будет примером "прямого" квантового вычисления; она будет описана в терминах преобразований базисных векторов.

Рассмотрим два оператора:

и

Оператор в матричной форме может быть записан так (напомним, что ):

Оператор нам задан (это оракул). Построим квантовую схему, вычисляющую . Действовать будем так: переведем в некоторым оператором , затем применим оператор , после чего применим .

Построить оператор , который переводит в , просто. Это , где оператор -- из стандартного базиса (см. лекцию 7). Действительно, .

Теперь построим реализацию оператора . Используем обратимую классическую схему, реализующую оператор ,

(С точностью до перестановки аргументов, .) Поскольку имеет малую схемную сложность (в классическом смысле), по лемме для вычисления существует небольшая схема (в которой берутся "напрокат" дополнительные q-биты).

Схема, реализующая оператор , изображена на рис. рис. 8.1.. Центральная часть, включающая в себя , и , реализует оператор . В схеме используется оператор ( из стандартного базиса).



Рисунок 8.1.

Заметим, что и действуют тождественно на векторах с нулевыми значениями q-битов, взятых напрокат. Поэтому решающую роль играет оператор , действующий на вспомогательный q-бит, который также не меняется после всего вычисления.

Пусть вас не смущает то, что действует только на "управляемый" q-бит, а меняется в результате весь вектор. Вообще, различие между "чтением" и "записью" в квантовом случае неабсолютно и зависит от выбора базиса. Приведем соответствующий пример.

Напишем матрицу в базисе для каждого из q-бит. Другими словами, запишем матрицу для оператора . Схема для этого оператора изображена на рис. рис. 8.2. Используя равенство , найдем действие на базисном векторе:



Итак, в базисе

управляющий и управляемый биты поменялись местами. Какой бит "управляющий", или какой "читается", зависит от выбора базиса. Разумеется, такое положение дел противоречит нашей классической интуиции. Трудно представить, как при переходе к другому базису квантовый принтер вдруг становится квантовым сканнером.

Рисунок 8.2.

Задача 8.2. Что будет, если изменить базис только в одном бите? Например, как будет выглядеть матрица оператора, схема которого изображена на рисунке? Попробуйте также поменять базис в другом бите.



Вернемся к построению схемы для универсальной переборной задачи. Оракул нам задан, и мы реализовали оператор . Из вектора можно получить вектор применением оператора ( ). Теперь с помощью операторов и построим из вектора искомый вектор . Для этого будем поочередно действовать операторами :

Что при этом получается? Геометрически оба оператора есть отражения относительно гиперплоскости. Подпространство инвариантно относительно обоих операторов, а, значит, и относительно . Поскольку вектор принадлежит этому подпространству, достаточно рассмотреть действие на нем.

Композиция двух отражений относительно двух прямых есть поворот на удвоенный угол между этими прямыми. Угол легко вычислить, , т.е. эти прямые почти перпендикулярны. Поэтому можно написать , где -- поворот на малый угол . Но тогда , где -- поворот на угол . Знак нас не интересует (фазовые множители не меняют вероятностей). При больших имеем . Тогда после итераций исходный вектор повернется на угол и станет близок к искомому вектору. Это и означает, что система окажется в состоянии с вероятностью, близкой к единице.

Если решается переборная задача в общей постановке (т.е. ответов может быть несколько, а может не быть вообще), требуются дополнительные технические ухищрения. Число шагов для поворота от исходного вектора к какому-нибудь вектору из подпространства, порожденного векторами ответов, обратно пропорционально корню из числа решений.

Тема 8.3 Универсальная квантовая схема

Второй из примеров, упомянутых во введении, -- моделирование квантовомеханических систем. Это нечетко поставленная задача, так как большую роль в ней играет выбор конкретной системы и выделение существенных "степеней" свободы. С математической точки зрения, более корректно говорить о моделировании квантовых схем.

Квантовые схемы имеют конструктивное описание, если указать точность, с которой известны матричные элементы операторов, входящих в схему. Пусть есть описание квантовой схемы , размера и точности . Элементами этой схемы могут быть любые унитарные операторы на q-битах (так чтобы полная длина описания схемы не превышала ,). Обозначим оператор, реализуемый этой схемой, через .

Из результатов задач 7.1 и 7.11 следует, что можно построить универсальную квантовую схему размера , которая моделирует работу произвольной квантовой схемы следующим образом. Если задано описание некоторой схемы размера и ее вход , то

Квантовые алгоритмы и класс BQP.

До сих пор мы рассматривали неоднородные вычисления (вычислялись булевы функции). Алгоритмы вычисляют функции на словах произвольной длины. Определение квантового алгоритма можно дать, используя уже введенные квантовые схемы. Пусть есть функция , длина результата -- полином от длины входа. Ей сопоставляется последовательность булевых функций (ограничения на входы длины ) . Квантовый алгоритм для вычисления -- это однородная последовательность схем, вычисляющих . "Однородная" означает, что по можно построить описание соответствующей схемы на обычной полиномиально ограниченной машине Тьюринга. Будем говорить, что алгоритм работает за время , если размер схемы, вычисляющей , равен .

Замечание 8.1. Можно определить квантовую машину Тьюринга и непосредственно через суперпозиции различных состояний ленты МТ (первоначальное определение Д.Дойча было именно таким). Наше определение оказывается эквивалентным.

Определение 8.2. Функция принадлежит классу , если есть квантовый алгоритм ее вычисления, работающий за время для некоторой константы .

Как соотносится класс BQP{} с сложностными классами, введенными ранее?

Задача 8.3. Докажите, что



Класс состоит из предикатов вида

где , и учитываются только с длиной меньше некоторого полинома .

Это почти все, что известно о соотношениях между BQP и другими сложностными классами. Косвенное свидетельство в пользу строгого включения дает существование эффективных квантовых алгоритмов для некоторых теоретико-числовых задач, традиционно считаемых трудными (см. раздел 12).

Заметим также, что в последнее время появились интересные результаты о квантовых аналогах некоторых более сильных сложностных классов (не описанных в части I).

Задача 8.4. Постройте квантовые схемы полиномиального размера в базисе из операторов на двух q-битах, которые выполняют следующие действия:

для заданного числа , , записанного двоичными цифрами, преобразовать состояние в состояние ;

преобразовать в , считая, что записано двоичными цифрами;

выполнить преобразование Фурье на группе при :



считая, что и записаны двоичными цифрами; (в этом случае найдите схему размера ).



Лекция №9

Тема 9.1 Квантовые вероятности

Перейдем теперь к обсуждению некоторых "физических" аспектов квантовых вычислений. Пусть система из q-битов находится в состоянии . Коэффициенты разложения по выделенному базису (классических состояний) называются амплитудами. Квадрат модуля амплитуды равен вероятности обнаружить систему в состоянии (сравните с (8.1)). Другими словами, при измерении состояния этой квантовой системы будут получаться классические состояния, распределенные как .

Определенная формулой (8.1) величина обладает основными свойствами обычной вероятности. Тот факт, что квадрат модуля амплитуды -- это вероятность наблюдения системы в состоянии , согласуется с тем, что физические состояния в квантовой механике соответствуют векторам единичной длины, а преобразования этих состояний не меняют длины, т.е. унитарны. Действительно, (сумма вероятностей равна 1), а применение физически реализуемого оператора должно сохранять это соотношение, т.е. должно быть унитарным.

Формулы (8.1) достаточно для определения квантового вычисления и класса BQP. Однако есть вопросы, в которых это определение оказывается неудобным или неприменимым. Два основных примера: измеряющие операторы и алгоритмы, построенные на их основе, и задача построения надежных квантовых схем из ненадежных элементов (исправление ошибок).

Поэтому мы построим определение квантовой вероятности, в котором обобщается как то, что мы наблюдаем (состояние системы), так и результат наблюдения. К этому общему определению мы придем, рассматривая ряд примеров. Для начала перепишем уже полученное выражение для вероятности в виде

где через обозначен проектор на подпространство, порожденное .

Чтобы сделать следующий шаг к общему определению квантовой вероятности, подсчитаем вероятность того, что первые битов имеют заданное значение . Для этого представим состояние в виде двух блоков.

Имеем

(9.1)

здесь обозначает проектор на подпространство . Формула (9.1) задает определение квантовой вероятности и в том случае, когда -- произвольное подпространство.

В этом случае проектор на подпространство определяется как , где пробегают любой ортонормированный базис .

Замечание 9.1. Величина , которая используется в определении вычисления функции из в квантовой схемой (см. лекцию 8), равна , где . Еще раз напомним смысл этого определения: схема вычисляет , если для любого вероятность наблюдения правильного ответа после применения схемы к начальному состоянию больше .

Проекторы не являются физически реализуемыми операторами, точнее говоря, они не описывают переход от одного состояния системы к другому за определенный промежуток времени. Такой переход описывается унитарными операторами. Все же, допуская некоторую вольность, проекторам можно придать физический смысл. Проектор выделяет часть состояний системы из всех возможных. Представьте фильтр (устройство, а не теоретико-множественное понятие), который пропускает только системы в состояниях из . Если на такой фильтр подать систему в состоянии , то сквозь фильтр пройдет система в состоянии . Суммарная вероятность выделенных состояний, вообще говоря, меньше 1, она равна . Число определяет вероятность того, что система сквозь фильтр не пройдет.

Сравним свойства классической и квантовой вероятности.

Классическая вероятность	Квантовая вероятность
Определение
Событие -- подмножество некоторого конечного множества. Распределение вероятностей задается функцией со свойствами а) ; б) . Вероятность: .	Событие -- подпространство некоторого конечномерного унитарного пространства . Распределение вероятностей задается вектором состояния , . Вероятность: .
Свойства
1. Если , то	1q. Если , то .
2. (в общем случае) .	2q. Если , то .

Заметим, что условие эквивалентно условию .

Если есть два неортогональных подпространства с пустым пересечением, то квантовая вероятность необязательно аддитивна. Приведем простой пример, когда .

Пусть , (линейное подпространство, порожденное вектором ), , причем близко к 1. Тогда

Итак, мы определили в наиболее общем виде то, что мы измеряем. Теперь нужно обобщить то, над чем проводится измерение. В результате получим определение вероятности, обобщающее как классическую, так и квантовую вероятность.

Рассмотрим распределение вероятностей на конечном множестве квантовых состояний . Вероятность состояния обозначим , очевидно, что . Подсчитаем вероятность наблюдения состояния в подпространстве :

(9.2)

где через обозначена матрица плотности1) . Последнее выражение в (9.2) и примем за общее определение вероятности.

Задача 9.1. Докажите, что операторы вида -- это в точности эрмитовы неотрицательно определенные операторы со следом 1, т.е. операторы, удовлетворяющие условиям:



В дальнейшем под матрицей плотности понимается любой оператор с этими свойствами.

Рассуждение о "распределении вероятностей на квантовых состояниях" носило вспомогательный характер. Задача состоит в том, чтобы обобщить понятие квантового состояния так, чтобы оно включало в себя классические распределения вероятностей. Полученный нами ответ (последнее выражение в (9.2)) зависит лишь от матрицы плотности, поэтому мы можем постулировать, что обобщенные квантовые состояния и матрицы плотности -- это одно и то же (такая аксиома не противоречит физическим наблюдениям). Если состояние задается одним вектором ( ), то оно называется чистым, если состояние задается общей матрицей плотности, то оно называется смешанным.

Определение 9.1. Для квантового состояния, задаваемого матрицей плотности , и подпространства вероятность "события" равна .

Диагональные матрицы соответствуют классическим распределениям вероятностей на множестве базисных векторов. Это означает, что при вычислении вероятности по общей квантовой формуле для диагональной матрицы и координатного подпространства (натянутого на часть базисных векторов : ) получается то же, что и при вычислении по обычной классической формуле: .

Продолжим сравнение свойств классической и квантовой вероятности, под последней мы будем теперь понимать общее определение с использованием матриц плотности. (Свойства и остаются в силе).

Классическая вероятность

Квантовая вероятность

Свойства

3. На множестве задано распределение вероятностей вида . Имеется два множества исходов , . Тогда вероятности перемножаются: .

3q. На пространстве задана матрица плотности вида . Имеется два подпространства , . Тогда вероятности также перемножаются: .

4. Имеется совместное распределение на множестве . Интересующее нас событие не зависит от исхода во втором множестве: . Вероятность такого события выражается через проекцию распределения на первое множество: , где .

4q. В квантовом случае ограничение на одну из подсистем задается операцией взятия частичного следа (см. ниже). Поэтому, даже если исходное состояние было чистым, полученное состояние подсистемы может оказаться смешанным: .

Определение 9.2. Пусть . Частичный след оператора по пространству определен следующим образом: если , то .

Докажем, что это определение корректно, т.е. не зависит от выбора слагаемых в представлении . Для этого зафиксируем некоторые ортонормированные базисы в пространствах и выразим частичный след через матричные элементы . Пусть

и . Тогда

и частичный след равен



Рассмотрим пример, когда взятие частичного следа от матрицы плотности, соответствующей чистому состоянию, приводит к матрице плотности, соответствующей смешанному состоянию.

Пусть , а , где . В этом случае , поэтому получаем

Эта матрица соответствует смешанному состоянию (чистым состояниям соответствуют матрицы ранга 1). Более того, это смешанное состояние эквивалентно классическому распределению вероятностей: и имеют вероятности, равные . Таким образом, отбрасывание второго q-бита приводит к чисто классическому распределению вероятностей на первом q-бите.

Утверждение 9.1. Любое смешанное состояние представимо как частичный след от чистого состояния большей системы, , причем можно считать, что .

Доказательство. Полагаем . Так как неотрицательно определена, то существует . Докажем, что для выполнено искомое, т.е. .

Поскольку эрмитова, она диагонализуется в некотором ортонормированном базисе . Тогда , а , и . Вклад в частичный след вносят лишь слагаемые с . Поэтому .

Задача 9.2. Пусть имеется чистое состояние . Докажите, что существует так называемое разложение Шмидта:

где , а множества векторов и являются ортонормированными.

Заметим, что числа -- это ненулевые собственные числа частичных следов и . (Таким образом, ненулевые собственные числа и совпадают.) Отсюда следует, что взятие частичного следа от чистого состояния приводит к чистому состоянию тогда и только тогда, когда исходное состояние разложимо: .

Задача 9.3. Пусть -- два чистых состояния, таких что . Докажите, что для некоторого унитарного оператора на пространстве .



Лекция №10

Тема 10.1 Физически реализуемые преобразования матриц плотности

Теперь опишем, какие преобразования матриц плотности допустимы с физической точки зрения.

Унитарный оператор переводит матрицу плотности чистого состояния в матрицу . Естественно считать (по линейности), что такой же формулой задается и действие унитарного оператора на произвольные матрицы плотности:

Второй тип преобразования состоит во взятии частичного следа. Если есть , то отбрасывание второй системы задается преобразованием

Вспомним, что нам еще бывает нужно брать напрокат q-биты в состоянии 0. Пусть есть состояние . Рассмотрим изометрическое (сохраняющее скалярные произведения) вложение в пространство большей размерности, задаваемое формулой . Матрица плотности при этом преобразуются в . Для любого изометрического вложения по аналогии полагаем



Будем считать, что физически реализуемые преобразования матриц плотности есть в точности композиции любого числа преобразований типа 2 и 3 (случай 1 -- частный случай преобразования типа 3).

Задача 10.1. Докажите, что любое физически реализуемое преобразование матриц плотности имеет вид , где -- изометрическое вложение.

Операция взятия частичного следа означает забывание (отбрасывание) одной из подсистем. Покажем, что такая интерпретация является разумной, а именно, дальнейшая судьба отброшенной системы не влияет на величины, характеризующие оставшуюся систему. Возьмем систему, состоящую из двух подсистем и находящуюся в некотором состоянии . Если мы выбрасываем вторую систему (в мусорную корзину), то она будет подвергаться неконтролируемым воздействиям. Пусть мы применили какой-то оператор к первой системе. Получили состояние , где -- произвольный унитарный оператор (действие мусорной корзины на мусор). Если мы хотим найти вероятность для подпространства , относящегося к первой системе (мусор нас не интересует), то она не зависит от и равна

Здесь первое равенство -- это свойство 4q квантовой вероятности, а второе равенство -- новое свойство:

(10.1)

Задача 10.2. Докажите тождество (10.1) для частичного следа.

Задача 10.3. Запишем линейный оператор в координатном виде:

Докажите, что физическая реализуемость эквивалентна набору из трех условий:

(символ Кронекера);

;

-- неотрицательная матрица (по парам индексов).

Задача 10.4. Докажите, что линейный оператор является физически реализуемым преобразованием матриц плотности тогда и только тогда, когда выполнены три условия:

для любого ;

для любого ;

является вполне положительным преобразованием. А именно, для любого пространства преобразование отображает неотрицательные операторы в неотрицательные.

Тема 10.2 Подсчет вероятностей для квантового вычисления

Теперь, имея общие определения квантовой вероятности и физически реализуемого преобразования матриц плотности, можно вычислять вероятности, входящие в определение квантового вычисления, двумя способами. Пусть мы использовали при вычислениях дополнительную подсистему. После того, как она стала нам не нужна, мы можем выбросить ее в мусорную корзину, а при подсчете вероятности взять частичный след по пространству состояний дополнительной подсистемы. А можно тянуть весь этот мусор до самого конца и считать вероятность для событий вида (раз уж мы перестали использовать вторую подсистему, то никакие детали ее состояния нам не важны -- нам безразлично, что именно произойдет с использованной подсистемой в мусорной корзине). Как уже говорилось, эти вероятности равны: .

Замечание. Нетрудно определить более общую модель квантового вычисления, в которой элементарными действиями являются подходящие преобразования матриц плотности общего вида (не обязательно унитарные операторы). Такая модель более адекватна физической ситуации, когда квантовый компьютер взаимодействует с "окружающей средой". С вычислительной точки зрения новая модель эквивалентна стандартной (если в обоих случаях используется полный базис). Однако в модели с общими преобразованиями матриц плотности возможно более естественное определение подпрограммы для квантового вычисления, поскольку результат работы квантовой схемы -- вероятностная функция. Здесь мы не будем давать этого определения и отсылаем заинтересованного читателя к [20].

Потеря когерентности (decoherence).

Рассмотрим в качестве примера преобразование матриц плотности, которое "забывает" внедиагональные элементы:

Покажем, что оно "физически реализуемо", т.е. может быть построено композицией описанных выше преобразований. Будем строить это преобразование в три шага. Вначале добавим нулевые биты:

Затем скопируем обратимым образом исходные биты в добавленные. Обратимое копирование задается оператором . Получаем

А теперь возьмем частичный след по добавленным битам. Получим диагональную матрицу

Предостережение. Рассмотренная нами "операция копирования"

(композиция первых двух преобразований) на самом деле копирует только базисные состояния. Заметим, что копирование произвольного квантового состояния является нелинейным оператором, поэтому не может быть реализовано физически. В дальнейшем копирование всегда будет определяться относительно некоторого базиса.

Замечание 10.2. Рассмотренное преобразование переводит любое состояние в классическое (с диагональной матрицей плотности), используя копирование битов. Это можно интерпретировать так: если постоянно наблюдать за системой (делать копии), то система будет вести себя как классическая. В случае одного q-бита то же самое преобразование (обнуление внедиагональных элементов) можно получить, если применить оператор с вероятностью :

Подобный процесс называется случайным сбоем фазы: состояние домножается на фазовый множитель с вероятностью . Таким образом, сбой фазы также приводит к тому, что система ведет себя как классическая.

Задача 10.5. Пусть имеется физически реализуемое преобразование со следующим свойством: для любого чистого состояния . Докажите, что тогда (для любого оператора ), где -- некоторая фиксированная матрица плотности на пространстве .

Таким образом, нельзя получить никакой информации о неизвестном состоянии , не возмущая это состояние.

Тема 10.3 Измерение

При описании квантовых алгоритмов часто бывает естественно считать, что наряду с квантовым вычислительным устройством используется и классическое. Основной механизм взаимодействия между квантовой и классической частями состоит в измерении квантовых регистров, дающем классический результат.

Рассмотрим систему, состоящую из двух частей, -- квантовой ( ) и классической ( ). По классическим координатам матрица плотности диагональна:

где -- вероятность иметь классическое состояние , а оператор обладает всеми свойствами матрицы плотности. Таким образом, квантово-классическое состояние всегда разложимо на "условные" (по аналогии с условными вероятностями) матрицы плотности . Будем использовать для такого случая специальное обозначение: .

Пусть имеется ряд взаимоисключающих возможностей, что выражается разложением пространства состояний в прямую сумму попарно ортогональных подпространств

где -- множество возможностей (действительно, если подпространство ортогонально подпространству , то для любой матрицы плотности выполняется ).

Преобразование матриц плотности, которое мы будем называть измерением, состоит в том, что для состояний из подпространства "измеряющий прибор" помещает в классический регистр номер состояния :

(10.2)

Хотя измерение отображает пространство в , результат всегда диагонален по второй компоненте. Поэтому можно считать, что измерение отображает в .

Для выполняется равенство . Поэтому из соображений линейности можно доопределить измерение на всех остальных матрицах плотности

и прийти к следующему определению.

Определение 10.1. (Детерминированным) измерением называется преобразование матриц плотности

(10.3)

где .

Можно сказать, что -- это результат измерения, -- вероятность получить данный результат, а -- состояние измеряемой системы после измерения при условии, что получен результат . Если мы измеряем чистые состояния, т.е. , то , где .

Приведем простейший пример измерения. Сделаем две копии бита. Пусть , а . Тогда

Задача 10.6. "Квантовая телепортация" (см. [21]). Пусть имеются три q-бита: первый из них находится в произвольном (заранее неизвестном) состоянии , второй и третий -- в состоянии

Произведем над первыми двумя q-битами измерение, соответствующее ортогональному разложению

Покажите, что используя результат измерения и оставшийся третий q-бит, можно восстановить исходное состояние . Запишите всю последовательность действий (измерение и восстановление) в виде квантовой схемы.

Замечание 10.3. Этот процесс можно представлять таким образом. Допустим, что Алиса хочет передать Бобу1) квантовое состояние по классическому каналу связи (например, по телефону). Оказывается, что это возможно, если Алиса и Боб заранее приготовили состояние и взяли от него по половинке -- одному q-биту. Алиса производит измерение и сообщает результат Бобу. Затем Боб переводит свой q-бит в состояние .



Лекция №11

Тема 11.1 Измеряющие операторы

Введем особый класс операторов -- измеряющие операторы. Пусть есть пространство состояний , причем первый сомножитель разложен в прямую сумму попарно ортогональных подпространств: . Тогда всякий оператор вида будем называть измеряющим.

Чтобы оправдать такое название, рассмотрим следующий процесс. Пусть имеется некоторое состояние, описываемое матрицей плотности . Подсоединим прибор ; совместное состояние системы и прибора описывается матрицей плотности (мы считаем, что во втором сомножителе, описывающем прибор, есть выделенный базис, например, что это ).

Теперь применяем измеряющий оператор . Получаем состояние

(здесь мы воспользовались характеристическими свойствами проектора , ).

И последнее действие: прибор становится классическим. Это означает, что матрица диагонализуется по второму сомножителю. Посмотрим, во что переходят при этом вторые сомножители в написанной сумме:

Теперь запишем получившийся результат:

где введены условные вероятности . Заметим, что для измерения (как оно было определено в предыдущем разделе) , поэтому только что описанный процесс можно назвать "вероятностным измерением". Введенные таким образом квантовые условные вероятности ведут себя как обычные, если рассматриваются произведения измеряющих операторов, построенных на одном и том же ортогональном разложении пространства состояний (см. ниже).

Приведем примеры измеряющих операторов.

1. Оператор , действующий на пространстве , -- измеряющий.

1'. Нетривиально, что он измеряющий и по второй компоненте. Поскольку -- унитарный оператор, его можно разложить в сумму проекторов на собственные подпространства: , . Тогда . В этом случае условные вероятности равны и , поэтому такой оператор, хотя и является измеряющим по определению, фактически ничего не измеряет.

Замечание для физиков. Пусть -- оператор фазового сдвига света при прохождении сквозь стеклянную пластинку. Мы можем разделить луч света на два, пропустив его через полупрозрачное зеркало, затем один из полученных лучей пропустить через стеклянную пластинку, а затем заставить полученные в результате лучи интерферировать. По картине интерференции можно узнать фазовый сдвиг.

Математический вариант предыдущего примера. Аналогом полупрозрачного зеркала будет служить оператор

Как видно из приведенной выше картинки, его нужно применить в начале и в конце. Строго говоря, рассмотрим оператор

Если начальный вектор имеет вид ( ), то , где

Поэтому

Теперь подсчитаем условные вероятности. Собственные числа унитарного оператора равны по модулю 1, поэтому можно полагать . В результате имеем

В дальнейшем именно с помощью такого оператора мы будем оценивать собственные числа. Для этого придется брать разные биты в качестве первых сомножителей (разные "приборы"). Конечно, следует убедиться, что это корректно (т.е., что вероятности будут перемножаться).

Тема 11.2: Свойства измеряющих операторов.

Мы будем рассматривать измеряющие операторы, соответствующие одному и тому же ортогональному разложению .

1. Произведение измеряющих операторов -- измеряющий оператор. Действительно, пусть есть два измеряющих оператора

Поскольку , имеем

2. Условные вероятности для произведения измеряющих "разными приборами" операторов перемножаются. Более точно, пусть , а . Тогда . Это равенство следует непосредственно из определения условных вероятностей и из очевидного тождества



3. Формула полной вероятности. Пусть есть измеряющий оператор . Если применить его к состоянию , где , то вероятность наблюдения состояния можно записать в виде:

Доказательство. . Ранее было доказано, что . Далее,

Поскольку

получаем искомое выражение .

Задача 11.1. Докажите формулу полной вероятности напрямую, не используя взятия частичного следа.

Задача 11.2. "Обратимое измерение" Пусть -- измеряющий оператор, . (Имеется в виду, что операторы действуют на q-бит; первые q-бит (т.е. ) -- "полезный результат", остальные q-бит (т.е. ) -- "мусор".) Допустим, что измеряет некоторую функцию с вероятностью ошибки , т.е.



Постройте c использованием и квантовую схему полиномиального размера, реализующую с точностью новый измеряющий оператор

(Разрешается "брать напрокат" дополнительные q-биты.)



Лекция №12

Тема 12.1 Быстрый квантовые алгоритмы

Единственное нетривиальное использование квантовых свойств для вычислений, которое мы уже рассмотрели, -- это решение универсальной переборной задачи алгоритмом Гровера, изложенным в лекции 8. К сожалению, при этом достигается лишь полиномиальное ускорение. Поэтому никаких серьезных следствий для теории сложности вычислений (типа ) алгоритм Гровера не дает. В настоящее время нет доказательства того, что квантовые вычисления превосходят по скорости классические вероятностные. Но есть косвенные свидетельства в пользу такого утверждения. Первое из них -- пример задачи с оракулом (т.е. процедурой типа "черного ящика"), для которой существует полиномиальный квантовый алгоритм, в то время как любой классический вероятностный алгоритм экспоненциален1). Этот пример, построенный Д. Саймоном [42], называется задачей о скрытой подгруппе в . В дальнейшем мы решим также задачу о скрытой подгруппе в , обобщающую все результаты из этого раздела.

Задача о скрытой подгруппе. Пусть -- конечная группа, причем задано некоторое представление элементов двоичными словами. Имеется устройство ( оракул ), вычисляющее функцию со следующим свойством:

(12.1)

где -- некоторая заранее неизвестная подгруппа. Нужно найти эту подгруппу.

Задача о скрытой подгруппе в .

Мы рассмотрим сформулированную выше задачу в случае . Элементы этой группы можно представлять строками длины из нулей и единиц; групповая операция -- побитовое сложение по модулю 2.

Легко доказать, что нельзя быстро найти "скрытую подгруппу" на классической вероятностной машине. (Классическая машина посылает на вход "черного ящика" строки и получает ответы . Каждый следующий вопрос зависит от предыдущих ответов и некоторого случайного числа .)

Утверждение 12.1. Пусть . Для любого классического вероятностного алгоритма, делающего не более обращений к оракулу, существует подгруппа и соответствующая функция , для которой алгоритм ошибается с вероятностью .

Доказательство. Для одной и той же подгруппы существует несколько различных оракулов . Мы будем считать, что один из них выбирается случайно и равновероятно. (Если алгоритм ошибается с вероятностью при случайном оракуле, то он также будет ошибаться с вероятностью при каком-нибудь конкретном оракуле.) Случайный оракул обладает следующим свойством: если очередной ответ не совпадает ни с одним из предыдущих ответов , то он равномерно распределен на множестве . Таким образом, случайный оракул эквивалентен устройству с памятью, которое на вопрос выдает наименьшее число , такое что . Классическую машину можно изменить таким образом, что она сама будет производить случайный выбор , когда .

Пусть число вопросов к оракулу равно . Без уменьшения общности все вопросы различны. В случае все ответы также различны, то есть для всех . Теперь рассмотрим случай , где выбирается случайно с равномерным распределением на множестве всех ненулевых элементов группы . Тогда, независимо от используемого алгоритма, c вероятностью . С вероятностью это имеет место для всех . Напомним, что у нас есть два случайных параметра: и . Мы можем зафиксировать таким образом, чтобы вероятность получения ответов (для всех ) по-прежнему была больше . Посмотрим, что будет делать классическая машина в этом случае. Если она выдает ответ " " с вероятностью , положим -- тогда выдаваемый ответ будет неверным с вероятностью . Если же вероятность ответа " " меньше , положим .

Теперь определим квантовый аналог описанного выше устройства. Соответствующий квантовый оракул -- это унитарный оператор

(12.2)

( обозначает побитовое сложение). Заметим, что квантовый оракул допускает линейные комбинации разных вопросов, поэтому его можно использовать более эффективно, чем классический оракул.

Пусть , а -- группа характеров на , т.е. гомоморфизмов . В случае группу можно охарактеризовать следующим образом:

где обозначает скалярное произведение по модулю 2. (Соответствующий характер имеет вид .) Покажем, как можно породить случайный элемент , используя оператор . Породив достаточно много случайных элементов, мы найдем группу , и, тем самым, исходную подгруппу D.

Начнем с того, что приготовим состояние в одном квантовом регистре. Во второй регистр поместим состояние и применим оператор . Затем выбросим второй регистр, т.е. не будем его больше использовать. Получится смешанное состояние

Теперь применим оператор :

Легко видеть, что величина отлична от нуля только в том случае, когда . Таким образом,

Это в точности матрица плотности для случайного равномерно распределенного элемента группы . Теперь осталось воспользоваться следующей леммой, которую мы сформулируем в виде задачи.

Задача 12.1. Пусть -- независимые случайные равномерно распределенные элементы абелевой группы . Докажите, что они порождают всю группу c вероятностью .

Таким образом, достаточно случайных элементов, чтобы породить всю группу с вероятностью ошибки . (Такая маленькая вероятность ошибки получается без особых затрат по сравнению с . Чтобы сделать ее еще меньше, эффективнее всего воспользоваться стандартной процедурой: повторить все вычисление несколько раз и выбрать наиболее часто встречающийся ответ).

Подведем итог: для нахождения "скрытой подгруппы" требуется обращений к квантовому оракулу. В целом алгоритм имеет сложность .

Тема 12.2 Разложение на множители и нахождение периода относительно возведения в степень

Второе свидетельство в пользу гипотезы -- быстрые квантовые алгоритмы разложения числа на простые множители и вычисления дискретного логарифма. Они были найдены П. Шором [38]. Обсудим пока первую из этих двух задач.

Факторизация числа. Дано натуральное число . Требуется найти его разложение на простые множители

Эта задача считается сложной настолько, что на предположении о трудности ее решения основываются практические алгоритмы криптографии. С теоретической точки зрения положение несколько хуже: неизвестно ни сведение к задаче факторизации задач из класса NP, ни другие "прямые" свидетельства в пользу ее сложности. (Слово "прямые" взято в кавычки из-за того, что в настоящее время неизвестен ответ на вопрос .) Таким образом, предположение о сложности задачи факторизации пополняет и без того обильную коллекцию недоказанных гипотез в вычислительной теории сложности. Количество таких гипотез хочется по возможности уменьшать. В этом и состоит основная ценность результата Шора -- если совершить один "акт веры" и уверовать в сложность задачи факторизации, то необходимость в еще одном акте веры (относительно больших вычислительных возможностей квантового компьютера) отпадает.

Мы будем строить быстрый квантовый алгоритм не для решения задачи факторизации, а для решения другой задачи Нахождение периода, к которой задача факторизации сводится с помощью классического вероятностного алгоритма.

Нахождение периода. Имеется число , записывающееся не более чем двоичными цифрами ( ) и число такое, что , ( обозначает наибольший общий делитель). Нужно найти период относительно , т.е. такое наименьшее неотрицательное число , что .

Другими словами, период -- это порядок числа в мультипликативной группе вычетов . Будем обозначать период числа относительно как .

Ниже мы построим квантовый алгоритм для решения задачи о нахождении периода числа. Но начнем с того, что опишем классическое вероятностное сведение задачи факторизации к задаче вычисления периода. Читателю также предлагается вспомнить вероятностный тест простоты числа, изложенный в первой части (см. лекцию 3).

Сведение факторизации к вычислению периода.

Итак, предположим, что мы умеем решать задачу нахождения периода. Ясно, что факторизацию числа можно получить, используя раз подпрограмму, которая по любому составному числу вычисляет какой-то его делитель с вероятностью, не меньшей . (Конечно, нужна также стандартная процедура усиления вероятностей, описанная в лекции 3.)