Методические материалы, статьи

О квантовом компьютере и национальных традициях, или о пользе инерции

Новая грандиозная задача, встающая перед мировым научным сообществом — создание действующего квантового компьютера, — призвала под свои знамена представителей разных дисциплин. Это не только специалисты по собственно компьютингу, но и физики, и математики, и биологи. На стыке квантовой физики, теории информации и вычислительной техники рождается альтернатива традиционным компьютерам, подходящим к своему физическому пределу. Однако возникновение новой вычислительной парадигмы происходит небезболезненно, наряду с очевидными успехами проявились проблемы, к которым надо бы готовиться загодя…

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

Академик В. Арнольд


За последние два года я неоднократно выступал за рубежом перед студентами и молодыми учеными. И, к сожалению, видел, что молодые люди, которые хотят заниматься компьютингом, убеждены, что физика им совсем не нужна, а математика, если и нужна, то лишь фрагментарно, минимально. В России такое отношение пока еще не так выражено, но и здесь оно ощущается. Это устойчивое заблуждение может уже в ближайшем будущем привести к острому дефициту специалистов, способных идти в ногу с чрезвычайно быстро возрастающим уровнем компьютерных технологий, который потребует очень глубоких знаний фундаментальной физики, а также и математики. Сейчас я попробую привести аргументы в пользу такого прогноза.

Это произошло на рубеже XIX и ХХ веков. Выдающийся математик Давид Гильберт на Всемирном математическом конгрессе в Париже в августе 1900 года сделал свой знаменитый доклад. В нем он сформулировал 23 фундаментальные математические проблемы. Одна из них — 23-я в списке Гильберта — формулируется следующим образом: существует ли «механическая» процедура, механическая — в смысле алгоритмичная, которую можно выполнить по шагам любому человеку или прибору, дающая на любое математическое утверждение ответ, верно оно или ложно. Проблему решили в 30-х годах независимо друг от друга двое ученых и ответили на вопрос Гильберта отрицательно. Один из них — австрийский математик Курт Гедель, другой — известный английский математик Алан Тьюринг, который разработал гипотетическую «машину Тьюринга» именно для того, чтобы решить эту проблему. «Машина Тьюринга» — чисто умозрительная механическая машина, которая считывает посимвольно информацию с некоей потенциально бесконечной ленты и обрабатывает ее по определенной схеме в зависимости от считанного символа.

Именно эта машина и основанные на ней вычисления, исследованные Тьюрингом, положили начало математической теории вычислений. Существует тезис Черча — Тьюринга, согласно которому любая алгоритмическая процедура может быть выполнена на этой машине. В этом смысле машина Тьюринга эквивалентна любому современному компьютеру. Но в свете нашего разговора важно, что это чисто «механическая» процедура, это исключительно математический подход к компьютингу. Вся современная теория информатики основана на машине Тьюринга. С ее помощью впервые было показано, что к теории вычислений можно подходить чисто математически, забывая, что любой компьютер — это физический прибор, что это объект физики. А это сыграет, как мы увидим, и отрицательную роль.


Кубит, еще кубит…

Все мы хорошо знаем, что компьютеры становятся миниатюрнее и миниатюрнее. Здание нашей Лаборатории в ОИЯИ — пример недальновидности прогнозов 60 — 70-х годов: центральные холлы, ныне почти пустующие, предусматривались для вычислительных машин будущего. Как тогда предполагали, более мощные машины будут требовать больше и больше места под периферию, память и так далее. В действительности все оказалось как раз наоборот.

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

Если экстраполировать закон Мура, то мы увидим, что примерно в 2020 году физический размер элементарной ячейки информации в 1 бит станет размером с атом, то есть порядка 10-8 сантиметра. Конечно, прогноз может измениться, но в целом тенденция такова. А на этом уровне, как мы знаем, классическая физика перестает работать, и в игру вступает совсем другая, квантовая физика. Если даже отвлечься от проблем нагревания, от проблем скорости обмена информации, которая ограничена скоростью света, между ячейками памяти и так далее, то человечество, увеличивая степень интеграции микросхем, столкнется с необходимостью учета квантовых эффектов в компьютинге.

