Квантовые вычисления
Если облучить атом светом, фотоны которого обладают подходящей энергией, можно заставить атом изменить состояние из |0> в |1> и обратно. Так мы инвертируем бит атома. Другими словами, мы выполняем логическую операцию «не». В статье «Потенциально реализуемый квантовый компьютер» (A Potentially Realizable Quantum Computer), опубликованной в 1993 г. в журнале Science, я показал, что немного более сложный набор последовательностей лазерных импульсов, чем используемый для операции «не», позволяет атомам выполнять логические операции «и», «или» и «копировать» – точно так же, как в обычных цифровых вычислениях. Каждый атом хранит один бит, и набор атомов может вычислять все, что может вычислять обычный PC или Mac.
Но атомы могут сделать намного больше, чем обычный PC или Mac. Атомы могут хранить нечто большее, чем биты; они могут хранить кубиты. В отличие от классических битов, кубиты могут находиться в квантовых суперпозициях |0> и |1>, то есть они могут быть в состоянии 0 и 1 в одно и то же время. Можно ли каким-то образом использовать эти квантовые суперпозиции для вычислений, которые не могут делать классические компьютеры? Этот вопрос впервые поднял Дэвид Дойч в середине 1980-х гг., но ответ на него был найден только в начале 1990-х. И этот ответ – да.
Чтобы увидеть, почему квантовые компьютеры и квантовые биты могут сделать больше, чем классические компьютеры и классические биты, давайте вспомним, что делают биты в компьютере. Некоторые из них, например биты на жестком диске компьютера или в его памяти, просто хранят информацию. Например, биты в памяти моего компьютера получают и хранят этот текст, по мере того как я его печатаю. Другие биты, например биты компьютерных программ, являются инструкциями или командами. Они велят компьютеру делать то или другое. Функционирует ли бит как бит памяти или как бит команды, зависит от контекста, в котором он используется.
Рассмотрим бит, который компьютер интерпретирует как команду: 0 означает «Делай это!», а 1 означает «Делай то!» «Это» может быть, скажем, «прибавь 2 к 2», а «то» может быть «прибавь 3 к 1». Или «это» может означать «отправь электронное письмо», а «то» – «открой веб-браузер».
В отличие от классического бита, квантовый бит может содержать 0 и 1 в одно и то же время. Что делает квантовый компьютер, когда он пытается интерпретировать такой кубит как команду? Часть суперпозиции, обозначаемая нулем, говорит квантовому компьютеру: «Делай это», а часть суперпозиции, соответствующая единице, говорит: «Делай то». Как же квантовый компьютер решает, что ему делать? А никак! Он делает «то» и «это» одновременно! Как квантовый бит может хранить два значения сразу, так и квантовый компьютер может выполнять два вычисления одновременно.
Дэвид Дойч назвал эту парадоксальную способность квантового компьютера делать две вещи сразу «квантовым параллелизмом». Квантовый параллелизм очень отличается от обычных классических параллельных вычислений. Классический параллельный компьютер состоит из нескольких процессоров, соединенных вместе. При классическом параллельном вычислении один процессор выполняет одну задачу, а другие процессоры выполняют другие задачи. В случае квантового параллелизма один квантовый процессор выполняет несколько задач сразу.
Эта способность делать две вещи сразу присуща именно квантовой механике. В двухщелевом эксперименте фотон может пройти через обе щели сразу; кубит может хранить 0 и 1 в одно и то же время; квантовый компьютер может выполнять две разных задачи одновременно. Способность делать две вещи сразу является результатом волновой природы квантовой механики. Каждое возможное состояние квантовой системы соответствует волне, а волны могут накладываться друг на друга.
Мы все знакомы с ситуациями, где наложение волн приводит к качественно новым и более богатым явлениям. Рассмотрим звуковые волны. Волна, колеблющаяся вверх и вниз на определенной частоте, соответствует чистому тону. Звуковая волна, колеблющаяся вверх и вниз 440 раз в секунду, соответствует звуку ноты «ля» первой октавы. Звуковая волна, колеблющаяся вверх и вниз 330 раз в секунду, дает звук ноты «ми» первой октавы. Суперпозиция этих двух волн соответствует аккорду, который обладает качественно иным, более богатым звуком, чем звук любого чистого тона, взятого отдельно. Богатство звука возникает благодаря интерференции, наложению этих двух чистых тонов.
Классическое вычисление похоже на сольную партию – отдельные строки чистых тонов, следующие друг за другом. Квантовое вычисление похоже на симфонию, состоящую из множества строк тонов, интерферирующих друг с другом. Именно это явление интерференции придает квантовому вычислению его особые качества и дополнительную мощь.
Квантовые вычисления не ограничиваются всего двумя «партиями». Как и симфония, квантовое вычисление становится богаче и сильнее, создавая сложные последовательности аккордов. Например, предположим, что на вход компьютера подается «кутрит» с тремя возможными состояниями: 0, 1 и 2. Состояние 0 инструктирует квантовый компьютер «делать это», состояние 1 инструктирует его «делать то», а состояние 2 инструктирует его «делать что-то еще». Если «это» означает «прибавить 2 к 2», а «то» означает «прибавить 3 к 1», то «что-то другое» может означать «прибавить 4 к 0». Когда квантовому компьютеру на вход подают суперпозицию всех трех инструкций, он начинает делать «это», «то» и «что-то другое» сразу. В нашем примере компьютер одновременно исследует все возможные способы получить 4 как сумму неотрицательных целых чисел. Такое квантовое вычисление похоже на трио, где три волны интерферируют, накладываются друг на друга, а три вычисляющих «голоса» сотрудничают над разложением числа 4 на слагаемые и делают это быстрее, чем мог бы сделать один вычисляющий «голос».
Количество вещей, которые одновременно может делать квантовый компьютер – число голосов в симфонии квантового вычисления – быстро растет с увеличением числа входных битов. Даже небольшое количество кубитов может создать чрезвычайно богатую фактуру интерферирующих волн в ходе вычисления. Квантовый компьютер, получивший на входе 10 кубитов, может делать 1024 (210) вещей сразу. Квантовый компьютер, получивший 20 кубитов, может сделать 1 048 576 (220) вещей сразу. При 300 кубитах на входе он может одновременно сделать больше вещей, чем элементарных частиц во всей Вселенной. Квантовый параллелизм позволяет даже относительно маленькому квантовому компьютеру, содержащему всего несколько сотен кубитов, одновременно исследовать огромное количество возможностей.
И снова проблема измерения
Но что происходит, когда мы берем квантовый компьютер, делающий несколько вещей сразу, и спрашиваем его, что он делает? Возможно ли провести измерения, чтобы определить, делает ли он «это», «то» или «что-то другое»? Как и с любой квантовой системой, когда мы проводим измерения в суперпозиции нескольких возможных состояний, результат измерения дает случайным образом одну из этих возможностей. Так, если квантовый компьютер исследует все способы получить цифру 4 как сумму положительных целых чисел, то когда мы начнем его опрашивать, он скажет, например: «О, я прибавляю 3 к 1», или: «Я прибавляю 2 к 2».
Следуя метафоре квантового вычисления как симфонии: если мы измеряем квантовый компьютер, в то время как он вычисляет, мы не слышим всего оркестра; мы слышим только один голос, выбранный случайным образом.
Вспомним двухщелевой эксперимент. В этой модели электрон делает две вещи сразу: он проходит через обе щели одновременно. Когда мы проводим измерения, чтобы выяснить, через какую щель проходит электрон, он обнаружится в одной или во второй щели, случайным образом. Точно так же, если мы возьмем квантовый компьютер, делающий две вещи сразу, и измерим его, чтобы выяснить, что он делает, то окажется, что он делает одну или другую из этих вещей, случайным образом. Если мы хотим увидеть интерференционную картину в эксперименте с двойной щелью, нам нужно подождать, пока электрон достигнет экрана, чтобы две волны – одна от одной щели, вторая от другой – смогли проинтерферировать друг с другом. Картина интерференции возникает из «дуэта» этих двух волн. В квантовом вычислении, если мы хотим получить от него максимальную пользу, не следует наблюдать за вычислением, когда оно происходит. Чтобы получить полный симфонический эффект квантового вычисления, нужно позволить всем волнам в этом вычислении интерферировать друг с другом. Нужно позволить «голосам» вычисления сливаться и перекликаться так, как они хотят.