О.Закутняя. Квант гениальности
"Итоги", № 46, 10.11.2008
Наш соотечественник физик Алексей Китаев - один из немногих, кто знает, как сделать квантовый компьютер. За это ему присудили американский и грант гениев"
Грант Фонда Макартуров, лауреатом которого стал в этом году профессор Калифорнийского технологического института наш соотечественник Алексей Китаев, не совсем обычный. Скорее он похож на стипендию (собственно, сама программа фонда так и называется - Fellowship, стипендия на проведение научно-исследовательских работ). Она недаром получила название "грант гениев". Уровень лауреатов очень высок - среди них ученые, писатели, общественные деятели, художники, музыканты, учителя и многие другие. Размер гранта составляет 500 тысяч долларов. Эти деньги будут выплачиваться в течение пяти лет равными частями и облагаться налогом. Согласно правилам фонда, который рассматривает грант как вложение в человека, а не в научную организацию, лауреат не обязан отчитываться по нему и может распоряжаться суммой по своему усмотрению: использовать деньги для продолжения работ выбранной области, создания чего-то нового или, возможно, полной смены своих занятий.
Алгоритм будущего
Алексей Китаев заинтересовался возможностью использовать для вычислений принципы квантовой механики, еще будучи студентом МФТИ, когда читал книгу Юрия Манина "Вычислимое и невычислимое". "Во введении к этой книге, посвященной математической логике, высказывалась мысль о том, что квантовая механика может предоставить новые возможности для вычислений, - рассказал "Итогам" Китаев. - В книге этому посвящалось лишь несколько абзацев, но сама идея меня очень заинтересовала". Позже Алексей Китаев познакомился со статьей американца Ричарда Фейнмана, где эти проблемы обсуждались более определенно. А всерьез он заинтересовался темой в середине 90-х, уже работая в Институте теоретической физики им. Л. Д. Ландау РАН. Это особенное время - именно тогда были впервые выполнены работы, доказывавшие преимущество квантовых вычислений перед обычными.
В это время американский физик Питер Шор разработал квантовый алгоритм для двух задач: разложения числа на простые множители и нахождения дискретного логарифма. Немного позже Алексей Китаев разработал другой алгоритм для вычислений с абелевыми группами (алгебраическими системами с одной операцией), частными случаями которых являются эти две задачи. Суть первой из них довольно проста. Если есть два простых числа, то перемножить их и найти произведение очень легко. Но вот решить обратную задачу - найти простые множители какого-то числа - гораздо сложнее. Формулировка второй задачи звучит более сложно, чем предыдущей, но они во многом схожи. И главное, что объединяет их, - отсутствие эффективного алгоритма, позволяющего найти решение с помощью обыкновенного компьютера. Дело в том, что время, требуемое для решения, растете зависимости от увеличения количества цифр в числе. Поэтому с практической точки зрения решения часто не существует - для него требуется слишком много времени. Но квантовый компьютер, как доказали Китаев и Шор, может справиться с задачей гораздо эффективнее, за время, равное n3, где n - количество цифр в числе.
Высокая эффективность квантового компьютера объясняется тем, что он работает на иных по сравнению с обычной ЭВМ принципах. В классическом компьютере единицей информации является один бит, который может принимать значение "ноль" или "единица". В квантовом компьютере единицей информации служит квантовый бит, или кубит (от quantum bit). Он обладает необычными с классической точки зрения свойствами. Обыкновенные биты кодируются с помощью устройств, которые находятся в двух состояниях: "открыто" (логическая единица) или "закрыто" (логический ноль). Кубиты же кодируются квантовыми системами. Один из возможных вариантов (ноне единственный) - кодирование при помощи спинов элементарных частиц: состояние, когда спин частицы направлен вверх, будет соответствовать нулю, а вниз - единице. Вообще физики описывают квантовое состояние как вектор в восьмимерном пространстве. С этим квантовым состоянием можно производить определенные операции, подобно тому, как их проводят с обычными битами. Например, если два спина начнут взаимодействовать между собой, то квантовое состояние определенным образом изменится. Вычисления на квантовом компьютере будут сводиться к тому, чтобы последовательно выстроить такие операции, а потом считать результат.
Особенно эффективным квантовый компьютер будет для двух классов задач. Во-первых, для криптографии, так как операции с кубитами хорошо подходят для решения именно таких задач. И во-вторых, для моделирования реальных физических систем, в том числе квантовых -эта задача современным компьютерам пока не под силу.
К сожалению, описанная схема - пока только теория. Квантовый компьютер не воплощен "в железе". "Существует математическая модель вычислений, которая включает набор элементарных операций, сформулированных на основе принципов квантовой механики, - поясняет Алексей Китаев. - Теоретически квантовый компьютер, работающий таким образом, возможен". Необходимо научиться управлять отдельными квантовыми системами - а это задача нетривиальная. Кроме того, квантовые системы нужно тщательно изолировать от взаимодействия с окружающей средой, так как их состояние очень хрупко. Малейшее возмущение, даже пролетевший рядом фотон, может его изменить и, следовательно, поменять результаты вычислений. Проблема помех существует и в обычных компьютерах, но ее научились решать с помощью кодов, исправляющих ошибки, так что потеря некоторого количества битов не влияет на результат. В квантовых компьютерах реализовать такие коды оказалось очень сложно. Алексей Китаев был одним из первых, кто предложил и теоретически обосновал вариант создания квантового компьютера, защищенного от помех.
Без помех
"Алексей Китаев в свое время сделал несколько фундаментальных работ в области квантовых вычислений, - рассказывает Владимир Лебедев, член-корреспондент РАН, директор Института теоретической физики им. Л. Д. Ландау РАН. - В частности, он разработал принцип топологической защищенности элементов квантового компьютера, то есть дал математическое обоснование того, какой может работать. Его исследования были первыми в этой области. И хотя сам принцип квантового компьютера сформулировали раньше, только после его работ в этой области за -брезжил практический выход". Идея Ктаева состояла в том, чтобы изменить сам подход к реализации квантовых вычислений - подобрать для них такую физическую систему, в которой взаимодействия между элементами образуют нечто похожее на квантовый код. Ее состояние будет устойчивым в силу естественных свойств самой системы.
Для реализации идеи Китаев предложил использовать особенные квазичастицы - анионы (по-английски anyon, встречается также русское написание "энион", чтобы не смешивать их с химическими анионами - отрицательными ионами). Анионы - это возбуждения в двумерной электронной жидкости (например, в электронном слое между двумя полупроводниками), которые ведут себя подобно частицам и античастицам. Говоря образно, каждая квазичастица - это место, где плотность электронов немного выше или ниже среднего уровня. Анионы - устойчивые образования и обладают очень интересными свойствами. В частности, они не относятся ни к одному из двух больших классов частиц: ни к бозонам, ни к фермионам. Бозонами называют частицы с целым значением спина, фермионами - с полуцелым. Если поменять местами два расположенных рядом фермиона, то их квантовые состояния, или волновая функция, умножаются на - 1. Если переставить их обратно, то они вновь умножаются на - 1, и система возвращается в начальное состояние. С бозонами при этом процессе ничего не происходит: "переставленный" бозон ничем не отличается от "непереставленного". Довольно долгое время считалось, что все элементарные частицы (и квазичастицы в том числе) подразделяются только на эти два класса.
Но анионы не принадлежат ни к тому, ни к другому классу: при их перестановке квантовое состояние умножается не на минус или плюс единицу, а на определенное комплексное число или на оператор. Именно это свойство делает анионы очень удобными объектами для квантовых вычислений. "Вычисления начинаются с определенного состояния системы, в которой присутствуют пары анионов, - объясняет Алексей Китаев. - Частицы в такой паре, если их соединить, аннигилируют как частица и античастица. Но потом, когда мы начинаем двигать их вокруг друг друга, состояние анионов меняется. Подбирая определенную последовательность движений, можно производить вычисления. В конце мы вновь соединяем частицы попарно, но, поскольку состояние уже изменилось, они не аннигилируют полностью. Окончательное состояние системы и будет результатом вычислений на квантовом компьютере".
Эта система будет устойчива к помехам, поскольку операции кодируются не состоянием частицы, а действием с системой частиц. Траектории их перестановки при вычислениях будут сплетаться в определенный узор - для его обозначения используют термин "коса". Результат вычислений заключается именно в структуре косы. Она хорошо защищена от небольших возмущений. Это и есть принцип топологической защищенности компьютера. Существует одна тонкость: для квантовых вычислений нужны анионы определенного типа, называемые "неабелевыми". В состоящей из них системе важен порядок, в котором переставляют квазичастицы. Предполагается, что такие анионы существуют в некоторых средах, и сейчас многие исследователи ищут доказательства тому, что обнаруженные в ряде экспериментов квазичастицы являются неабелевыми анионами.
На вопрос о том, когда можно ожидать появления квантового компьютера "в железе", Алексей Китаев отвечает осторожно. По его мнению, до этого момента пройдет еще довольно много времени и пока сложно сказать, как он будет реализован физически: "Например, мне нравится мысль использовать контакты между сверхпроводниками. Из них также можно делать определенные схемы, в которых возникают топологически защищенные состояния". Сейчас уже проводятся предварительные эксперименты с этими системами. По мнению Алексея Китаева, в ближайшие десять лет ожидать появления квантового компьютера не стоит, но вот в более далеком будущем - почему бы и нет.