Но сам по себе этот учет еще не ведет к отказу от классической модели вычислений, используемой в современных компьютерах. Это означает, в частности, что «не решаемые» задачи, требующие огромного объема вычислений, останутся «не решаемыми» независимо от роста производительности классических компьютеров. Истинно же квантовые компьютеры используют совершенно иную модель вычислений, основанную на особом наложении состояний элементарных ячеек информации — квантовых битов, или кубитов. Вычислительная мощь квантового компьютера состоит в том, что благодаря такому наложению вычисления производятся сразу с многократно большим числом состояний соответствующей системы классических битов. Это дает основание рассчитывать на переход (по крайней мере, отдельных) «не решаемых» задач в класс «решаемых».

Физики обратили внимание на важность квантовой механики для компьютинга и на преимущество квантовых компьютеров над классическими уже в начале 80-х годов, после работ нобелевского лауреата Ричарда Фейнмана. Он показал, что ни один классический компьютер не может нормально моделировать квантовую систему. В принципе может, но будет существенно запаздывать. Основываясь на этом, Фейнман сделал вывод о том, что для успешного моделирования квантовой системы нужен принципиально новый компьютер, и предложил одну из теоретических моделей квантовых компьютеров1.

Таким образом, в настоящее время имеются две принципиально разные модели компьютеров: классический, основанный на машине Тьюринга, и квантовый (для его описания можно ввести понятие квантовой машины Тьюринга, как показал Дэвид Дойч из Англии), к которому проявляется очень мощный интерес во всем мире; сегодня практически все ведущие компьютерные лаборатории серьезно занимаются проектами, связанными с квантовыми компьютерами.

Как создатели первых громоздких ламповых ЭВМ не подозревали о темпах миниатюризации вычислительной техники,…

Новости из Интернета. Квантово-механическая природа атомов, особенно ярко проявляющаяся при температурах, близких к абсолютному нулю, дает возможность создавать «атомные чипы». Сотрудники Имперского колледжа и Саутгемптонского университета (Великобритания) создали из таких атомов «строительные блоки» и приступили к сборке цепей для будущих квантовых компьютеров.

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

Экспериментальное создание квантовых цепей — важнейший шаг на пути построения компьютера, основанного на квантовой механике.

Другим важным направлением исследований в области квантовых вычислений является разработка алгоритмов, основанных на особом механизме квантовых вычислений. Как показали исследования последних 10 -15 лет, квантовый компьютер способен решать отдельные задачи успешнее классического. Самый яркий пример — алгоритм 1994 года Питера Шора (США). Известно, что современная криптография, обеспечивающая защиту информации, основана на простом факте: чтобы «вскрыть» секретный код, подобрать ключ, необходимо знать разложение очень длинного (на практике составляющего сто и более цифр) десятичного числа на два множителя. Оказывается, при использовании классических алгоритмов разложения эта задача является «не решаемой». Другими словами, на классическом компьютере на «вскрытие» кода, то есть на разложение на множители длинного числа, скажем, со 150-ю цифрами, потребуется непомерно много времени, а квантовый компьютер, эквивалентный по производительности современному персональному компьютеру, сможет решить такую задачу за секунды. А это очень большая разница. Американский ученый Умеш Вазирани привел такой пример: представьте себе, что каждая элементарная частица нашей Вселенной является современным классическим компьютером. Тогда, чтобы разложить на множители дветысячизначное число с помощью всех таких компьютеров, одновременно работающих на полную мощность, не хватит всего времени жизни Вселенной! Для алгоритма Шора это займет менее часа на одном квантовом компьютере.

