О битах и кубитах

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

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

Квантовые вычисления - это, как можно догадаться, вычисления на квантовом компьютере. Квантовых компьютеров на свете пока нет. Более того, до сих пор неясно, когда появятся практически полезные конструкции и появятся ли вообще. Тем не менее, квантовые вычисления - предмет, чрезвычайно модный сейчас в математике и физике, как теоретической, так и экспериментальной, и занимается им довольно много людей. В чем же дело? Во-первых, в том, что область сама по себе очень интересная, необычная и удивительно живая (особенно на фоне того нагромождения абстракций, которое у многих ассоциируется с теорией алгоритмов). Судя по всему, именно интерес стимулировал первопроходцев - Ричарда Фейнмана, написавшего пионерскую работу, в которой ставился вопрос о вычислительных возможностях устройств на квантовых элементах, Дэвида Дойча, формализовавшего этот вопрос в рамках современной теории вычислений, и Питера Шора, придумавшего первый нетривиальный квантовый алгоритм. (Этот список нельзя, конечно, считать каноническим - в частности, о квантовых автоматах писал в конце 70-х годов Ю. И. Манин.)

И, конечно же, огромную роль сыграла сама тема работы Шора, вызвавшая лавинообразный рост числа публикаций о квантовых вычислениях. Шор построил квантовый (т. е. реализуемый на квантовом компьютере) алгоритм факторизации (разложения целых чисел на множители - используется в том числе для вскрытия зашифрованных сообщений). Все известные алгоритмы для обычного компьютера - экспоненциальные (время их работы растет как экспонента от количества знаков в записи факторизуемого числа). Факторизация 129-разрядного числа потребовала 500 MIPS-лет, или восемь месяцев непрерывной работы системы из 1600 рабочих станций, объединенных через Интернет. А при числе разрядов порядка 300 это время существенно превзойдет возраст Вселенной - даже если работать одновременно на всех существующих в мире машинах. Считается (хотя это и не доказано!), что быстрого алгоритма для этой задачи не существует. Более того, гарантией надежности большинства существующих шифров является именно сложность решения задачи факторизации, или одной из родственных ей теоретико-числовых задач, например - дискретного логарифма. И вдруг выясняется, что на квантовом компьютере эта задача имеет всего лишь кубическую сложность! Тем самым, при наличии квантового компьютера классические банковские, военные и другие шифры мгновенно теряют всякую ценность. Короче говоря, работа Шора показала, что вся эта изысканная академическая деятельность непосредственно касается такой первобытной стихии, как деньги. После этого и началась настоящая популярность…

Первое впечатление от беглого ознакомления с работами по КВ - такой математики в Computer Science еще не видывали. Аппарат квантовой теории поля в полном объеме - не угодно ли? Квантовые группы, алгебры Хопфа, когомологии - наугад беру термины из последней статьи А. Китаева… Любопытно, должны ли будут программисты квантовых компьютеров все это знать? Конечно, самые умопомрачительные конструкции будут, скорее всего, спрятаны в операторы какого-нибудь квантового Фортрана. Но как тогда быть с кубитом, который в принципе нельзя скопировать, не зная его содержимое?

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

Впрочем, и в специальной литературе встречаются интересные вещи, о которых можно рассказать обычным человеческим языком, не слишком обезобразив главную идею. В небольшой статье "Алиса у Боба украла бит" речь пойдет о любопытном результате, полученном совсем недавно, в сентябре этого года. Выясняется, что не только классическая, но и квантовая криптография (наука о шифровании сообщений) часто не способна противостоять квантовой криптоаналитике (науке о расшифровке). Некоторые важные криптографические протоколы, такие как "подбрасывание монеты по телефону", рушатся при переходе к квантовым вычислениям. Точнее, гарантией их надежности является отныне не сложность тех или иных алгоритмов, а сложность задачи создания квантового компьютера.

