Продолжение, часть 3 — здесь.

Квантовые операции (1)

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

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

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

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

𝑓: {0,1}^𝑛 → {0,1}^𝑚

Эта запись означает, что упорядоченному набору из n битов однозначно соответствует упорядоченный набор из m битов.

Для ясности, можно привести такое представление обычных, знакомых каждому ИТ-инженеру логических схем:

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

Набор элементов в таблице на рисунке 4-1 является в этом смысле базисным, но не минимальным, поскольку в нём есть избыточные элементы, которые могут быть выражены через другие элементы. Например, элемент ИЛИ может быть выражен при помощи комбинации двух элементов НЕ и одного элемента НЕ-И.

Что получается в случае квантовых вычислений?

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

В случае квантовых вычислений:

• Данные – это кубиты
• Операции – это квантовые вентили (или т.н. унитарные операторы)
• Результаты – это измерения.

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

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

Переходя на язык формул, можно сказать, что, при измерении состояния вектора волновой функции |ψ⟩ = α|0⟩ + β|1⟩, мы получаем 0 с вероятностью α² и получаем 1 с вероятностью β².

Более того, состояние вектора после измерения будет |0⟩ или|1⟩, в зависимости от результата, полученного при измерении. Это необычное явление называется «коллапсом волновой функции» (wave function collapse).

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

Представим себе кота, сидящего в ящике, в котором находится пробирка с ядом. Если происходит квантовое событие, с результатом |0⟩ или|1⟩, то, если при измерении будет получен результат, скажем |0⟩, то в результат означенного квантового события воображаемая пробирка не разбилась и кот остался жив. Если получен результат |1⟩, это значит, что что квантовое событие вызвало разрушение пробирки с ядом, и кот умёр. Однако несмотря на то, что квантовое событие произошло, и нам известны вероятности наступления обеих результатов, |0⟩ или|1⟩, мы не можем точно сказать, жив ли кот после квантового события, либо мёртв. Это мы можем узнать только проведя прямое измерение, то есть, открыв ящик и посмотрев, как чувствует себя наш бедный кот. Пока ящик закрыт, мы не можем сказать ничего более определённого, что кот жив с вероятностью α² и мёртв с вероятностью β².

Примерно такие результаты, в виде вероятностей, будут получаться после действия любого квантового оператора. Причем, как входных битов может быть не два, а больше, например, m, так и выходных битов может быть n (а не два, как в случае с котом Шрёдингера).

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

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

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

Более того, существует теорема невозможности клонирования.

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

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

Однако, вернёмся к квантовым операторам.

В квантовых вентилях (цепях) операции выполняются при помощи унитарных матриц (вентилей, «гейтов» — gates), которые обозначаются буквой U. Вентиль — это «унитарное преобразование», некоторая квадратная матрица U, размерность которой соответствует количеству базовых квантовых состояний, подчиняющаяся простому свойству:

𝑈†𝑈=𝑈𝑈†=𝐼

где 𝑈† — т.н.  «эрмитово-сопряжённая» матрица к 𝑈, а 𝐼 – единичная матрица. Эрмитовое сопряжение – это операция над квадратными матрицами с комплексными числами. Для того чтобы получить эрмитово-сопряжённую матрицу, необходимо транспонировать матрицу и заменить все числа в ней на их комплексно-сопряжённые. Например, так:

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

𝑈†(𝑈|𝜑⟩)=𝑈†𝑈|𝜑⟩=(𝑈†𝑈)|𝜑⟩=𝐼|𝜑⟩=|𝜑⟩

Самым простым унитарным оператором является единичная матрица 𝐼. Эрмитово-сопряжённой к ней является она сама же, а произведение двух единичных матриц есть единичная матрица.

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

Например, это операторы Паули, которые поворачивают кубиты вокруг различных осей в трёхмерном пространстве. Эти операторы используют обозначения: X, Y и Z (аналогично осям в трёхмерном пространстве).

Оператор Паули X работает так:

На схемах квантовых вычислений операторы Паули обозначаются следующим образом обозначаются :

Операторы Паули являются квантовым аналогом двоичного логического элемента НЕ, поскольку они переводит кубит |0⟩ в |1⟩, и наоборот.

По сути, оператор Паули просто поворачивает кубит в сфере Блоха так, что после операции вектор кубита смотрит в прямо противоположную сторону сферы.

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