Квантовые вычисления со времен Демокрита - Скотт Ааронсон

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

где

есть единичная матрица.

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

Таким образом, возвращаясь к теме замкнутых времениподобных траекторий, если мы начинаем с глобального унитарного преобразования как кубитов типа CTC, так и кубитов, уважающих причинность, а затем «исключаем» (или игнорируем) хронологически верные кубиты, то у нас остается некоторый выведенный путем индукции супероператор S, который действует на CTC-кубиты. Тогда Природа в противовес ему найдет смешанное состояние ρ, представляющее собой неподвижную точку преобразования S, то есть такую, что S(ρ) = ρ. Не всегда возможно найти чистое состояние ρ = |ψ〉〈ψ| с такой характеристикой, но согласно обычной линейной алгебре (детали проработаны у Дойча) такое смешанное состояние всегда существует.

Упражнение для неленивого читателя. Докажите это.

Итак, ρ есть состояние непосредственно над CTC-кубитами. Единственная реальная причина для существования остальных кубитов — то, что без них супероператор всегда был бы унитарным, а в этом случае максимально смешанное состояние I всегда было бы неподвижной точкой. Это сделало бы модель тривиальной.

Согласно общему принципу, квантовые компьютеры способны имитировать классические, и (как несложно показать) при добавлении замкнутых времениподобных траекторий ситуация не меняется. Так что мы можем с уверенностью сказать, что BQPCTC включает в себя PSPACE. Но какова верхняя оценка BQPCTC?

EXPSPACE наверняка подойдет. Можете ли вы дать более точную верхнюю оценку?

Итак, нам дан n-кубитный супероператор (заданный явно в виде схемы), и мы хотим найти в нем неподвижную точку. По существу, это задача из линейной алгебры. Мы знаем, что вычисления линейной алгебры можно проделать за время, полиномиальное в размерности гильбертова пространства, которая в данном случае равна 2n. Это подразумевает, что мы можем имитировать BQPCTC в EXP. Так что мы теперь знаем, что BQPCTC располагается где-то между PSPACE и EXP. В моем обзорном докладе об NP-полных задачах и физической реальности[179] уточнение положения этого класса было названо главной нерешенной формальной задачей!

Около 2008 г. мы с Джоном Ватрусом сумели эту проблему решить[180]. Мы доказали, что BQPCTC = PCTC = PSPACE. Иными словами, если бы замкнутые времениподобные траектории существовали на самом деле, то квантовые компьютеры были бы не мощнее классических.

Студент: Знаем ли мы что-нибудь о других классах с замкнутыми времениподобными траекториями? Таких как PSPACECTC?

Скотт: Этот класс тоже совпадает с PSPACE. С другой стороны, нельзя просто взять произвольный класс сложности и приписать к нему индекс CTC. Нужно сказать точно, что это означает, к тому же для некоторых классов (таких как NP) это вообще не имело бы смысла.

В последней части этой главы я могу намекнуть вам, почему BQPCTC ⊆ PSPACE. Если дан супероператор S, описанный полиномиального размера квантовой схемой, которая отображает n кубитов на n кубитов, то наша цель — вычислить смешанное состояние ρ, такое, что S(ρ) = ρ. Мы не сможем записать ρ явно (получится слишком длинно для памяти PSPACE-машины), но нам и нужно всего лишь имитировать результат некоторого полиномиального по времени вычисления, которое можно было бы произвести над ρ.

Пусть vec(ρ) — «векторизация» ρ (вектор из 22n компонент, по одному на каждый элемент матрицы ρ). Тогда существует матрица M размера 22n × 22n, такая, что S(ρ) = ρ для любого ρ в том и только том случае, когда M vec (ρ) = vec(ρ). Иными словами, мы можем просто расширить все, от матриц до векторов, и затем нашей целью будет найти a + 1 собственный вектор M.

Определим P:= limz→1 (1 — z) (I — zM)–1. Тогда по разложению в ряд Тейлора

Иными словами, P проецируется на неподвижные точки M. Для любых v имеем M(Pv) = (Pv).

Таким образом все, что нам теперь нужно сделать, это начать с какого-нибудь произвольного вектора v, скажем vec(I), где I есть максимально смешанное состояние, и затем вычислить:

Но как применить эту матрицу P в PSPACE? Ну, мы можем применить M в PSPACE, поскольку это всего лишь полиномиальное по времени квантовое вычисление. Но как насчет того, чтобы найти обратную матрицу? Здесь мы заимствуем кое-что из вычислительной линейной алгебры. Алгоритм Чанки, предложенный в 1970-х гг., позволяет нам вычислить матрицу, обратную матрице n × n, не просто за полиномиальное время, но при помощи схемы глубиной log² n. Аналогичные алгоритмы реально используются сегодня, к примеру, при проведении научных расчетов с участием множества параллельных процессоров. Далее, «подняв все наверх» в показатели степеней, мы обнаруживаем, что можно обратить матрицу размером 22n × 22n при помощи схемы размером 2O(n) и глубиной O(n²). Но вычисление результата работы схемы экспоненциального размера и полиномиальной глубины (описанной неявно) — это расчет класса PSPACE, более того, это PSPACE-полный расчет. В качестве финального шага можно взять предел при z → 1 при помощи алгебраических правил и еще кое-каких фокусов, за которые мы должны благодарить Бима, Кука и Хувера[181].

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

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

Поскольку в первый раз эта глава писалась в 2006 г., с тех