Демистификация принципов квантовых вычислений

«Думаю, я смело могу сказать, что квантовую механику никто не понимает», — Ричард Фейнман

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

В научно-популярных статьях опускаются описания квантовых систем и приводятся утверждения типа:

Обычный бит может быть равен «1» или «0», но кубит может быть одновременно равен «1» и «0».

Если вам сильно повезет (в чем я не уверен), то вам расскажут, что:

Кубит находится в суперпозиции между «1» и «0».

Ни одно из этих объяснений не выглядит правдоподобным, поскольку мы пытаемся сформулировать квантовомеханический феномен при помощи языковых средств, созданных в очень традиционном мире. Чтобы понятно объяснить принципы квантовых вычислений, необходимо применить другой язык — математический. 

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

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

Для начала давайте пробежимся по принципам цифровой логики. Она основана на использовании электрических схем для проведения вычислений. Чтобы сделать наше описание более абстрактным, упростим состояние электропровода до «1» или «0», что будет соответствовать состояниям «вкл» или «выкл». Выстроив транзисторы в определенной последовательности, мы создадим так называемые логические элементы, принимающие одно или несколько значений входных сигналов и преобразующие их в выходной сигнал на основе определенных правил булевой логики.

Распространенные логические элементы и таблицы их состояний

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

Как я уже упоминал ранее, нам необходим способ математического отображения цифровой логики. Для начала давайте представим математическую традиционную логику. С помощью линейной алгебры классические биты со значениями «1» и «0» можно представить в виде двух вектор-столбцов:

где цифры слева являются дираковскими обозначениями вектора. Представив наши биты таким образом, мы можем моделировать логические операции над битами с использованием векторных трансформаций. Обратите внимание: несмотря на то, что при использовании двух битов в логических элементах можно выполнять множество операций («И» (AND), «Не» (NOT), «Искл. Или» (XOR) и др.), при использовании одного бита возможно выполнение только четырех операций: тождественное преобразование, отрицание, вычисление константы «0» и вычисление константы «1». При тождественном преобразовании бит остается неизменным, при отрицании значение бита изменяется на противоположное (с «0» на «1» или с «1» на «0»), а вычисление константы «1» или «0» устанавливают бит в «1» или «0» вне зависимости от его предыдущего значения.

Identity	Тождественное преобразование
Negation	Отрицание
Constant-0	Вычисление константы «0»
Constant-1	Вычисление константы «1»

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

Прежде чем двинуться дальше, давайте обратимся к понятию обратимых вычислений, которое всего лишь подразумевает, что для обеспечения обратимости операции или логического элемента необходимо определить список значений входных сигналов на основании выходных сигналов и названий используемых операций. Таким образом можно заключить, что тождественное преобразование и отрицание являются обратимыми, а операции по вычислению констант «1» и «0» — нет. Благодаря унитарности квантовой механики квантовые компьютеры используют исключительно обратимые операции, поэтому на них мы и сосредоточимся. Далее мы преобразуем необратимые элементы в обратимые, чтобы обеспечить возможность их использования квантовым компьютером.

С помощью тензорного произведения отдельных битов можно представить множество битов:

Теперь, когда у нас имеются почти все необходимые математические представления, перейдем к нашему первому квантовому логическому элементу. Это оператор CNOT, или контролируемое «Не» (NOT), который имеет большое значение в обратимых и квантовых вычислениях. Элемент CNOT применяется к двум битам и возвращает два бита. Первый бит назначается «управляющим», а второй — «контрольным». Если управляющий бит установлен в «1», контрольный бит меняет своё значение; если управляющий бит установлен в «0», контрольный бит не изменяется.

Этот оператор может быть представлен в виде следующего вектора преобразования:

Чтобы продемонстрировать всё, с чем мы уже разобрались, я покажу варианты применения элемента CNOT в отношении множества битов:

Резюмируем уже сказанное: в первом примере мы раскладываем |10⟩ на части его тензорного произведения и используем матрицу CNOT для получения нового соответствующего состояния произведения; затем мы факторизуем его до |11⟩ в соответствии с приведенной ранее таблицей значений CNOT.

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

