Квант. Путеводитель для запутавшихся

Само собой, отдельный кубит не очень полезен. Но если запутать два кубита или более, потенциал такой системы станет очевиден. Представьте информационное содержание трех классических битов. Каждый может принимать значение либо 0, либо 1, поэтому существует восемь различных комбинаций этой тройки (000, 001, 010, 100, 011, 101, 110, 111). Но всего три запутанных кубита позволяют нам хранить все восемь комбинаций одновременно! Каждая из трех цифр одновременно принимает значение и 0, и 1.

Добавление четвертого кубита дает нам 16 комбинаций, пятого – 32 и так далее. Объем хранимой информации увеличивается экспоненциально (как 2^N, где N – это число кубитов). Теперь представьте осуществление операций тем же способом, который мы применяем к классическим битам. Мы сможем выполнить 2^N вычислений одновременно, и это максимально возможная скорость параллельной обработки данных. Определенные проблемы, на решение которых у обычного компьютера ушли бы годы, в результате могут оказаться решены за долю секунды.

Так на что способен квантовый компьютер?

Все это звучит прекрасно, но как именно мы можем все это применить для решения реальной проблемы? В конце концов, если классические компьютеры становятся все быстрее и могут через Интернет связываться для параллельной работы, не сможем ли мы в итоге достичь такой производительности другими средствами? Ответ на эти вопросы был найден в 1994 году, когда Питер Шор, работая в Лабораториях Белла в Нью-Джерси, создал самый первый квантовый алгоритм – набор инструкций для выполнения задачи, справиться с которой под силу только квантовому компьютеру. Задача заключалась в невероятно эффективной факторизации больших чисел, что представляло собой одну из главных проблем компьютерной науки. Сразу стало очевидно, что квантовые компьютеры, если их создание вообще возможно, окажут огромное влияние на торговлю и банковское дело, поскольку безопасные в настоящее время методы шифрования с открытым ключом станут бесполезны и на сцену выйдет квантовая криптография.

Несколькими годами позже коллега Питера Шора математик Лов Гровер открыл другой квантовый алгоритм, который позволяет квантовому компьютеру осуществлять поиск по несортированной базе данных гораздо быстрее обычного поискового движка. Представьте простой пример: если бы я попросил вас найти конкретную карту в хорошо перетасованной колоде, вероятность вытащить ее с первого раза составила бы один к пятидесяти двум. Конечно, вам может повезти, но может и не повезти – и тогда, открывая одну карту за другой, вы найдете нужную лишь на последнем ходе. Попробовав произвести эту процедуру много раз, вы выясните, что в среднем вам понадобится двадцать шесть попыток (что равняется половине колоды). Используя алгоритм Гровера, квантовый компьютер может найти нужную карту в среднем за семь попыток. Математика такова: в базе данных из N элементов классическому компьютеру необходимо N/2 попыток, а квантовому компьютеру достаточно и квадратного корня из N.

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

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

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

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