Когда Шор показал, что квантовый компьютер способен легко взломать любые, ныне «безопасные» коды за короткое время, то фирмы, занятые компьютерной безопасностью, криптографией, начали серьезно воспринимать и финансировать исследования по квантовым вычислениям. Существуют и другие квантовые алгоритмы, хотя их пока еще очень мало, которые существенно лучше классических.

Говорить о самой квантовой машине как таковой пока рано, когда она будет создана — непонятно. Тем не менее лаборатории строят экспериментальные модели квантовых компьютеров, основанные на ядерно-магнитном резонансе и ионных ловушках. Уже созданы системы из нескольких квантовых битов.

Новости из Интернета. IBM продемонстрировала использование созданного в лабораториях компании семикубитового квантового компьютера. Хотя решенная им задача вряд ли способна поразить воображение (компьютер верно определил, что делителями числа 15 являются числа 3 и 5), это самое сложное вычисление за всю историю квантовых компьютеров. Компьютер, созданный группой ученых из IBM и Стэнфордского университета, представляет собой пробирку с миллионами молекул, имеющих семь ядерных спинов. Он может быть «запрограммирован» при помощи электромагнитных импульсов разной частоты, а для получения результатов работы устройства используется ЯМР-сканер.

Исследователи Висконсинского университета (США) добились успеха в моделировании архитектуры квантового компьютера и утверждают, что современный уровень технологий позволяет воплотить идеи в железе. В качестве квантового бита будут использоваться электроны, находящиеся в квантовых зонах полупроводников. В зависимости от спина электрона определяется значение бита — 0 или 1. Проблемы квантовых операций — высокая чувствительность к повышению входного напряжения и требование однородности структуры, ведь для нормальной работы квантового процессора потребуется свыше миллиона битов электронов. Но, по мнению исследователей, существующее оборудование для кремниевого производства можно использовать для производства квантовых компьютеров.

Владимир Гердт – доктор физико-математических наук, профессор, начальник сектора Лаборатории информационных технологий ОИЯИ (Дубна)

Квантовый компьютер является по самой своей природе вероятностным, не детерминистским, как классический компьютер. Сам процесс квантовых вычислений — временная эволюция состояний кубитов — описывается уравнением Шредингера, а вывод результата представляет собой физический процесс «измерения».

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


Понедельник начинается в субботу

Говоря о современном компьютерном образовании во всем мире, я хотел бы отметить, что, на мой взгляд, математика и особенно логика изучаются весьма поверхностно. В мире создаются очень сложные программы и системы, которые требуются для обработки колоссальных массивов данных, интернет-технологий, распределенных вычислений, создания больших программных комплексов управления сложнейшими объектами, моделирования приборов и диспетчеров в авиаперелетах и так далее. Для создателей этих программ главное — надежность. Она всегда основывалась на верном следовании хорошим эмпирическим правилам. Сбой в работе таких программных комплексов — это катастрофа. Как проверить правильность их работы?

С точки зрения современных технологий, для правильной проверки необходимо использовать математическую логику. При отладке, верификации сложнейших программных систем логика играет фундаментальную роль. В конце октября прошлого года в Линце проходил конгресс «Логика. Компьютинг. Математика», посвященный юбилею одного из крупнейших современных специалистов во всех трех областях — австрийского ученого Бруно Бухбергера, который неоднократно бывал у нас в Дубне. Там отмечалось возникновение глубокого кризиса: разрабатываются огромные программные комплексы, а при этом у специалистов, занимающихся их отладкой, отсутствуют глубокие знания по математической логике. Именно только логический анализ всей совокупности программ и подпрограмм, знание логики всего хода вычислений позволят реально создать надежный программный продукт. Остальное — эффект опыта. Но если работать на одном опыте, на тестах, тогда вам ничего не будет гарантировано, особенно при постоянном все большем усложнении программного обеспечения.