Если вы дочитали до этого места, то у меня для вас хорошая новость: кубиты легко можно выразить математически. В общем, если классический бит (cbit) может устанавливаться в |1⟩ или |0⟩, кубит просто находится в суперпозиции и до измерения может одновременно быть равен |0⟩ и |1⟩. После измерения он коллапсирует в |0⟩ или |1⟩. Иными словами, кубит можно представить в виде линейной комбинации |0⟩ и |1⟩ в соответствии с приведенной ниже формулой:

где a₀ и a₁ представляют, соответственно, амплитуды |0⟩ и |1⟩. Их можно рассматривать как «квантовые вероятности», которые представляют вероятность коллапсирования кубита в какое-либо из состояний после его измерения, поскольку в квантовой механике объект в суперпозиции коллапсирует в одно из состояний после фиксации. Разложим это выражение и получим следующее:

Чтобы упростить свое объяснение, именно этим представлением я буду пользоваться в настоящей статье.

Для этого кубита шанс коллапсирования в значение a₀ после измерения равен |a₀|², а шанс коллапсирования в значение a₁ равен |a₁|². Например, для следующего кубита:

шанс коллапсирования в «1» равен |1/ √2|², или ½, то есть 50/50.

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

Если вы знакомы с тригонометрией, то заметите, что это уравнение соответствует теореме Пифагора (a²+b²=c²), то есть мы можем графически представить возможные состояния кубита в виде точек на единичной окружности, а именно:

Логические операторы и элементы применяются в отношении кубитов также, как и в ситуации с классическими битами — на основании матричной трансформации. Все обратимые матричные операторы, которые мы вспомнили до настоящего момента, в частности, CNOT, могут использоваться для работы с кубитами. Такие матричные операторы позволяют использовать каждую из амплитуд кубита без его измерения и коллапсирования. Позвольте привести пример использования оператора отрицания к кубиту:

Прежде чем мы продолжим, я напомню, что значения амплитуд a₀ и a₁ на самом деле являются комплексными числами, поэтому состояние кубита наиболее точно можно отобразить на трехмерной единичной сфере, также известной как сфера Блоха:

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

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

Одним из самых важных операторов является «элемент Адамара»: он берет бит в состоянии «0» или «1» и ставит его в соответствующую суперпозицию с 50 %-шансом его коллапсирования в «1» или «0» после измерения. 

Обратите внимание, что в нижней правой части оператора Адамара присутствует отрицательное число. Это связано с тем, что результат применения оператора зависит от значения входного сигнала: — |1⟩ или |0⟩, и потому вычисление является обратимым.

Еще одним важным моментом, связанным с элементом Адамара, является его обратимость, то есть он может принимать кубит в соответствующей суперпозиции и преобразовать его в |0⟩ или |1⟩.

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

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

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

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

То есть, если мы начинаем с бита |0⟩, применяем инверсию бита, а затем — операцию Адамара, затем — еще одну инверсию бита, и еще раз — операцию Адамара, после чего — финальную инверсию бита, в итоге мы получаем вектор, приведенный в правой части цепи. Накладывая различные машины состояний друг на друга, мы сможем начинать с |0⟩ и отслеживать разноцветные стрелки, соответствующие каждого из преобразований, чтобы понять, как это всё работает.

Раз уж мы зашли так далеко, пришло время рассмотреть один из типов квантовых алгоритмов, а именно — алгоритм Дойча-Йожи, и показать его преимущество над классической вычислительной машиной. Стоит отметить, что алгоритм Дойча-Йожи является полностью детерминированным, то есть он возвращает правильный ответ в 100 % случаев (в отличие от многих других квантовых алгоритмов, основанных на вероятностном определении кубитов).

Давайте представим, что у вас есть черный ящик, который содержит функцию/оператор над одним битом (помните — при использовании одного бита возможно выполнение только четырех операций: тождественное преобразование, отрицание, вычисление константы «0» и вычисление константы «1»). Какая именно функция выполняется в ящике? Вы не знаете, какая, однако можете перебрать сколько угодно вариантов входных значений и оценить результаты на выходе.

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

