Используя алгоритм Гровера, квантовый компьютер может найти нужную карту в среднем за семь попыток. Математика такова: в базе данных из N элементов классическому компьютеру необходимо N/2 попыток, а квантовому компьютеру достаточно и квадратного корня из N.

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

Квантовые вычисления

Эндрю Стин, преподаватель физики, Оксфордский университет

Сегодняшние компьютеры, при всей их удивительности, работают на том же фундаментальном принципе, что и механические устройства, о которых в XIX веке мечтал Чарлз Бэббидж и которые впоследствии описал Алан Тьюринг: одно стабильное состояние такой машины соответствует одному числу. Этот принцип характерен даже для таких, казалось бы, нестандартных вычислительных моделей, как модель, основанная на ДНК. Что еще им остается? И все же мир вокруг нас описывают тонкие законы квантовой физики, которые предлагают нам иначе взглянуть на вычисления. Квантовая физика предлагает мощные методы манипулирования информацией, которые мы только начинаем понимать.

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

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

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

Пока неясно, как лучше всего понять вычислительное преимущество, обеспечиваемое запутанностью. Одна из ее черт заключается в том, что, так как каждый кубит может добавить и 0, и 1 к любому заданному состоянию, всякий раз, когда к компьютеру добавляется один кубит, количество добавлений к состоянию компьютера удваивается, что приводит к поистине огромному числу добавлений (например, 2100 = 1267 миллиардов миллиардов миллиардов всего для 100 кубитов). В некоторых отношениях квантовый компьютер действует как совокупность огромного числа традиционных компьютеров, одновременно проводящих вычисления! Однако эта картина не дает полного представления о происходящем, потому что отдельные звенья любого такого квантового вычисления не могут быть полностью независимыми, а также должны снова оказываться вместе (и вступать в интерференцию друг с другом) до получения осмысленного результата.

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

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

Квантовые логические вентили

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

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

Квантовая логика работает сходным образом, только теперь нам приходится отслеживать все возможности. Квантовые алгоритмы вроде алгоритмов Шора и Гровера основываются на особом порядке, в