Квантовые компьютеры и квантовые вычисления

Что это такое и с чем его едят

Эти слова (поставленные в заголовок) появились в обиходе не вчера. Сегодня их уже употребляют и к месту и не к месту. Чаще – не к месту. А их правильного смысла в широком обиходе нет. Он бытует в узких кругах специалистов.

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

А представления о квантовом компьютере у меня (и – думаю – у огромного множества других людей) до недавних пор были примерно такие.

Есть так называемый закон Мура, согласно которому число элементов в единице объема процессора удваивается каждые, если не ошибаюсь, два года. Это значит, что размеры единичного схемного элемента (транзистора) каждые два года вдвое уменьшаются. В конце концов (и время это не за горами), наступит такой момент, когда для описания его работы станет невозможно пользоваться классическими (если быть совсем точным – квазиклассическими) представлениями и придется в полной мере опираться на законы квантовой механики, описывающие физику совсем мелких объектов. Вот тогда-де и наступит эра квантовых компьютеров. То есть, квантовый компьютер – это технологическое продолжение того, что уже сегодня стоит у меня на столе. Как же я заблуждался!

А когда я понял, что с квантовым компьютером надо навести порядок и в собственной голове и, – по возможности, – в головах других людей, мне помог это сделать профессор Григорий Николаевич Жолткевич – декан мехмата Харьковского университета им. В.Н. Каразина и по совместительству заведующий его кафедрой теоретической и прикладной информатики.

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

– Дело в том, что с моей профессиональной точки зрения компьютер не есть физическая система. Это система вычислительная. И эти две вещи – вычислительную систему и ее физическую реализацию – нужно разделять. Совершенно неважно, на каких физических явлениях и устройствах она будет реализована, лишь бы она обладала вполне определенным функционалом. Когда мы говорим о современном компьютере, важно, чтобы он был реализацией универсальной машины Тьюринга, а эта последняя основывается на классических представлениях не квантовых. Это математическая абстракция, построенная – опять таки из умозрительных – очень простых функциональных элементов с хорошо известными свойствами, с помощью которой специалисты думают о вычислительных системах и вычислениях.
Следует подчеркнуть, что современные вычислительные системы моделируют вычислительный процесс, т.е. процесс обработки информации, так, как если бы информацию обрабатывал человек. А мы, –  люди, – классические системы, а не квантовые, поэтому и воспринимаем мир с классической точки зрения.

– А что, возможны и другие модели?

– В 1980, если я не ошибаюсь, году московский математик Манин опубликовал книгу “Вычислимое и невычислимое”. В ней он занимался двумя тесно связанными друг с другом проблемами. Первая (проблема вычислимости) состоит в том, чтобы установить, можно ли на компьютере в принципе решить данную задачу, а вторая (проблема сложности) – можно ли данную (в принципе решаемую) задачу решить на данном компьютере с его конкретными ресурсами. А данный компьютер – это всегда машина Тьюринга.

– Тогда что же такое квантовый компьютер?

– Давайте вернемся немножко назад и кое-что уточним. Машина Тьюринга – это не компьютер, она реализуется в компьютере. Машина Тьюринга – это предписание, как решать задачу, это алгоритм. Каждая конкретная машина Тьюринга – это решатель определенного класса задач, и основной результат теории алгоритмов состоит в том, что существует такая машина Тьюринга, которая может решить все задачи, которые в принципе можно решить. Она называется универсальной машиной Тьюринга. Все компьютеры, которые у нас есть – это физические реализации универсальной машины Тьюринга. Поэтому, прежде, чем говорить, что такое квантовый компьютер, надо сказать, что такое квантовый алгоритм. А с этим дело обстоит довольно сложно. Первый из известных нам алгоритмов – алгоритм нахождения наибольшего общего делителя двух целых чисел – изобрели еще древние греки. С тех пор им все пользовались, не зная формального определения, что такое алгоритм. Лишь в 1936 году Алану Тьюрингу удалось дать формальное определение, и математики получили возможность работать с ним на современном уровне математической культуры. Если быть совсем точным, то в 1936 году в таком порядке: А. Черч, А. Тьюринг, Э. Пост, опубликовали свои формальные определения алгоритма. Определения Тьюринга и Поста очень похожи и их эквивалентность почти очевидна, определение Черча сформулировано на совсем другом языке – языке, который он специально придумал для этого (ламбда-исчисление). Но в 1937 году Тьюринг доказал эквивалентность определения Черча своему. Так вот, для квантового алгоритма формального определения до сих пор не существует, поэтому говорить о квантовых вычислениях на должном уровне математической строгости пока нельзя.

– Означает ли это, что наука о квантовом компьютере зашла в некий теоретический тупик?

– Нет, конечно. Тысячи лет люди не знали формального определения классического алгоритма, но это не мешало им работать на интуитивно-эвристическом уровне. Точно так же будет обстоять дело и с квантовым алгоритмом – мы будем им пользоваться, формально не до конца понимая, что же это такое. Первые образцы квантовых алгоритмов появились в конце 80-х– начале 90-х годов прошлого века. Сколько времени понадобится, чтобы до конца понять, что такое квантовый алгоритм? Думаю, 500 лет на это не потребуется.

– Вы говорили, что главное – это именно алгоритм, а не “железо”. Можно ли сделать квантовый компьютер на сегодняшнем “железе”?

– Только формально. Практической пользы от него не будет – быстродействия не хватит.
Но вообще-то польза, конечно, есть. Такие симуляции позволяют исследовать квантовые информационные системы, не реализуя их в «железе». Для науки это очень важно, ведь те кубиты (квантовые аналоги битов), которые сегодня умеют изготавливать, например, во ФТИНТе, стоят 2 500 евро за штуку.

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

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

В той книге, которую я уже цитировал, Манин говорит, что проблему сложности можно было бы преодолеть, использовав не классические, а квантовые вычисления, если проэксплуатировать для этого квантовомеханический принцип суперпозиции. Он назвал это “квантовым автоматом” и больше ничего не сказал. А в 1982 году физик, Нобелевский лауреат Ричард Фейнман, сделал теперь уже знаменитый доклад, в котором он сказал, что из-за крайней вычислительной сложности, отличающей математические модели в квантовомеханических задачах, их можно было бы атаковать с помощью квантовомеханических вычислительных систем, высказав, как и Манин, мнение, что здесь не следует привязываться к технологической конкретике, а следует разработать абстрактную модель вроде машины Тьюринга, только основанную на фундаментальных законах квантовой механики. Вот тогда и прозвучали впервые слова: квантовый компьютер и квантовые вычисления. Таким образом, здесь видны два круга проблем: с одной стороны, физики хотят заниматься созданием реальных элементов “квантового”, если можно так сказать, поколения ЭВМ, а с другой – отчетливо чувствуется нужда в фундаментальных исследованиях, требующих формальных определений. Вот вокруг этого все и крутится. Кроме того, есть примеры задач, имеющих очень высокую сложность для классических компьютеров, которые за шаг решаются на квантовых (если бы, конечно, они были).

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

Беседовал Валерий Тырнов