Это произошло на рубеже XIX и XX веков. Выдающийся математик Давид Гильберт на Всемирном математическом конгрессе в Париже в августе 1900 года сделал свой знаменитый доклад. В нем он сформулировал 23 фундаментальные математические проблемы. Одна из них — 23-я в списке Гильберта — формулируется следующим образом: существует ли «механическая» процедура, механическая — в смысле алгоритмичная, которую можно выполнить по шагам любому человеку или прибору, дающая на любое математическое утверждение ответ, верно оно или ложно. Проблему решили в 30-х годах независимо друг от друга двое ученых и ответили на вопрос Гильберта отрицательно. Один из них — австрийский математик Курт Гедель, другой — известный английский математик Алан Тьюринг, который разработал гипотетическую «машину Тьюринга» именно для того, чтобы решить эту проблему. «Машина Тьюринга» — чисто умозрительная механическая машина, которая считывает посимвольно информацию с некоей потенциально бесконечной ленты и обрабатывает ее по определенной схеме в зависимости от считанного символа.
Именно эта машина и основанные на ней вычисления, исследованные Тьюрингом, положили начало математической теории вычислений. Существует тезис Черча — Тьюринга, согласно которому любая алгоритмическая процедура может быть выполнена на этой машине. В этом смысле машина Тьюринга эквивалентна любому современному компьютеру. Но в свете нашего разговора важно, что это чисто «механическая» процедура, это исключительно математический подход к компьютингу. Вся современная теория информатики основана на машине Тьюринга. С ее помощью впервые было показано, что к теории вычислений можно подходить чисто математически, забывая, что любой компьютер — это физический прибор, что это объект физики. А это сыграет, как мы увидим, и отрицательную роль.
Кубит, еще кубит...
Все мы хорошо знаем, что компьютеры становятся миниатюрнее и миниатюрнее. Здание нашей Лаборатории в ОИЯИ — пример недальновидности прогнозов 60 — 70-х годов: центральные холлы, ныне почти пустующие, предусматривались для вычислительных машин будущего. Как тогда предполагали, более мощные машины будут требовать больше и больше места под периферию, память и так далее. В действительности все оказалось как раз наоборот.
Историческая справка. В середине 60-х годов Гордон Мур сформулировал правило, требующее удвоения производительности вычислительных систем каждые восемнадцать месяцев. До сих пор оно не нарушалось. Мур вывел свой эмпирический закон, просто подсчитав темпы роста числа транзисторов в интегральной микросхеме в зависимости от времени. Соответственно, этот закон задает темпы миниатюризации отдельного транзистора.
Если экстраполировать закон Мура, то мы увидим, что примерно в 2020 году физический размер элементарной ячейки информации в 1 бит станет размером с атом, то есть порядка 10>-8 сантиметра. Конечно, прогноз может измениться, но в целом тенденция такова. А на этом уровне, как мы знаем, классическая физика перестает работать, и в игру вступает совсем другая, квантовая физика. Если даже отвлечься от проблем нагревания, от проблем скорости обмена информации, которая ограничена скоростью света, между ячейками памяти и так далее, то человечество, увеличивая степень интеграции микросхем, столкнется с необходимостью учета квантовых эффектов в компьютинге.
Но сам по себе этот учет еще не ведет к отказу от классической модели вычислений, используемой в современных компьютерах. Это означает, в частности, что «не решаемые» задачи, требующие огромного объема вычислений, останутся «не решаемыми» независимо от роста производительности классических компьютеров. Истинно же квантовые компьютеры используют совершенно иную модель вычислений, основанную на особом наложении состояний элементарных ячеек информации — квантовых битов, или кубитов. Вычислительная мощь квантового компьютера состоит в том, что благодаря такому наложению вычисления производятся сразу с многократно большим числом состояний соответствующей системы классических битов. Это дает основание рассчитывать на переход (по крайней мере, отдельных) «не решаемых» задач в класс «решаемых».
Физики обратили внимание на важность квантовой механики для компьютинга и на преимущество квантовых компьютеров над классическими уже в начале 80-х годов, после работ нобелевского лауреата Ричарда Фейнмана. Он показал, что ни один классический компьютер не может нормально моделировать квантовую систему. В принципе может, но будет существенно запаздывать. Основываясь на этом, Фейнман сделал вывод о том, что для успешного моделирования квантовой системы нужен принципиально новый компьютер, и предложил одну из теоретических моделей квантовых компьютеров[*Подробно отмеченные аспекты квантового компьютинга рассмотрены в статье К.А. Валиева и А.А. Кокина «От кванта к квантовым компьютерам» («Природа», 2002, N° 12). В ней авторы прослеживают историю развития физики, техники и технологий от открытия кванта и изобретения транзистора к микроэлектронике и нанотехнологиям; физико-математические основы квантовых вычислений и историю их возникновения и развития; структуру квантовых компьютеров и перспективные направления развития их элементной базы.].
