Книга: Размышления о думающих машинах. Тьюринг. Компьютерное исчисление

КАК РАБОТАЕТ КВАНТОВЫЙ КОМПЬЮТЕР

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

Если компьютер представляет данные в виде последовательности единиц и нулей, то есть битов, квантовый компьютер, как мы уже говорили, использует кубиты. Мысль о возможности сконструировать квантовый компьютер впервые высказал в 1982 году знаменитый физик Ричард Фейнман. Сегодня разработка этого типа компьютеров находится на начальном этапе. Недавно были проведены опыты с небольшим количеством кубитов, а также были разработаны симуляторы подобных компьютеров на традиционных машинах. Но для того чтобы традиционный компьютер мог выполнить квантовый алгоритм, необходим большой объем памяти и высокая вычислительная мощность, а также особые требования к комплектующим. Тем не менее даже простые опыты, которые возможно осуществить, помогают освоить новую технологию. Существующие симуляторы ограничиваются несколькими кубитами, так как современные технические средства не позволяют хранить, например, сразу 500 кубит.

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

РИС.1

Также нужно уточнить, что двоичная система счисления (база два) оперирует двумя возможными символами, 0 или 1, а десятичная система (база десять) — десятью возможными символами (0, 1, 2,..., 9). Число в каждой системе счисления представляет собой комбинацию символов. Так как двоичная система является внутренним языком компьютеров, преобразование чисел из одной системы в другую является обычной практикой. Для перевода двоичного числа в десятичный вид необходимо представить это число как сумму произведений последовательных степеней основания двоичной системы счисления (2) на соответствующие цифры в разрядах двоичного числа справа налево. Так, если в двоичной системе перед нами число 1011, мы действуем следующим образом: первый знак 1 справа умножаем на 2° (нулевая степень любого числа равна единице), следующий знак 1 умножаем на 20 знак 0 — на 2², знак 1 — на 2³. Теперь вычислим сумму полученного выражения 1 · 2³ + 0 · 2² + 1 · 2¹ + 1 · 20. Результат будет эквивалентным десятичным числом, в нашем случае — 11. На практике если двоичные числа состоят из четырех разрядов, результаты, полученные с помощью описанного метода, можно занести в таблицу.

Как мы можем представить число в кубитах?

Например, нам нужно представить число 9 (схема 2). В двоичной системе его эквивалентом будет 1001, так как вычислив 1 · 2³ + 0 · 2² + 0 · 2¹ + 1 -20 (помним, что 20 = 1), получим 9.

Следовательно, |9> соответствует 11001>. А число 8? |8) соответствует 11000>. Это означает, что квантовый компьютер представляет числа 8 и 9 так же, как и обычный.

Однако он также может представлять и выполнять операции суперпозиции, например с |8> + |9>.

РИС. 2

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

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

У нас есть два кубита, которые обозначим А и В, в состояниях 0 и 1. Представим их, согласно системе счисления, в виде |0>A и |1>B соответственно. Если они запутаны, нужно использовать символ ®, применяемый в математике для обозначения операции тензорного произведения, как показано далее:

В предыдущем выражении 1/?2

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

(1/?2)2,

получаем 1/2. Это позволяет измерить состояния в квантовом эксперименте и получить результаты |01> или |10>.

Представим, что Алан Тьюринг — друг Эндрю Ходжеса, его лучшего биографа, и что он может измерить, в каком состоянии находится кубит А, а Ходжес может измерить, в каком состоянии находится кубит В. Для того чтобы сделать эксперимент еще более эффектным, представим, что Алан и Эндрю находятся в разных комнатах и оба имеют устройство для измерения состояния кубитов.

РИС.З

В данном эксперименте интересно то, что если, например, Алан первым измерит состояние своего кубита (А), он узнает, что оно равно |0>A или |1>A, и вероятность того и другого события, как и при подкидывании монетки, составляет 50%. Однако фантастический аспект квантового исчисления состоит в том, что измерение Аланом кубита станет причиной коллапса, который произойдет после выяснения его состояния. В результате для Эндрю, находящегося в другой комнате, учитывая, что кубиты запутаны, эксперимент потеряет характер случайности. Если теперь Эндрю все же будет измерять свой кубит (В), результат его наблюдений заведомо известен. То есть для Эндрю результаты эксперимента уже не эквивалентны подбрасыванию монетки, так как в 100% наблюдений он получит результат, обратный результату Алана (схема 3). Например, если Алан увидел, что запутанный кубит А находится в состоянии |0>A, произойдет коллапс пары кубитов |0>A и |1>B. Если же Алан увидел обратную ситуацию, а именно что А находится в состоянии |1>A, тогда произойдет коллапс пары кубитов |1>A и |0>B. То есть измерения, проведенные Аланом, «изменили» кубиты таким образом, что однозначно определили наблюдения Эндрю.

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