Безусловно, любая компьютерная специальность изучает логику, но явно недостаточно. И студенты, освоив курс, подчас тут же его забывают. В лучшем случае знают элементы Булевой алгебры. Но саму логику — как математику — не знают. С точки зрения высоких технологий и новой техники, в первую очередь надо изучать физику и математику. Конструктивную математику, которая затем необходима в технике, нужно изучать очень глубоко. Уверен, что технологический уровень заставит весь мир через какое-то время повернуться лицом к математике и физике, как это было в 30-е, 40-е, 50-е, 60-е, 70-е годы.

Сегодня в курсе школьной информатики традиционно дают один из языков программирования, обычно Паскаль. Важно, если школьник хотя бы на одном языке программирования научится писать программы, освоит эту логику. Но не менее важно давать обзор развития информационных технологий или историю развития вычислительной техники в мире, в Советском Союзе, в России — какие машины создавались, какие задачи они решали — это же очень увлекательно. Понятно, что это нужно давать и будущим преподавателям в вузах или привлекать в школы людей из науки.

Отставание образования от реальных потребностей физики и техники хорошо прослеживается на информатике. Еще 10 — 15 лет назад в Германии факультеты информатики были, в общем-то, «на заднем плане». Заметно большее внимание уделялось физике, математике, биологии, другим предметам. Были свободные профессорские ставки, высококвалифицированные специалисты предпочитали не преподавать, а идти в промышленность. А потом оказалось, что за последние 5 — 10 лет спрос на специалистов по информатике возрос очень сильно, и выяснилось, что их не хватает. Стали приглашать специалистов из России, Индии, отовсюду. Сейчас ситуация изменилась, на информатику студенты идут очень охотно. Лет через десять Германия более-менее удовлетворит свои потребности в специалистах в области программирования и информационных технологий. Подобная картина, я думаю, будет наблюдаться и с физикой и математикой. Когда создадут квантовый компьютер, то не будет хватать специалистов, которые способны на нем работать: чтобы просто написать программу, надо знать квантовую механику. Для подготовки новых специалистов нужно будет сначала подготовить преподавателей для них, а на это уйдут годы и годы.


Не потерять в реформах традиции

Страна становится лидером, когда продает не сырье, а технологии. Одно интересное наблюдение на эту тему. Япония, одна из самых развитых стран в мире, в 80-х годах взялась за очень амбициозный проект создания вычислительных машин пятого поколения. Предполагалось тратить до 15 процентов валового продукта страны на этот проект. На чем они споткнулись? Япония обладала высочайшими технологиями, но только в создании «железа». У них не было интеллектуального опыта и традиций, они не вкладывали деньги в математическое образование, в создание программного обеспечения. В итоге этот проект Япония не смогла реализовать.

«Железо», микросхемы сегодня не главное. Все более интеллектуальным и дорогим становится программное обеспечение. И здесь очень важно математическое образование, культура, опыт. У японцев есть суперкомпьютеры, но они используют американское программное обеспечение. Америка после войны сразу стала вкладывать деньги именно в разработку программ, в интеллектуальную сферу компьютинга. Они сейчас лидеры. Европейцы в отдельных направлениях тоже. У нас же было много ошибок в советские времена. Была создана мониторная система «Дубна», поколение машин БЭСМ-6 — великолепные машины с собственным программным обеспечением. Потом мы пошли по западному пути, стали адаптировать западные технологии и системы и в итоге отстали и технологически, и в создании программных продуктов. Сегодня у нас есть великолепные, но одиночные программные продукты.

Не понимаю, почему наши реформаторы средней школы стараются идти по пути западных систем образования, не дающих сегодня, как показывает практика, хороших результатов. Не надо этого делать. Кто на последней олимпиаде по программированию, проходившей осенью 2001 года на Гавайях, занял первое место? Китайцы. Они действуют умно, не теряют свои традиции. К счастью для нас всех, реформы школьного образования идут со скрипом. Мы еще сохраняем хотя бы частично тот могучий потенциал, который был заложен в советскую и досоветскую эпоху. До сих пор у нас уровень школьного образования, несомненно, выше, чем в западных странах. Но тенденция идет к его потере.


