Женская логика: Квантовый компьютер

Квантовый компьютер работает со скоростью света, но выдает приблизительный ответ
РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

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

Одно из основных положений, которое иначе как магическим не назовешь, — принцип суперпозиции. Заключается он в следующем: если субатомная частица может находиться в нескольких состояниях, то она находится во всех этих состояниях одновременно. Принцип суперпозиции легко продемонстрировать на примере всем известного электрона. Электрон имеет некоторую внутреннюю характеристику, называемую спином. Электрон может находиться в двух состояниях — «спин вверх» (Spin Up) и «спин вниз» (Spin Down). В соответствии с принципом суперпозиции он находится в обоих состояниях сразу, каждое из которых присутствует со своей вероятностью (эти вероятности не обязательно равны, но сумма их — всегда 1).

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

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

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

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

Регистры

Обычные компьютеры хранят информацию в ячейках, каждая из которых либо имеет электрический заряд, либо нет. Каждая такая ячейка соответствует минимальной единице информации — биту. Бит может быть равен нулю или единице. Хороший пример бита — это рубильник, который включает электролампу. Его значение либо 0 (лампа выключена), либо 1 (лампа включена). В квантовом компьютере аналогом бита является кубит (квантовый бит), который благодаря принципу суперпозиции находится в двух состояниях одновременно. Как в классических, так и в квантовых компьютерах биты или кубиты объединены в последовательности — регистры. Обычный двухбитовый регистр может хранить 4 значения — 00, 01, 10 или 11, но только одно из них в данный конкретный момент времени. А вот в двухкубитовом регистре одновременно находятся все 4 возможных значения. (Вообще в регистре размером N кубитов одновременно «живут» все возможные 2n значений.)

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

И как же оно работает

Начальные условия задаются установкой кубитов в нужные состояния. Как и в классическом компьютере, здесь за каждой командой стоит последовательность логических операций, которые реализуются через воздействие на кубиты (например, «переворот» спина радиочастотными импульсами соответствует операции отрицания в обычном компьютере). А считывание результатов — это «считывание» состояния кубитов.

Почему он работает так быстро

Допустим, вы хотите провести какое-то действие над каждым из 4 возможных чисел в регистре из 2 битов на обычном компьютере. Решение этой задачи потребует 4 шага, выполняемых последовательно, поскольку в 2 обычных бита в каждый момент времени записано только 1 из 4 возможных чисел. Мы должны их последовательно перебрать и над каждым выполнить нужную операцию. В квантовом компьютере с регистром из 2 кубитов задача будет решена за один шаг, ведь действие производится сразу над всеми числами, которые одновременно хранятся в регистре. Это называется «квантовый параллелизм». Именно квантовый параллелизм позволяет сделать некоторые вычисления намного более эффективными по сравнению с вычислениями на классическом компьютере.

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ
РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

Квантовые алгоритмы

Дальнейшее движение по пути создания квантового компьютера показало, что, несмотря на плодотворность идеи кубитов, праздновать победу еще рано. Тот самый квантовый параллелизм, который позволяет достичь фантастической производительности, порождает и новые проблемы: интересующий нас результат действия над квантовым регистром в действительности оказывается «спрятан» внутри суперпозиции. Если просто «прочитать» ответ, он окажется «первым попавшимся» из всех возможных (в системе с N состояниями правильный ответ будет выведен с вероятностью 1/N). Более того, в процессе «считывания» суперпозиция разрушается и система становится непригодной для дальнейших вычислений. И только заново настроив систему, можно снова попытаться получить правильный ответ. Весь выигрыш в быстродействии, который дает квантовый параллелизм, теряется!

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

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

Зачем нужна факторизация

Задача факторизации, кажущаяся на первый взгляд чисто теоретической, имеет важное практическое приложение. Дело в том, что один из самых распространенных сегодня методов шифрования с открытым ключом — RSA — построен на очень простом утверждении: если у вас есть два простых числа (M и N), то вычислить их произведение (К) проблемы не представляет. Но вот, зная K, найти M и N — задача, на сегодняшний день разрешимая только путем прямого перебора всех возможных чисел. А если M и N — очень большие простые числа (более 100 цифр), то мощность (а скорее — немощность) сегодняшних компьютеров делает ее неразрешимой. Например, чтобы с помощью обычного компьютера разложить на простые множители 250-значное число, потребуются многие тысячи лет. То есть алгоритм Шора, по сути, есть не что иное, как алгоритм взлома шифров. Таким образом, определилась идеальная область для применения квантового компьютера — криптография.

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ
РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

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

Препятствия

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

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

На практике

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

На предыдущей странице изображена искусственно созданная молекула. Она состоит из 5 атомов фтора и 2 атомов углерода и работает как семикубитный регистр. Атомы могут находиться в состояниях «спин вверх» и «спин вниз». Управление спинами осуществляется при помощи радиочастотных импульсов. В декабре 2001 года IBM при помощи своей машины удалось разложить на множители число 15. Ответ «3 и 5» был «считан» прибором для измерения ядерного магнитного резонанса (ЯМР).

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

«Не страшно, что ответ может показаться тривиальным. До сих пор никому не удавалось выполнить настолько сложное квантовое вычисление: во время эксперимента поддерживался беспрецедентный уровень управления 7 спинами», — заявил после обнародования результатов Набиль Амер, сотрудник исследовательской лаборатории. А руководитель проекта, профессор Массачусетского технологического института Исаак Чуанг считает: «Следующая наша задача — запустить квантовый компьютер в производство».

Что дальше?

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

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