Наконец, если комплектующие компьютера используют вентили И, ИЛИ и другие, в квантовом компьютере используются квантовые вентили, оперирующие кубитами, и их операции имеют реверсивный характер. Например, при использовании вентиля ИЛИ в обычном компьютере, если выход равен 1, выполненная операция не реверсивна. Это означает, что невозможно установить, какими были входные данные: 0 или 1,1 или 0,1 или 1. Кроме того, класс операций с кубитами, которые может совершать квантовый компьютер, выше, чем класс операций с битами, так как состояния, в которых может находиться кубит, могут быть представлены как вектор в сфере, называемой сферой Блоха (схема 4). Программа blochsphere симулирует один кубит, а также операции, которые можно с ним выполнить.

Кроме логических операторов булевой алгебры (И, ИЛИ и другие), возможны другие операции с кубитами, определяющие вращение вектора по осям X, Y, Z сферы Блоха. Эти операции являются результатом применения так называемых квантовых вентилей, то есть квантовых цепей, производящих операцию над одним или несколькими кубитами. Например, вентили Паули и Адамара позволяют совершать вращения. Необходимо помнить, что хотя кубит представлен в сфере Блоха как вектор, на самом деле квантовые операторы представляют матрицы, которые при умножении на вектор-кубит дают новый вектор — измененный кубит. Вот простой пример оператора Паули класса х с матрицей

При применении ее к кубиту произойдет вращение сферы Блоха по оси Х и изменение |0> на |1> и |1> на |0>. Это эквивалентно оператору НЕ на обычном компьютере. Вентиль Адамара представляет особый случай: вращение вектора происходит одновременно по осям X и Z:

Другие операторы, такие как контролируемое отрицание (CNOT), swap, вентиль Тоффоли, позволяют выполнять контролируемые операции с двумя или тремя кубитами.

РИС. 4

Сфера Блоха. Кубит представлен вектором |?>. Состояния |0> и |1> находятся на севере и юге сферы, в остальных частях сферы — состояния суперпозиции.

РИС. 5

Еще одной особенностью квантового компьютера является то, что операции выполняются параллельно, то есть одновременно по разным линиям, например по линиям L1 и L2, комплектующие квантового компьютера предусматривают соединение одного за другим квантовых вентилей (U; рисунок 5).

В 2011 году канадская фирма D-Wave Systems объявила о старте продаж первого коммерческого квантового компьютера под названием D-Wave One. По заверениям фирмы, компьютер обладал микропроцессором на 128 кубит. В том же году команда исследователей из США, Китая и Японии объявила, что такой класс компьютеров может быть построен в соответствии с моделью архитектуры фон Неймана. В 2012 году IBM также сообщила, что сделаны значительные успехи в создании машины с такими характеристиками. Больше чем через полвека повторяется сценарий, имевший место с ENI АС, Colossus и другими компьютерами. Однако это не совсем верно, так как строительство квантового компьютера является настолько сложным проектом, что разные страны объединили усилия, создав многонациональные команды и оставив в прошлом межнациональное соперничество. Ожидается, что квантовый компьютер найдет применение не только в криптографии: с его помощью станет возможным более реалистическое моделирование, например воздействия медикаментов на человека, а также выполнение расчетов в физике, химии, астрономии и решение масштабных математических задач, таких как факторизация больших чисел.

Скорее из любопытства ученые уже создали квантовые версии игры «Жизнь» Конвея. Также в последнее время были предложены различные модели искусственных нейронных цепей, в которых нейроны симулируются квантовыми операторами, что открывает путь для дальнейших исследований в области квантового искусственного интеллекта. Еще одним применением квантового компьютера может стать генерация истинно случайных чисел, которые будут не псевдослучайными, а будто бы вытащенными из лотерейного барабана. Уже сегодня интернет дает возможность получить случайные числа с помощью квантовых феноменов (см. www.randomnumbers. info).

Оглавление книги