Информация к размышлению

Наиболее достоверные представления о динамике качества знаний, получаемых выпускниками школ, а также студентами в процессе вузовского обучения, можно получать на основе содержательного анализа достаточно больших массивов письменных работ абитуриентов и учащихся. Результаты исследований, проведенных в некоторых вузах Сибири, показывают, что задачи по математике, которые 25 — 30 лет назад успешно решало на приемных экзаменах подавляющее большинство поступающих, в последние годы оказываются посильными лишь для немногих. Требованиям, которые в 60-е годы предъявлялись на вступительных экзаменах в вузы по русскому языку и литературе, сегодня могут отвечать не более 10 процентов абитуриентов, хотя средний балл, получаемый ими, при том не снижается, а скорее, растет.

… так многие современные специалисты по компьютерному образованию не подозревают о необходимости изучения в скором будущем квантовой механики

В качестве экспертов, компетентных в этом вопросе, можно рассматривать профессоров, которые не один десяток лет преподают в вузах. Они, как правило, в один голос говорят об общем резком снижении уровня естественнонаучных знаний. Катастрофическое снижение уровня математической грамотности и культуры, по мнению академика РАН В.И. Арнольда, для России губительнее костров инквизиции. Российские либеральные реформаторы, круто повернувшись на Запад, заставляют педагогов слепо копировать оттуда все как заведомо самое лучшее, «забывая» о том, что советская средняя и высшая школа по уровню естественнонаучной и математической подготовки всегда занимала лидирующие позиции в мире. Видимо, они таким способом, как считает В.И. Арнольд, стремятся приблизить наш (достаточно высокий) уровень математического образования к американскому (традиционно низкому) в то самое время, когда сами американцы начинают перенимать наш опыт, поставив целью сделать свое образование лучшим в мире. Система образования в принципе не может оставаться благополучной в разрушаемой стране. Если в начале 60-х годов эксперты ЮНЕСКО признавали систему образования в СССР лучшей в мире, то в 90-х наша школа скатилась по уровню знаний и коэффициенту интеллектуального развития на серединное место в последней двадцатке слаборазвитых стран.

Статья подготовлена О. Тарантиной

Послесловие

В следующих номерах журнала темы, затронутые В. Гердтом, получат развитие в материалах о квантовом компьютере и о пресловутой «утечке мозгов».

1Подробно отмеченные аспекты квантового компьютинга рассмотрены в статье К.А. Валиева и А.А. Кокина «От кванта к квантовым компьютерам» («Природа», 2002, № 12). В ней авторы прослеживают историю развития физики, техники и технологий от открытия кванта и изобретения транзистора к микроэлектронике и нанотехнологиям; физико-математические основы квантовых вычислений и историю их возникновения и развития; структуру квантовых компьютеров и перспективные направления развития их элементной базы.

Владимир Гердт

ПРОЕКТ
осуществляется
при поддержке

Окружной ресурсный центр информационных технологий (ОРЦИТ) СЗОУО г. Москвы Академия повышения квалификации и профессиональной переподготовки работников образования (АПКиППРО) АСКОН - разработчик САПР КОМПАС-3D. Группа компаний. Коломенский государственный педагогический институт (КГПИ) Информационные технологии в образовании. Международная конференция-выставка Издательский дом "СОЛОН-Пресс" Отраслевой фонд алгоритмов и программ ФГНУ "Государственный координационный центр информационных технологий" Еженедельник Издательского дома "1 сентября"  "Информатика" Московский  институт открытого образования (МИОО) Московский городской педагогический университет (МГПУ)
ГЛАВНАЯ
Участие вовсех направлениях олимпиады бесплатное

Номинант Примии Рунета 2007

Всероссийский Интернет-педсовет - 2005