Квантовый компьютер работает со скоростью света, но выдает приблизительный ответ
Квантовый компьютер — это порождение квантового мира, живущего по законам квантовой механики, которые на первый взгляд могут показаться очень странными. Но нам ничего не остается, кроме как поверить в справедливость этих законов, поскольку именно на их основе построено и работает множество окружающих нас сегодня устройств — например, лазеры и томографы.
Одно из основных положений, которое иначе как магическим не назовешь, — принцип суперпозиции. Заключается он в следующем: если субатомная частица может находиться в нескольких состояниях, то она находится во всех этих состояниях одновременно. Принцип суперпозиции легко продемонстрировать на примере всем известного электрона. Электрон имеет некоторую внутреннюю характеристику, называемую спином. Электрон может находиться в двух состояниях — «спин вверх» (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) запустило проект построения квантового компьютера, по масштабам сопоставимый с проектом создания атомной бомбы. Это вполне вероятно — ведь задачи криптографии представляют интерес в первую очередь для спецслужб, накопивших огромное количество информации, расшифровать которую существующими способами вряд ли удастся в обозримое время.
Препятствия
Итак, идея обоснована, алгоритмы придуманы, и на пути создания действующего квантового компьютера остались только технические проблемы: выбрать метод реализации и "