частиц; поведение всех этих электронов и фотонов на микроуровне заметно отличается от привычного для нашего здравого смысла поведения макроскопических тел... Кто-то слышал, быть может, и о том, что на состояние элементарных частиц воздействует сам факт наблюдения за ними. Впрочем, начала квантовой физики мы здесь излагать не станем; незачем лишать пытливого читателя радости самостоятельного погружения в этот удивительный мир. Расскажем лишь о самых базовых понятиях, которые помогут сориентироваться в вопросе принципиального отличия квантовых вычислений от классических.
Прежде всего несколько слов о бинарной, базовой для современной полупроводниковой электроники, логике. В булевом макромире она проста: есть понятия «ложь», 0, и «истина», 1. Есть операции логического сложения и умножения. Собственно, все; на этом простеньком базисе выстраивается огромное здание современных вычислительных технологий. Формально-логическим закономерностям подчиняется ощутимый и зримый нами макромир. А вот над элементарными частицами, особенно если изучать их поведение на расстояниях, сравнимых с их собственными размерами, властны иные законы – вероятностные.
Электрон, вращаясь вокруг атомного ядра, не находится в определенной точке пространства в каждый момент времени, а представляет собой так называемую суперпозицию квантовых состояний: в каждой точке орбиты вероятность его присутствия строго определена, но никогда не составляет ровно 100 %. То же самое можно сказать о всяком квантовом состоянии: направлении спина (вектора собственного момента импульса) частицы, направлении тока в сверхпроводящем микрокольце, возбужденном и основном состояниях атома и т. п. Любая квантовая система никогда не находится в некоем фиксированном с точки зрения макромира положении – она «дышит» в границах между своими крайними состояниями, которые можно обозначить как 0 и 1. Все множество состояний квантовой системы между ее граничными положениями принято называть квантовым битом, или кубитом (quantum bit).
Отвлечемся пока от того, как именно можно воплотить этот самый кубит «в металле». Если такое принципиально возможно, то нет никаких препятствий и к тому, чтобы объединять кубиты, как и их макроаналоги, в регистры – последовательные цепочки. Именно регистр, наряду с логическим переключателем, – базовый элемент любой электронной схемы. Протяженность, или разрядность, регистра имеет значение: если он состоит из n ячеек, а в каждой ячейке может содержаться значение 0 или 1, то число возможных уникальных комбинаций внутри регистра – 2n. Для «классического», бинарного, регистра на этом описание его свойств исчерпывается. Но – не для квантового!
Если взять классический регистр длиной в n бит, то, очевидно, ровно n его элементов и будут доступны для изменения, т. е. записи информации. Если же подействовать на квантовый регистр (переменой магнитного поля, лазерным пучком – не имеет значения; физика процесса пока не важна), то воздействие это будет распространяться на все его состояния суперпозиции, т. е. в итоге можно будет произвести 2n изменений и получить информационный контейнер именно такой поражающей воображение емкости. Но почему? Да потому, что между соседними кубитами возможны (и осуществляются) так называемые нелокальные корреляции.
Вот что это такое: даже если мы записываем в кубит значение «единица», он, вследствие квантовомеханических эффектов, находится в этом состоянии лишь с некоторой, наперед известной вероятностью. То же верно и для соседнего кубита. Значит, система из двух таких элементов может одновременно пребывать в состояниях 0–0, 0–1, 1–0 и 1–1, причем для каждого из этих состояний четко просчитывается вероятность его реализации. В общем случае для регистра из n кубитов суммарное число комбинаций как раз 2n. Для создания квантовой вычислительной системы, помимо кубитов как таковых, требуются вентили двух типов: осуществляющие, во-первых, переход между различными базовыми состояниями одного кубита (поворот спина, условно говоря) по команде извне; во-вторых, тот же переход, но инициируемый для данного кубита конкретным состоянием другого.
Звучать может странновато и непривычно, но, поверьте, это работает. Получается, что максимальный выигрыш при использовании квантового регистра в сравнении с классическим составляет 2n/n. Отсюда следует, кстати, что по-настоящему заметным такой выигрыш может стать, если использовать длинные квантовые регистры (с числом кубитов 20 и больше). В идеале – сотни и тысячи.
Стоп-стоп-стоп... Сотни? Тысячи? А как быть с привычными нам объемами памяти – мега-, гига– и прочими терабайтами? Что, пара тысяч кубитов сможет удовлетворить системным требованиям MS Windows Vista Ultimate?
Сможет. Гигабайт – это двойка в степени всего лишь тридцать, так что трех десятков кубитовых ячеек хватит, чтобы хранить такой объем информации. И дело не только в объеме: быстродействие квантового компьютера теоретически демонстрирует взрывной, экспоненциальный рост в сравнении с компьютерами обычными. Если над каждой из n ячеек традиционной памяти один процессор способен в единицу времени совершить только одну операцию, то любое воздействие на систему кубитов означает одновременное изменение всех 2n ее базовых состояний. Пока предел для квантовой системы не достигнут, даже теоретически. Однако уже разработанные квантовые алгоритмы демонстрируют заметное ускорение вычислений: так, одна из наиболее ресурсоемких задач вычислительной математики (разложение натурального числа на простые множители) решается на кубитовом компьютере благодаря алгоритму Шора за время, пропорциональное логарифму этого числа. Настолько стремительно обычные компьютеры не работают, там зависимость в лучшем случае линейная.
И пусть не всякая вычислительная задача допускает «квантовое ускорение», существует очень важный круг проблем, которые квантовый компьютер поможет принципиально низвести на уровень «третий класс, вторая четверть». Это... внимание, криптографы, приготовьте валокордин, – будем надеяться, вам он достанется пока без рецепта, – задачи взлома паролей методом «грубой силы». Как известно, такой метод заведомо приводит к гарантированному результату, хотя и является одновременно самым трудоемким. Если известен алфавит, применявшийся для составления пароля, нужно просто перепробовать все возможные комбинации его символов: пароль гарантированно окажется среди них. Метод «грубой силы» на современных ПК прекрасно срабатывает для традиционных (к сожалению, коротких) паролей длиной 8 символов и менее: такие «волшебные слова» взламываются за считанные минуты на средненьком Pentium III.
История вопроса
Фон Нейман рассуждал о возможности использовать в вычислительных целях эффекты квантовой механики еще в 1950-х гг., когда и классических-то, в современном понимании, компьютеров не существовало. К этой проблематике вернулся в следующем десятилетии американец Ф. Ландауэр, указавший на то, что машинное вычисление – не математическая абстракция, а некий реальный физический процесс, и, значит, отталкиваясь от чисто физических знаний о строении материи, можно предложить новые эффективные методики организации вычислений. Но только в 1980-е гг. советский (Ю. Манин) и американский (П. Бенев) ученые вплотную подошли к разработке теории квантовых вычислений. Дополнительное внимание к этому направлению привлек знаменитый физик Р. Фейнман.
В 1994 г. П. Шор, сотрудник Lucent Technologies, разработал квантовый алгоритм факторизации (разложения на простые множители) больших чисел. Как раз этот алгоритм лежит в основе современной компьютерной криптографии. Шор уделил немало внимания проработке схем кодирования квантовых