Тему продолжит статья, в которой мы вернемся к изложению основных принципов работы квантовых компьютеров и расскажем о предлагаемых вариантах их реализации. Строго говоря, можно выделить два типа квантовых компьютеров. И те, и другие основаны на квантовых явлениях, только разного порядка.

Представителями первого типа являются, например, компьютеры, основанные на квантовании магнитного потока на нарушениях сверхпроводимости - Джозефсоновских переходах. На эффекте Джозефсона уже сейчас делают линейные усилители, аналого-цифровые преобразователи, СКВИДы и корреляторы. Известен проект создания RISC-процессора на RSFQ-логике (Rapid Single Flux Quantum). Эта же элементная база используется в проекте создания петафлопного (1015 оп/с) компьютера (http://pavel.physics.sunysb.edu/RSFQ). Экспериментально достигнута тактовая частота 370 ГГц, которая в перспективе может быть доведена до 700 ГГц. Однако время расфазировки волновых функций в этих устройствах сопоставимо со временем переключения отдельных вентилей, и фактически на новых, квантовых принципах реализуется уже привычная нам элементная база - триггеры, регистры и другие логические элементы. Для сравнения - время расфазировки электрона в золотом проводнике при температуре 1o K - порядка 10-13 с. Та же самая величина для ядерного спина, пока теоретически, может измеряться годами.

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

Пока квантовым компьютерам по плечу только наиболее простые задачи - например, они уже умеют складывать 1 и 1, получая в результате, угадайте, - два. На следующий год запланировано взятие другого важного рубежа - факторизации числа 15, его предстоит разложить на простые множители - 3 и 5. А там, глядишь, дойдет дело и до более серьезных задач.

Опытные образцы сейчас содержат менее 10 квантовых битов. По мнению Нейла Гершенфельда (Neil Gershenfeld), участвовавшего в создании одной из первых действующих моделей квантового компьютера, необходимо объединить не менее 50-100 кубитов, чтобы решать полезные с практической точки зрения задачи. Интересно, что добавление каждого следующего кубита в квантовый компьютер на эффекте объемного спинового резонанса требует увеличения чувствительности аппаратуры в два раза. Десять дополнительных кубитов, таким образом, потребуют увеличения чувствительности в 1000 раз, или на 60 ДБ. Двадцать - в миллион раз, или 120 ДБ…

Тем не менее, исследователи не теряют надежды. Разработками сейчас занимаются в ведущих университетах мира, не отстают и крупные компьютерные и телекоммуникационные компании, среди которых - IBM и AT&T, Hughes и Hitachi. Квантовыми компьютерами заинтересовалась и армия. На грант министерства обороны США в пять миллионов долларов в прошлом году был образован институт, специализирующийся на квантовых компьютерах, а желающие могут и сейчас поучаствовать в конкурсе, объявленном в сентябре армией США (http://www.aro.ncren.net/research/quantum.htm).

Думаем, читателям будет любопытна и некоторая информация об основоположниках, которую можно получить в Сети. Например, поучительно ознакомиться с оксфордской Web-страницей Дэвида Дойча (http://eve.physics.ox.ac.uk/Personal/deutsch/ David.html). На ней, кроме стандартных ссылок на статьи и на введение в квантовые вычисления, есть три интересных линка. Первый указывает на страницу, посвященную одному из самых знаменитых философов 20 века Карлу Попперу (Carl Popper), по второму можно попасть на сайт Ричарда Докинза (Richard Dawkins), живого классика теории эволюции, автора оригинальнейшей концепции эгоистичного гена. А на этих сайтах есть другие интересные ссылки… Вот он, культурный слой Интернета!

Между прочим, один из наиболее ярких ученых, активно работающих в области квантовых вычислений - наш соотечественник, молодой математик Алексей Китаев. Причем работает он, вопреки мифу о том, что "все уехали", в самой что ни на есть Москве…

Отзывы и замечания по теме номера можно направлять по адресу gbash@cterra.com.