Сегодня в рамках работы над книгой «Квантовые вычисления и функциональное программирование» я хотел бы представить на суд почтеннейшей публики свою очередную статью про квантовые вычисления.
Квантовая схемотехника — это, по сути, методология анализа и, главное, синтеза квантовых схем, реализующих те или иные алгоритмы (в общем понимании, не только квантовые). Обобщённо любой вычислительный процесс представляется в виде тройки (вход, процесс преобразования, выход). Принимая во внимание это соображение, задачами квантовой схемотехники можно назвать:
- Прямой анализ. При наличии схемы входа и описания вычислительного процесса определить схему выхода.
- Обратный анализ. При наличии описания вычислительного процесса и схемы выхода определить схему входа.
- Синтез. При наличии схем входа и выхода построить описание вычислительного процесса.
К сожалению, в имеющейся литературе по квантовым вычислениям данные вопросы практически не находят своего отражения (от силы есть пара источников на русском языке, где кратко рассматриваются некоторые из них), а именно они являются краеугольным камнем прикладного программирования. Поэтому далее в этой статье я постараюсь в полной мере раскрыть все три аспекта квантовой схемотехники.
Прямой анализ
С математической точки зрения эта задача решается достаточно просто. Входная схема — это описание множества возможных значений, которые могут быть поданы на вход квантовому вычислительному процессу. Поскольку квантовый регистр, то есть набор кубитов, может быть представлен в виде вектора, а каждый гейт в квантовой схеме представляет собой унитарную матрицу, то задача прямого анализа сводится к последовательному умножению матриц на вектор. А можно сначала перемножить все матрицы в правильном порядке, а затем итоговую матрицу умножить на входной вектор.
Проведя эту процедуру на всех возможных значениях входа (либо применив иные техники анализа), можно получить все выходные значения, после чего объединить их в схему. Данный вид анализа затрудняется тем, что при увеличении количества кубитов размерность векторов и матриц увеличивается экспоненциально. И если для квантовых регистров, состоящих из 1 — 3 кубитов такую процедуру ещё можно провести, то ручной анализ для четырёх кубитов уже затруднителен, а для десяти кубитов и больше уже сложно проводить и перемножение матриц на компьютере.
Обратный анализ
В рамках модели квантовых вычислений задача обратного анализа тривиально сводится к задаче прямого анализа. Поскольку вычисления являются обратимыми, а матрицы всех гейтов — унитарными, то для обратного анализа заданной квантовой схемы достаточно обратить её, то есть перекоммутировать гейты в обратном порядке, сделав выход входом и наоборот, а сами гейты преобразовать в эрмитово-сопряжённые. После этого проводится описанная ранее процедура прямого анализа.
Само собой разумеется, что вышеприведённые рассуждения применимы только к квантовым схемам, в которых нет операции измерения, которая является необратимой. С другой стороны, измерение обычно применяется в самом конце квантовых вычислений, когда необходимо получить классический результат, поэтому обращение схемы можно осуществить, отбросив операции измерения. И есть совсем немного квантовых алгоритмов, в которых измерение производится в середине процесса вычислений (например, квантовая телепортация), и к таким алгоритмам и их квантовым схемам этот метод обратного анализа не подходит, и надо использовать иные (если они вообще существуют — в общем случае обратная задача неразрешима).
Синтез
Задача построения квантовой схемы по заданным входу и выходу усиливается, по сравнению с классическим случаем, необходимостью обеспечить обратимость вычислений. В общем случае произвольный вычислительный процесс может быть описан как двоичная функция, принимающая на вход n битов и возвращающая m битов. Такая функция в классическом варианте может быть построена при помощи базисного (универсального) набора логических элементов.
Наличие классической схемы из универсального набора строительных блоков для заданной функции переводит задачу синтеза в задачу построения квантового оракула. Квантовый оракул строится из классического выражения функции следующим образом:
- Квантовый оракул будет иметь по (n + m) входов и выходов. Первые n входов принимают входные параметры функции, а следующие m входов инициализируются в
|0>. Соответственно, первые n выходов возвращают входные данные, а следующие m выходов получают сумму по модулю 2 (операция Исключающее ИЛИ) значения функции на заданном входе с m входными данными. - Все элементы классической схемы преобразуются в соответствующие квантовые гейты (например, можно воспользоваться универсальным набором из гейтов H и CNOT, либо квантовым аналогом элемента Тоффоли). Это может привести к появлению огромного количества так называемых мусорных кубитов.
- Построенная схема из универсальных квантовых элементов подвергается процессу оптимизации. Это довольно нетривиальный процесс, и в каждом случае применяются свои методы и техники. Цель этого процесса — свести количество мусорных кубитов к минимуму, желательно вообще их исключить.
- Если от мусорных кубитов избавиться не удалось (пусть их осталось l), то все они добавляются к входным и выходным (стало быть, входов и выходов становится (n + m + l)). Но эти кубиты должны быть вначале инициализированы в
|0>, а по окончании вычислений они также должны быть установлены в|0>. Это следствие законов квантовой механики.
Таким образом, будет построена квантовая схема классической функции. Однако, это не единственный способ. Другим вариантом является построение одной унитарной матрицы для представления полной классической функции. Эта задача может быть успешно разрешена при помощи решения системы уравнений, получаемой из произведения матрицы на вектор. Проблема лишь в том, что количество уравнений и неизвестных растёт экспоненциально от количества кубитов. И если количество входов и выходов равно (n + m), то количество уравнений и неизвестных в них будет равно, как полагается, 22(n + m). Решать такую систему просто для небольших чисел, а вот для больших уже проблематично.
В качестве примера можно рассмотреть построение квантового аналога классической логической операции И. Функция, реализующая эту операцию, имеет 2 входа и 1 выход, следовательно у квантового оракула будет по 3 входа и выхода. Следующая таблица показывает 8 возможных вариантов поведения квантового оракула.
| X1 | X2 | Y | X1 & X2 | (X1 & X2) ⊕ Y |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
Следовательно, система уравнений, которую надо решить, выглядит следующим образом:
Её решение тривиально, и результатом будет следующая матрица:
Эта матрица и есть квантовый оракул в матричном представлении. Теперь необходимо убедиться, что она унитарна. Для этого надо умножить её на эрмитово-сопряжённую. Поскольку эта матрица является самосопряжённой, то её надо просто возвести в квадрат. Несложные умозаключения дают понять, что результатом будет единичная матрица, то есть найденная матрица является унитарной.
Краткие пояснения. Единичная матрица в исходном уравнении получается из восьми строк вышеприведённой таблицы, в которых выделены столбцы 1, 2 и 3. Каждая из этих восьми строк преобразуется в вектор-столбец (здесь ради экономии показаны векторы-строки, но надо помнить, что это векторы-столбцы). Строка «0 0 0» представляет собой вектор (1 0 0 0 0 0 0 0), строка «0 0 1» представляет вектор (0 1 0 0 0 0 0 0) и т. д. до строки «1 1 1», которая есть вектор (0 0 0 0 0 0 0 1). Результирующая матрица строится по тому же принципу, однако теперь из таблицы берутся строки со столбцами 1, 2 и 5. Как видно, столбец 5 отличается от столбца 3 только в 7-ой и 8-ой строке, отсюда и перемена 7-го и 8-го столбцов в результирующей матрице.
Другими словами, для получения результирующей матрицы квантового оракула достаточно собрать векторы-столбцы по тому же принципу, как это описано в предыдущем абзаце. Для n входных кубитов берётся 2n строк, в каждой из которых (n + 1) столбец. Первые n столбцов принимают все возможные значения входных кубитов, а последний столбец — значение y ⊕ f(x). Для каждой строки ставится в соответствие вектор-столбец в вычислительном базисе, а потом все столбцы собираются в матрицу.
Задача решена. Хорошим упражнением для заинтересованного читателя будет построение таких же матриц для других пятнадцати двоичных функций от двух переменных.
Заключение
При всём описанном необходимо понимать, что синтез квантовой схемы — это не построение квантового алгоритма. Показанная здесь техника позволяет решать на квантовом компьютере произвольную вычислительную задачу. А разработка квантового алгоритма — это дело настолько необычное и нетривиальное, что чаще помогает озарение, нежели скрупулёзное построение шаг за шагом. На текущий день все разработанные квантовые алгоритмы базируются на нескольких базовых, которые были найдены именно при помощи озарения.
Мои предыдущие статьи по теме квантовых вычислений:
И ещё раз напоминаю про свой проект: «Квантовые вычисления и функциональное программирование».
Автор: Darkus
