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

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

Теорема 4.2. тогда и только тогда, когда существует такая игра с полиномиальным от длины входного слова числом ходов и полиномиально вычислимым результатом, что Б имеет выигрышную стратегию .

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

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

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

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

Игра заканчивается, когда длина промежутка становится равной 1. Результат определяется так: для обоих концов этого промежутка в процессе игры были названы состояния . Если состояние правого конца получается из состояния левого конца за один такт работы , то Б выиграли, иначе выиграли Ч.

Если ответ на слове действительно "да", то белым нужно все время говорить правду, это гарантирует им выигрыш.

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

Задача 4.1. Докажите, что класс языков, распознаваемых недетерминированными машинами, работающими на памяти , содержится в классе языков, распознаваемых детерминированными машинами, работающими на памяти .

В качестве следствия теоремы 4.2 получаем включения всех определенных выше классов , в класс . Взаимное соотношение этих классов можно изобразить диаграммой включений, показанной ниже. На этой диаграмме от большего класса к меньшему можно пройти, двигаясь по стрелкам. Внизу располагается класс , отвечающий играм с 0 ходов, затем идут дополняющие друг друга классы, отвечающие играм с конечным числом ходов (для одного хода это NP и co-NP, для двух ходов -- и и т.д.). Завершается эта диаграмма классом , который определяется произвольными играми с одним естественным условием -- время игры должно быть полиномиально ограничено размером входного слова. Мы уже доказали все включения, изображенные на этой диаграмме. Ни про одно из включений, следующих из этой диаграммы, неизвестно, является ли оно строгим. Быть может, скажем, . С другой стороны, возможно и так, что , где обозначает (не рассматривавшийся нами) класс языков, вычислимых за экспоненциальное время . Впрочем, наиболее популярна гипотеза о том, что все включения, изображенные на диаграмме -- строгие.

Рисунок 4.1: Схема PSPACE

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

Докажите, что .

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

Задача . Задается предикатом

есть истинная булева формула с кванторами (True Quantified Boolean Formula), т.е. формула вида

где , -- некоторая логическая формула, а -- либо , либо . По определению, , а

.

Теорема 4.3. -полна.

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

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

Чтобы превратить в булеву формулу, добавим новые переменные (значение, вычисленное при -м присваивании в схеме) и заменим на формулу вида

где -- размер схемы, -- правая часть -го присваивания.

После этой подстановки получим квантифицированную булеву формулу, которая истинна в точности для .

Раздел №5. Квантовые вычисления

Тема 5.1 Квантовые вычисления

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

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

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

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

Пространство состояний для такой системы -- конечномерное (размерности ) пространство над полем комплексных чисел.

Состояния

Обычного компьютера

квантового компьютера

биты

q-биты

базисное:

произвольное:

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

Вычисление можно представлять как последовательность преобразований на множестве состояний системы. Опишем, какие преобразования возможны в классическом, а какие -- в квантовом случае.

Классический случай:

Квантовый случай:

преобразования -- это функции из в

преобразования -- это унитарные операторы, то есть операторы, сохраняющие длину вектора .

Замечание. Все сказанное относится только к замкнутым системам. Реальный квантовый компьютер -- это часть большой системы (Вселенной), взаимодействующая с остальным миром. Квантовые состояния и преобразования открытых систем будут рассмотрены в разделах 9-10.

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

Тема 5.2 Определения и обозначения

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

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

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

Другими словами, указанные векторы считаются равными 0.

Можно доказать, что данные определения эквивалентны.

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

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

Скалярное произведение антилинейно по первому аргументу1) и линейно по второму, т.е.

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

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

Унитарный оператор -- это линейный оператор, сохраняющий скалярное произведение. Условие

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

Наше определение скалярного произведения в согласовано с тензорным произведением:

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

Если операторы заданы в матричном виде в некотором базисе, т.е.

(легко понять, что -- линейный оператор: ), то матричные элементы оператора имеют вид .

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

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

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

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

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

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

Очевидно, что

(5.1)

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

Определение 5.1. Квантовая схема. Пусть -- некоторое множество унитарных операторов (базис). Тогда квантовая схема в базисе -- это последовательность , где -- множества q-битов,

Оператор, реализуемый квантовой схемой. Это оператор , равный .

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

Оператор , реализуемый схемой в расширенном смысле. Это такой оператор, что произведение

действующее на q-битов, , для любого вектора удовлетворяет условию .

Таким образом, мы "берем напрокат" дополнительную память, заполненную нулями, и должны возвратить ее в прежнем состоянии. Какой смысл имеет такое определение? Зачем нужно требовать, чтобы дополнительные q-биты вернулись в состояние ? На самом деле это условие чисто техническое, однако важно, чтобы вектор состояния в конце вычисления был разложим, т.е. имел вид (с произвольным ). Если это так, то первая подсистема находится в определенном состоянии , поэтому про вторую подсистему (дополнительную память) можно забыть. В противном случае, совместное состояние двух подсистем оказывается "запутанным" (entangled), поэтому первую подсистему нельзя отделить от второй.

Раздел №6. Соотношение между классическим и квантовым вычислением

Тема 6.1 Соотношение между классическим и квантовым вычислением

Классический объект, соответствующий унитарному оператору, -- перестановка. Любой перестановке естественно сопоставляется унитарный оператор в пространстве , действующий по правилу .

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

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

Перестановка, реализуемая обратимой схемой. Это произведение перестановок .

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

(действующее на битов, ) для любого удовлетворяет условию .

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

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

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

Задача 6.1. Докажите для обратимых схем полноту базиса, состоящего из отрицания и элемента Тоффоли.

Лемма 6.1. Пусть функция реализуется булевой схемой размера в некотором базисе . Тогда можно реализовать функцию обратимой схемой размера в базисе { , состоящем из функций ( ), а также функции .

Замечание 6.1. Помимо "полезного" ответа схема, указанная в формулировке леммы, производит "мусор" .

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

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

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

Каждое присваивание в схеме имеет вид , , . В обратимой схеме аналогом присваивания будет действие перестановки , , т.е. .

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

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

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

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

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

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

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

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

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

Поскольку задача TQBF PSPACE-полна, то достаточно вычислять на небольшой памяти значение формулы

(6.1)

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

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

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

В заключение сформулируем теорему о вычислении обратимых функций, которая является прямым обобщением леммы 6.2.

Теорема 6.1. Пусть и вычислимы булевыми схемами размеров . Тогда реализуется обратимой схемой размера .

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

Раздел №7. Базисы для квантовых схем

Тема 7.1 Точная реализация