В случае с классическим компьютером потребуется сделать 2 запроса для определения применяемой функции. Например, если при вводе «1» мы получаем на выходе «0», становится понятно, что используется либо функция вычисления константы «0», либо функция отрицания, после чего вам придется изменить значение входного сигнала на «0» и посмотреть, что получится на выходе.

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

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

Используя квантовый алгоритм, вы сможете определить, является ли функция в черном ящике постоянной или переменной на основании всего лишь одного запроса. Но прежде чем подробно рассматривать, как это сделать, нам нужно найти способ, который позволит структурировать каждую из таких функций на квантовом компьютере. Поскольку любые квантовые операторы должны быть обратимыми, мы сразу сталкиваемся с проблемой: функции вычисления констант «1» и «0» таковыми не являются.

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

До:	После:

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

Применив то же представление квантовой цепи, что мы использовали ранее, посмотрим, как можно реализовать каждый из четырех элементов (тождественное преобразование, отрицание, вычисление константы «0» и вычисление константы «1») с использованием квантовых операторов. 

Например, так можно реализовать функцию вычисления константы «0»:

Вычисление константы «0»:

Здесь нам вообще не нужны операторы. Первый входной кубит (который мы приняли равным |0⟩) возвращается с этим же значением, а второе входное значение возвращает само себя — как обычно.

С функцией вычисления константы «1» ситуация обстоит немного иначе:

Вычисление константы «1»:

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

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

Тождественное преобразование:

Использованный здесь символ обозначает элемент CNOT: верхняя линия обозначает контрольный бит, а нижняя — управляющий. Напомню, что при использовании оператора CNOT значение контрольного бита меняется, если управляющий бит равен |1⟩, но остается неизменным, если управляющий бит равен |0⟩. Поскольку мы приняли, что значение верхней линии всегда равно |0⟩, то её значение всегда присваивается нижней линии.

Аналогичным образом действуем с оператором отрицания:

Отрицание:

Мы просто-напросто инвертируем бит в конце выходной линии.

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

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

Элемент Адамара повторно применяется к результату использования функции, чтобы вывести кубиты из суперпозиции и сделать алгоритм детерминированным. Мы запускаем систему в состоянии |00⟩ и по причинам, о которых я сейчас расскажу, получаем результат |11⟩, если применяемая функция является постоянной. Если же функция внутри черного ящика переменная, то после измерения система возвращает результат |01⟩.

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

Использовав оператор инверсии бита, а затем применив элемент Адамара к обоим входным значениям, равным |0⟩, мы обеспечим их перевод в одинаковую суперпозицию |0⟩ и |1⟩, а именно:

На примере передачи этого значения функции в черном ящике легко продемонстрировать, что обе функции постоянного значения дают на выходе |11⟩.

Вычисление константы «0»:

Аналогично, мы видим, что функция вычисления константы «1» также дает на выходе |11⟩, то есть:

Вычисление константы «1»:

Обратите внимание: на выходе оба значения будут равны |1⟩, поскольку -1² = 1.

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

Тождественное преобразование:

Поскольку CNOT является двухкубитным оператором, его нельзя представить в виде простой машины состояний, и потому необходимо определить два выходных сигнала на основании тензорного произведения обоих входных кубитов и умножения на матрицу CNOT по описанному ранее принципу:

С помощью этого метода мы также можем подтвердить получение на выходе значения |01⟩, если в черном ящике скрыта функция отрицания:

Отрицание:

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

Что же дальше?

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

Мое описание сложно назвать полноценным руководством по квантовым вычислениям и алгоритмам — это, скорее, краткое введение в математику и систему обозначений, призванное развеять у читателей навязываемые научно-популярными источниками представления о предмете (серьезно, многие действительно не могут разобраться в ситуации!). Я не успел затронуть многие важные темы — например, такие как квантовая запутанность кубитов, комплексность значений амплитуды |0⟩ и |1⟩ и функционирование различных квантовых логических элементов при трансформации сферой Блоха.

Если вы хотите систематизировать и структурировать свои знания о квантовых компьютерах, настоятельно рекомендую вам прочитать «Введение в квантовые алгоритмы» (An Introduction to Quantum Algorithms) Эммы Штрубель: несмотря на обилие математических формул, в этой книге квантовые алгоритмы рассматриваются куда более подробно.

Источник: habr.com