Как работает квантовый компьютер: Объясняем на пальцах

С этим объяснением вы точно все наконец поймете.

Что такое квантовый компьютер? Вот определение этого термина, сокращенное до одного предложения:

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

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

Как хранит информацию обычный компьютер

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

Как хранит информацию квантовый компьютер

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

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

Пример того, как действует квантовый компьютер

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

Предположим, что отношения в группе распределяются следующим образом:

• Аня и Ваня — друзья;
• Аня и Сережа — враги;
• Ваня и Сережа — враги.

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

• Максимизировать число друзей;
• Минимизировать число врагов, попавших в одно и то же такси.

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

Решение задачи на обычном компьютере

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

• Аня едет в такси 0;
• Ваня также едет в такси 0;
• Сережа едет в такси 1.

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

С помощью трех битов можно представить любую из этих комбинаций.

Вычисление оценки для каждой конфигурации

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

• Максимизировать число пар друзей в автомобиле;
• Минимизировать количество пар врагов;

Давайте определим оценку следующим образом:

(оценка некоторого размещения) = (количество дружественных пар в автомобиле) — (число враждебных пар в автомобиле)

Предположим, что Аня, Ваня и Сережа сели в такси 1. В битах это выглядит как 111. В данной ситуации имеется только одна пара друзей — Аня и Ваня, но две враждебных пары: Аня и Сережа, Ваня и Сережа. Таким образом, общий балл этой конфигурации равен 1 — 2 = -1

Решение задачи

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

Как видно, имеется два правильных решения — 001 и 110. Оба набрали наибольшее количество очков (1). Эта задача довольно проста. Ее сложность стремительно возрастает по мере увеличения числа людей. С тремя пассажирами существует восемь возможных конфигураций. С четырьмя их число возрастает до 2 * 2 * 2 * 2 = 16 конфигураций. В общем случае с N пассажирами существует (2 в степени N) возможных расстановок. Если у нас всего 100 человек, необходимо просчитать:

2??? ~= 10?? = один миллион миллионов миллионов миллионов миллионов конфигураций.

Обычному компьютеру это не под силу.

Решение задачи на квантовом компьютере

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

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

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

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

В одном из миров кубит равен 0, в другом он равен 1. Что произойдет, если второй кубит также одновременно установить на 0 и 1? В этом случае у нас появится четыре параллельных мира. В первом мире оба кубита установлены на 0 (00). Во втором они равны 01. В третьем — 01, в четвертом — 11.

Похожим образом, если установить все три кубита на 0 и 1, возникнут восемь параллельных миров: 000, 001, 010, 011, 100, 101, 110 и 111.

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

В этом конкретном примере квантовый компьютер теоретически найдет одно из лучших решений за доли секунды (001 или 110):

На самом деле, чтобы вычислить эту задачу, необходимо задать квантовому два начальных условия:

• Все потенциальные решения, представленные кубитами;
• Функцию, которая каждому решению присваивает некую оценку. В данном случае она подсчитывает число дружеских и вражеских пар в автомобиле.

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

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

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

Масштабирование квантового компьютера

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

В случае четырех человек число операций остается прежним — 1. То же самое справедливо для 100 человек. Одной операцией квантовый компьютер вычисляет все 2??? ~= 10?? возможных конфигураций.

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

Источник: ru.ihodl.com

Комментарии: