Опубликовано в журнале Новый Мир, номер 7, 2011
ВЛАДИМИР ГУБАЙЛОВСКИЙ: НАУКА БУДУЩЕГО
Классические и квантовые компьютеры
Всякое вычисление есть измерение. Или более подробно: всякое вычисление сводится к измерению некоторого параметра определенного физического явления, причем в разных вычислителях наблюдаемые явления и параметры могут быть принципиально разные. Но все они используют некоторые известные физические законы. Информация — это реально существующий, физический объект, а не что-то идеальное.
Для начала я рассмотрю совсем простой пример. Несмотря на то что пример простой, в нем присутствуют все принципиально важные моменты любого вычисления.
Мальчик Боб умеет считать и знает цифры, но не умеет складывать. Но у него есть счетные палочки, каждая из которых весит 1 г, и есть весы, на которых можно производить взвешивания с точностью до 1 г. Как Боб может сложить два числа, например 3 и 5? Он отсчитает три палочки и положит их на весы. Потом отсчитает еще пять палочек и тоже положит на весы. А потом посмотрит на показатель весов. Там будет цифра 8. Это и есть результат сложения.
Взвешивание — это физический процесс, который в данном случае используется для счета. Значение веса и есть тот параметр физического явления, который позволяет Бобу не пересчитывать все палочки, а сразу получить ответ. Когда Боб отсчитывал палочки, он готовил исходные данные. Когда он положил их на весы, он запустил процесс счета. А когда посмотрел на показатель весов — считал результат. Как работают весы, он не имеет никакого представления, что такое вес — он тоже понятия не имеет. Но это не помешало ему получить результат сложения.
В данном случае вычисление есть измерение веса палочек.
Компьютер работает точно так же. Известно, что любое вычисление можно свести к вычислению функций алгебры логики, то есть таких функций, которые оперируют переменными, имеющими только два значения — 0 и 1. Функция также может принимать только два значения — 0 и 1. То, что к таким простым функциям сводится любой вычислительный процесс, было доказано великими логиками в 1930-е годы. Это независимо доказали Алонзо Чёрч, Стивен Клини и Алан Тьюринг. Тьюринг выразил свой результат в виде гипотетической «машины» — универсальной машины Тьюринга. Она представляет собой бесконечную бумажную ленту, на которую с помощью маркера наносятся нули и единицы. Машина может прочитать значение, написанное в клеточке, на которой стоит маркер, изменить значение, сдвинуть маркер по ленте влево или вправо. Это практически все.
Но еще в XIX веке американский логик и философ Чарльз Пирс обратил внимание на то, что любая функция алгебры логики может быть реализована с помощью соединения нескольких элементарных электрических схем. Чтобы вычислить любую функцию, нам нужно выставить переключатели в два состояния — «включено» или «выключено» (это точный аналог нулей и единиц) и пустить ток. Допустим, в нашей сети есть электрическая лампочка, тогда если она загорелась — значение функции при введенных данных (состоянии переключателей) равно единице, если лампочка не загорелась — нулю.
Здесь мы видим полную аналогию со взвешиванием палочек. Пока мы устанавливали переключатели, мы как бы пересчитывали палочки, когда включили ток — запустили процесс счета (или взвешивания), когда посмотрели на лампочку — считали результат.
Идеи Пирса независимо от него использовал Клод Шеннон при создании первых компьютеров в 1940-е годы. Фактически Шеннон показал, как можно с помощью электрических схем реализовать машину Тьюринга. Прямое следствие открытий Тьюринга и Шеннона — возникновение во второй половине XX века того постиндустриального, цифрового мира, в котором мы сегодня живем. Физика полупроводников сделала компьютеры сначала реализуемыми, а потом и настолько миниатюрными, что их можно уместить в мобильный телефон. Так что, когда вы будете звонить по своему мобильнику, помяните благодарным словом этих великих людей.
Но в начале XXI века выяснилось, что использование электрических схем для создания вычислительных устройств имеет свои границы, и эти границы на сегодня практически достигнуты: перед человечеством встали задачи, которые можно решить с помощью существующих компьютеров, только теоретически. В реальности их решение потребует времени, сравнимого или даже превосходящего время существования Вселенной. И некоторые такие задачи имеют совсем простую формулировку, например, разложить большое число на простые множители (задача факторизации). На реальной невозможности решения этой задачи построено большинство криптографических систем, работающих методом шифрования с открытым ключом. Здесь не место подробно разбирать принципы работы таких алгоритмов шифрования, стоит отметить только, что если бы сегодня кому-то удалось найти способ быстро разлагать большие числа на простые сомножители, — для него стали бы доступны все транзакции во всех банках мира.
Другая задача, с которой не справляются (и по-видимому, никогда не смогут справиться) сегодняшние компьютеры, — это моделирование квантовых систем, в том числе сложных молекул, в частности самых интересных для нас — ДНК.
Профессор МГУ Юрий Ожигов, работающий в лаборатории квантовых компьютеров Физико-технического института РАН (ФТИАН), сказал: «Даже для численного моделирования единственного атома гелия (а это всего второй по сложности атом — после атома водорода. — В. Г.), причем без учета движения ядра, требуется миллион миллионов узлов расчетной сетки, а это уже серьезная проблема даже для суперкомпьютера. Ну а о точном квантовом расчете сложнейших молекул белков и ДНК сегодня и думать невозможно»[6].
Если бы в первой половине XX века человечество не придумало, как использовать электрические схемы для вычислений, мир был бы другим — никакой механический вычислитель, те же весы, которые использовал для сложения Боб, невозможно встроить в мобильный телефон. Значит, и сегодня нам нужно найти другой физический принцип, чтобы его можно было использовать для «расчета сложнейших молекул белков и ДНК».
В 1965 году сотрудник компании «Intel» Гордон Мур сформулировал эмпирический закон, получивший его имя. Он заметил, что каждые два года плотность размещения транзисторов на одном квадратном дюйме кремниевой подложки увеличивается в два раза. (У этого закона было много уточнений, и это — только одна из возможных формулировок.) Этот закон утверждает, что вычислительные мощности растут экспоненциально, то есть фактически со скоростью взрыва. Когда Мур сформулировал свой закон, он, конечно, не предполагал, что такой рост сохранится долго. Между тем закон Мура до сих пор работает.
Но в начале XXI века стали заметны серьезные проблемы. И многие обычные пользователи персоналок, те, кто начинал еще в 90-е, их уже заметили. Столь частые в те годы победные реляции о достижении новой тактовой частоты уже давно не слышны.
Процессор Pentium 4, разработанный компанией «Intel» еще в 2002 году, имел тактовую частоту 3 ГГц. И с тех пор тактовая частота не выросла. Хотя есть процессоры с частотой 3,8 ГГц, но, как правило, используются процессоры с частотой 3 ГГц. А от частоты 4 ГГц «Intel» отказалась[7]. Для дальнейшего роста есть несколько принципиальных (непреодолимых) барьеров: атомная структура вещества, ограничение скорости света, туннельный эффект и проблема отвода тепла (перегрев процессора).
Процессор, каким бы маленьким он ни был, не может быть меньше одного атома. Сегодня самая передовая технология производства процессоров — 32-нанометровая — уже отличается от размера атома всего на три порядка — 1000 размеров атома. «Intel» заявила, что к 2017 году компания перейдет на 10-нанометровую технологию, но это уже точный предел для существующих решений.
Сигнал между транзисторами не может распространяться со скоростью, превышающей скорость света, а значит, есть предел для роста скорости обмена данными.
При размерах порядка нанометра заряженные частицы начинают «просачиваться» через закрытые переключатели, возникает «туннельный ток», и уже нельзя уверенно сказать, закрыт переключатель или открыт. Это чисто квантовый эффект, не имеющий аналогов в классическом мире, и связан он с тем, что заряженная частица — не частица вовсе, а волна информации, и при квантовых размерах локализовать ее положение с любой точностью нельзя.
Существует и еще одна принципиальная трудность — это отвод тепла. Работающий процессор нужно охлаждать, а это тоже возможно только до определенного предела. Еще в 1961 году сотрудник «IBM» Рольф Ландауэр сформулировал принцип, согласно которому в любой вычислительной системе, независимо от ее физической реализации, при стирании 1 бита информации выделяется теплота. Это происходит просто потому, что при стирании информации она теряется безвозвратно, а значит, увеличивается энтропия системы и неизбежно выделяется тепло. В начале 1960-х на этот принцип не обратили внимания — количество тепла показалось совершенно ничтожным; сегодня эта проблема стала одной из самых трудных.
Крупнейшие производители процессоров, и в первую очередь «Intel», отказались от наращивания тактовой частоты и перешли к реализации многоядерных решений, то есть фактически стали встраивать в компьютер не один процессор, а два или четыре. Но, во-первых, не все алгоритмы можно эффективно распараллелить, чтобы на двух процессорах они работали быстрее, чем на одном, а во-вторых, взаимодействие процессоров — это большие накладные расходы. Попросту говоря, два процессора работают не в два раза быстрее, чем один, а, скажем, в 1,8 раза. Причем чем процессоров больше, тем прирост будет менее значительным. То есть здесь тоже ясно виден предел. Но пока еще есть куда расти.
Зачем нам нужны все более быстрые и мощные компьютеры? Нельзя ли ограничиться теми, что есть? Ответ однозначный: даже в среднесрочной перспективе уже нельзя. Это связано с лавинообразным ростом количества цифровой информации и количества пользователей и производителей этой информации. Буквально шесть лет назад, в феврале 2005 года, когда появился Youtube, никто не подозревал, что количество видеоинформации будет расти с такой поразительной скоростью. И это только небольшая часть цифровой информации, которая создается и передается по глобальной сети. Хотя количество людей на Земле сравнительно невелико, количество устройств и сервисов, использующих цифровую информацию, ничем не ограничено. Если сегодня перестать наращивать цифровые мощности, встанет Сеть. Последствия могут быть катастрофическими. Но это только одна из проблем. Мы ведь хотим продолжать теми же темпами (а хотелось бы и побыстрее) познавать и конструировать природу, в частности, попытаться конструировать работу мозга, а без взрывного роста вычислительной мощности это невозможно.
В 1982 году Ричард Фейнман опубликовал статью[8], в которой предложил использовать принципиально новый физический принцип для вычислительных систем. Эту статью считают началом квантовых компьютеров.
Ричард Фейнман, анализируя проблему моделирования квантовых явлений, пришел к выводу, что моделирование таких явлений на реальных компьютерах при ограничении времени практически невозможно и не будет возможно в обозримой перспективе. Но вместо того чтобы считать трудность обработки квантовых явлений препятствием, Фейнман счел ее новой возможностью. Действительно, чтобы узнать исход эксперимента, необходимо выполнить невообразимо много вычислений. Но если мы поставим эксперимент, то сам факт его проведения и измерения его результатов будет равносилен выполнению сложного вычисления. То есть вместо того, чтобы считать, мы можем поставить эксперимент и «снять» результат, тогда мы как бы заглянем в ответ. И сам эксперимент станет своего рода «специализированным процессором», который возьмет на себя самую трудную часть вычислений и оставит классическому процессору фактически только обработку полученных результатов.
Если мы вернемся к весам и мальчику Бобу, то увидим полную аналогию. Классический компьютер не умеет моделировать квантовую систему. Но он может подготовить входные данные — «посчитать палочки». Затем мы запустим квантовый эксперимент и с помощью классического устройства зарегистрируем результат — «посмотрим на показатель весов».
Идея Фейнмана была только наброском. Первые решения, которые позволили приблизиться к реализации квантового компьютера, были получены Дэвидом Дойчем во второй половине 80-х. Но и они имели чисто теоретический характер.
Настоящий интерес квантовые компьютеры вызвали, когда было показано, что с их помощью (если бы они существовали) можно было бы очень быстро решить задачу факторизации, то есть взломать шифры с открытым ключом.
Трудности, которые стоят перед учеными, очень велики. Профессор Ожигов, один из ведущих специалистов по квантовым вычислениям, считает, что трудности эти сравнимы с решением проблем, связанных с межпланетными перелетами.
Не имея возможности подробно анализировать принципы квантовых вычислений и их физические реализации, я тем не менее попробую хотя бы контурно обрисовать те проблемы, которые стоят перед учеными, работающими в этой области.
Источник этих проблем заключен в тех же квантовых свойствах материи, которые и обеспечивают огромный прирост быстродействия квантового компьютера по сравнению с классическим.
Классический компьютер работает последовательно: по двум числам (битам), полученным на выходе, он однозначно определяет их сумму, передает ее пользователю и переходит к сложению следующей пары чисел. Чтобы сложить две пары чисел, потребуется два такта процессора. Так работает любое классическое вычислительное устройство — очевидна полная аналогия с весами, с помощью которых складывал числа мальчик Боб.
Квантовый компьютер работает не с битами, а с так называемыми кубитами; это могут быть частицы или системы, пребывающие в двух квантовых состояниях, — одно соответствует единице, другое — нулю. Физически это может быть значение спина, или направление поляризации, или какое-то другое квантовое наблюдаемое.
Если классический процессор в каждый момент времени находится ровно в одном состоянии (т. е. все биты, с которыми он работает, имеют значение либо нуль, либо единица), то квантовый процессор находится в так называемой квантовой суперпозиции, то есть во всех возможных состояниях одновременно: каждый кубит с некоторой вероятностью равен нулю или единице. Весь набор кубитов называется квантовым регистром. Главный выигрыш, который мы получаем при использовании квантового компьютера, — это квантовый параллелизм.
«Данные в процессе вычислений представляют собой квантовую информацию, которая по окончании процесса преобразуется в классическую путем измерения конечного состояния квантового регистра. Выигрыш в квантовых алгоритмах достигается за счет того, что при применении одной квантовой операции большое число коэффициентов суперпозиции квантовых состояний, которые в виртуальной форме содержат классическую информацию, преобразуется одновременно» (курсив мой. — В. Г.)[9].
Если нам удастся за один такт процессора выполнить все возможные параллельные вычисления над всеми возможными наборами входных данных, необходимых для решения нашей задачи, мы безусловно получим очень серьезный выигрыш в вычислительной мощности.
Но, как водится, гладко было на бумаге. Проблем пока больше, чем решений. Дело в том, что непосредственно с квантовой информацией мы работать не можем — не потому, что не умеем, а потому, что это запрещено: как только мы попытаемся с ней работать, она превратится в классическую (наступит «коллапс волновой функции»), причем результат работы квантовой системы перейдет в классическую информацию не однозначно, а с некоторой вероятностью. Если бы у Боба были квантовые весы, после того как он положил на них палочки (кубиты) и отвернулся (то есть не наблюдал за системой), весы показывали бы некоторый интервал значений — например, от 1 до 10 — стрелочка металась бы по шкале, а когда Боб посмотрел бы на весы, они перешли бы в классическое состояние и замерли на значении, которое не обязательно с вероятностью 100% равно 8. То есть информацию о квантовой системе можно получить только с некоторой вероятностью, и, например, для задачи сложения двух чисел обычные весы безусловно подойдут лучше квантового компьютера. Не всегда это непреодолимая помеха, но вообще говоря, классических алгоритмов, которые можно ускорить с помощью квантового компьютера, довольно мало. А таких, которые ускорить нельзя, — подавляющее большинство.
Другая проблема — это сохранение и передача квантового состояния. Квантовое состояние нельзя сохранить — его можно только создать заново. Точно так же его нельзя передать, например, по Сети, его можно только опять-таки заново создать на новом месте — этот процесс называется квантовой телепортацией, и до решения возникающих при этом проблем еще очень далеко.
Так почему же ученые с таким энтузиазмом занимаются столь трудной проблемой? К тому же еще непонятно, приведет ли преодоление многих-многих трудностей к тем прикладным результатам, которые все окупят. Скептиков более чем достаточно. Я приведу мнение академика РАН, лауреата Филдсовской премии, математика и физика-теоретика Сергея Новикова. Он касается почти всех моментов, на которых я останавливался, поэтому процитирую его подробно.
Новиков пишет: «Что такое └квантовые компьютеры”? Возможность развить теорию квантового аналога процесса вычислений сама по себе интересна как раздел абстрактной математической логики квантовых систем. Когда же мы говорим о создании компьютера, возникает первый вопрос: можно ли указать какую-либо возможную физическую реализацию, чтобы грубо оценить числовые параметры для границ, преодоление которых было бы необходимо для реализации, для оценки возможностей, скорости? Без этого подобный объект существует только в платоновской физике. Об этом пока можно только писать романы наподобие Жюль Верна. Высокопарный разговор о всесилии технологии будущего неконкретен: оставим будущее будущим людям; пока мы просто ничего не знаем. Никто не знает, можно ли реально построить достаточно большую, полностью когерентную квантовую систему, способную реализовать классически управляемые квантовые процессы по заданному довольно сложному алгоритму. Физику таких процессов надо долго изучать. А если и окажется, что можно, то будет ли основанная на этом модель вычисления работать лучше обычной в реальном мире? Не увлекайтесь сравнением числа шагов — они здесь не те, что в обычных машинах А. Тюринга и Е. Поста. Инженерной идеи пока не видно, как и физической. Есть только абстрактная квантовая логика. Машины Поста и Тюринга создавались одновременно с реальными компьютерами; это не то, что квантовые компьютеры, которых нет. В такой ситуации мне непонятны восторги по поводу уже якобы решенных с помощью квантовых компьютеров проблем типа расшифровки кодов, нужных как частным фирмам, так и структурам типа КГБ, ЦРУ и т. д. Боюсь, КГБ-подобным организациям придется подождать. Возможно, здесь действует логика рекламы: └Почему не устроить шум и не получить у них деньги на исследования? У них много денег, они платили и экстрасенсам”. Во всяком случае, гениев типа Ферми, предложившего проект создания атомной бомбы, который мог бы поддержать и Эйнштейн, здесь пока не видно. Без гениев такие вещи не создаются, люди совсем об этом забыли. А вот возникновение шума без серьезной основы стало нормой в сообществе конца XX века.
Впрочем, скажу откровенно, что мне эта теория нравится. Возникший здесь шум может быть полезен, заставляя математиков наконец-то выучить квантовую механику. Да и денег сейчас, действительно, без шума не достанешь. Так что остается лишь пожелать здесь хоть какого-нибудь успеха»[10].
Сергей Новиков полагает, что пока до конкретных решений еще очень далеко, но лучше уж пусть деньги КГБ и ЦРУ пойдут на квантовые компьютеры. Это, конечно, бесполезно, но по крайней мере безвредно.
Однако не все ученые согласны, что создание квантовых компьютеров — дело еще очень далекого будущего. Есть оптимисты, и их становится все больше. Квантовые компьютеры идеально предназначены не для классических расчетов, а для моделирования самих квантовых систем: то есть это вычислители, предназначенные для обсчета самих себя и больше почти ни для чего, по большому счету, не пригодные.
Но это очень много, потому что на квантовом уровне вычисление (моделирование) системы и ее реальное создание практически совпадают: не только вычисление есть измерение, но больше того — измерение есть конструирование.
Рассчитать с помощью квантового компьютера молекулу ДНК — это в определенном смысле ее создать. А такие перспективы не могут не увлечь. Хотя как раз в создании ДНК и искусственного интеллекта могут возникнуть проблемы уже другого, даже не квантового порядка сложности.