Архивы: по дате | по разделам | по авторам

Идейный фундамент

Архив
автор : Михаил Фейгельман   28.09.2001

Быстродействие компьютеров в течении последних двадцати-тридцати лет растет впечатляющими темпами, однако этот рост имеет свои естественные пределы. В частности, вряд ли можно ожидать, что размер транзистора может быть меньше размера атома водорода, а рабочая частота - больше 1 000 000 000 000 000 Гц.

В этот момент мне хотелось быть шкипером. Я бы сказал - густо, окладисто, с хрипотцой что-нибудь отчаянное, например: «Пусть перелопаются в моем мозгу все тросы, если я что-нибудь понимаю!»
Александр Грин. «Золотая цепь»

Быстродействие компьютеров в течении последних двадцати-тридцати лет растет впечатляющими темпами, однако этот рост имеет свои естественные пределы. В частности, вряд ли можно ожидать, что размер транзистора может быть меньше размера атома водорода, а рабочая частота - больше 1 000 000 000 000 000 Гц (частота атомных переходов). Фактически проблемы начинаются гораздо раньше. В малых, но еще не атомных масштабах (их называют мезоскопическими; обычно это единицы микрон) сопротивление проводников (особенно при низких температурах) начинает существенно зависеть от положения одной-единственной примеси; магниты, если их сделать очень маленькими, начинают проявлять квантовые свойства и не желают сохранять направление намагниченности и т. д. Некоторое время назад считалось, что квантовые эффекты ставят естественный барьер дальнейшему совершенствованию компьютерной элементной базы.

Однако позднее обнаружился нетривиальный способ преодоления грядущих сложностей (частичный и пока еще гипотетический, но все же способ): вместо того чтобы избегать квантовых эффектов, наоборот, - достигнуть предельной квантовости и использовать новые возможности.

Надо заметить, что хотя квантовые компьютеры и квантовые вычисления обсуждаются довольно давно (первые идеи были высказаны Ю. Маниным, Р. Фейнманом и Д. Дойчем), настоящий интерес к себе они привлекли после того, как П. Шор обнародовал свой знаменитый квантовый алгоритм (алгоритм факторизации целых чисел). Стало ясно, что все это может иметь практический смысл (и не только для взломщиков кодов). Дело в том, что существует довольно много вычислительных задач так называемой экспоненциальной сложности - таких, которые любой классический компьютер может решить лишь за время, экспоненциально растущее с «размером» задачи. Такова, например, задача детального расчета свойств молекулы из N >> 1 атомов. Квантовые алгоритмы обещают возможность решения некоторых из них за время, растущее по мере увеличения числа N лишь степенным образом (скажем, кубически). При большом N разница приобретает критическое значение!

Однако заметим, что число известных квантовых алгоритмов, которые в самом деле работают быстрее обычных, очень невелико (алгоритм Шора как раз и был первым таким примером).

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

Много чисел в одну квантовую систему можно поместить в силу того, что в квантовом мире работает принцип суперпозиции. Вообще говоря, принцип суперпозиции в некоторой форме имеет место и в классической волновой физике, где он более известен как явление интерференции (света, волн на воде и т.п.). Однако в квантовой физике утверждается нечто новое: частица может находиться в суперпозиции экспериментально различимых состояний 1. Так, в отличие от «классического» триггера, один и тот же кубит может одновременно находиться в двух состояниях, а, предположим, один регистр из четырех кубитов способен одновременно хранить шестнадцать двоичных четырехразрядных чисел.

Суть квантового вычисления

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

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

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

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

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

При измерениях каждый из кубитов окажется в одном из состояний, причем если повторять измерения, то результаты будут другими, поскольку при каждом измерении суперпозиционное состояние безвозвратно коллапсирует к какому-то одному из полного их числа. Такой коллапс - это еще одно ограничение на квантовое вычисление: невозможно «подсмотреть» промежуточный результат, иначе все испортишь.

Каков же выход? Он, в общем-то, очевиден: вычисление должно приводить к результату, факторизованному по отдельным кубитам. Только в этом случае можно проводить измерения (после вычисления) последовательно над каждым кубитом в отдельности, не портя квантовые состояния остальных. Причем в идеале каждый кубит должен находиться в одном из двух заранее заданных состояний (то есть фактически к концу вычисления должно появиться вполне определенное число в двоичной записи на кубитах, и никаких квантовых суперпозиций!). Именно это требование задает колоссальное ограничение на теоретически возможные квантовые алгоритмы.

Что требуется для КК

Опишем теперь требования к универсальному квантовому компьютеру (вообще говоря может быть и неуниверсальный, неподстраиваемый КК 2). Итак:

  1. КК должен состоять из большого числа (N >> 1) элементарных кубитов - аналогов спина. Тут надо помнить, что физически кубит может быть вовсе не элементарным спином электрона, а сложной системой, построенной из многих частиц (подробнее об этом чуть позже). Главное требование к такой системе: в подходящем масштабе времени она должна быть «похожа» на спин, чтобы все происходящие в ней события могли быть описаны при помощи квантовых состояний (волновых функций), аналогичных применяемым для описания спинов.

  2. Гамильтониан 3 системы должен уметь «запутывать» состояния каждой пары кубитов (коих N•(N-1)/2 штук) и производить любые повороты каждого отдельного «спина».

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

  4. Каждый из кубитов с высокой надежностью необходимо изолировать от внешнего мира; время декогерентности должно быть много больше, чем время выполнения вычислений. «Много больше», по оценкам разных авторов, означает в тысячу (оптимисты) или в миллион раз больше (пессимисты). Основаны эти разные оценки на одном общем соображении: чтобы на КК получить сколько-нибудь интересный результат, надо уметь исправлять появляющиеся в процессе вычисления ошибки.

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

  5. Необходимо уметь производить в конце процесса «измерение» - то есть выяснять, в каком состоянии оказался каждый из N кубитов к концу действия алгоритма. Это требование выглядит столь очевидным, что может быть не сразу ясно, почему его вообще стоит упоминать. Однако дело в том, что принципиальная возможность произвести измерение, приводящее к однозначному результату (типа: 5-й кубит - в состояии «h» а 17-й - в состоянии «i»), означает, что каждый из наших кубитов должен быть в указанное алгоритмом время приведен в состояние сильного взаимодействия с измерительным прибором - для того чтобы произошел быстрый коллапс волновой функции.

Вот тут мы и обнаруживаем, что приведенные выше требования 1-5 очень плохо согласуются друг с другом в физическом мире: изолированность кубитов от внешней среды в процессе вычислений явно противоречит возможности точно управлять значениями параметров гамильтониана, да и возможности эффективно измерять конечное состояние. Среди множества предложенных в последние годы физических идей насчет способов реализации КК нет ни одной, которая бы естественным образом отвечала на вопрос, как согласовать все эти условия? Именно поэтому задача построения КК столь сложна.

Прежде чем описывать имеющиеся предложения «из чего построить КК» - обратим внимание на существование двух основных классов таких предложений: исходный элемент КК - кубит - может быть либо микрообъектом (спин электрона или ядра, атом или ион), либо объектом мезоскопическим 4 - то есть состоящей из большого числа электронов системой (сделанной из сверхпроводящих контактов субмикронных размеров, или полупроводниковых квантовых точек, или «молекулярных магнитов» - больших молекул со спином).

«Микрокубиты» лучше подходят по критерию 4 - взаимодействие элементарных спинов с шумовым электромагнитным полем и другими кубитами можно сделать очень слабым. Но именно поэтому результат их квантовой эволюции будет трудно измерить (п. 5): ведь в отличие от обычного физического измерения, когда интересуются, например, средней намагниченностью ферромагнетика, здесь надо измерять направление каждого из спинов по отдельности. А как к спину отдельного электрона или ядра подключить измерительный прибор?

Наоборот, «мезокубиты» естественным образом удовлетворяют требованиям 1, 2, 3 и 5, но имеются большие проблемы с 4: взаимодействие системы из большого числа электронов с разными «паразитными» переменными неизбежно будет сильнее, чем для отдельных электронных спинов. Какой из этих двух основных подходов в конце концов приведет к успеху - пока никто не знает.

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

Врезки

[i41424]


1 (обратно к тексту) - Экстремальный пример такого рода был придуман Шредингером и известен под названием кота Шредингера (КШ), который может в одно и тоже время находиться в живом и мертвом состоянии согласно принципу суперпозиции. Надо заметить, что квантовая механика действительно не запрещает такого состояния, и Шредингер даже придумал конкретное устройство, производящее таких котов (ружье, управляемое пролетающей мимо квантовой частицей со спином: если спин направлен «вверх», ружье стреляет в кота, а если спин «вниз» - не стреляет). Построение квантового компьютера - это, по сути, изготовление такого мини-КШ, существующего некоторое время, достаточное для проведения нетривиальных операций.
2 (обратно к тексту) - Так бывает и в жизни обычных компьютеров: например, в Bell Labs (1984 г.) и в Институте им. Ландау (1990 г.) были построены специальные процессоры для моделирования больших статистических систем методом Монте-Карло. Ничего другого такие процессоры не умели, но зато это они умели очень хорошо, лучше серийных суперкомпьютеров. Можно и для КК выбрать некоторую схему, которая реализует один-единственный алгоритм, - вопрос в том, как это сделать и как понять, для чего такой алгоритм полезен.
3 (обратно к тексту) - Для тех, кто не знаком со словом «гамильтониан», но еще помнит линейную алгебру, заметим, что гамильтониан - это оператор, действующий на вектор состояния и задающий скорость его изменения во времени. Гамильтониан можно представить в виде матрицы. Уже упоминавшийся ранее унитарный оператор, определяющий эволюцию во времени - это экспонента от гамильтониана и, соответственно, тоже матрица. Отметим еще одно любопытное обстоятельство: в гамильтониане присутствуют слагаемые, задающие лишь парные взаимодействия. Это общее свойство, все известные фундаментальные взаимодействия - только парные. Явно просматривается аналогия с математическим утверждением, что любые сколь угодно сложные операции над произвольным числом кубитов сводимы к последовательности одно- и двухкубитных операций.
4 (обратно к тексту) - Отличие мезоскопической системы от обычной макроскопической прежде всего в том, что ее размер хоть и велик, но недостаточно велик для того, чтобы забыть ее «квантовое происхождение», - то есть в ее поведении существенны квантовая интерференция и дискретность составляющих систему частиц; например, бывает возможно определить четность числа электронов на сверхпроводящем «островке», хотя полное их число там порядка 109.

Врезка 1

В одном из интервью Алексей Китаев (выпускник МФТИ, старший научный сотрудник Института теоретической физики им. Ландау и один из известнейших из авторитетнейших специалистов по квантовым вычислениям) заявил, что Российская общенациональная программа создания квантового компьютера может быть сравнима с программой создания атомной бомбы, отметив попутно, что фигуры масштаба Курчатова у нас сейчас просто нет, «хотя руководителей для нескольких небольших проектов найти можно».


Врезка 2

А зачем вообще нужен квантовый компьютер? Принято отвечать, что для ускорения счета. Однако если только для этого, то это грустно, господа. Когда в 1990-х годах в недрах отечественной «оборонки» стали поговаривать о квантовых вычислителях, имели в виду нечто концептуально более красивое. Речь шла о создании материальной системы, обладающей физическими свойствами должным образом обрабатывать информацию. Отсюда - надежность функционирования на уровне законов Природы. Как бы это проиллюстрировать? Ну, например, так: камень, который мы швырнули вверх, с высочайшей надежностью совершит движение по траектории, представляющей собой решение дифференциального уравнения. При том, что «на борту» этого камня нет ни датчиков, ни вычислителя, в память которого заложена программа движения. Камень просто летит себе и летит. Поскольку речь шла о бортовых вычислителях, задача приобретала вид исключительно изящный: найти (построить, синтезировать) такую квантовую систему, динамические свойства которой в соединении с динамикой, предположим, ракеты-носителя обеспечивали бы естественную устойчивость полета с абсолютной надежностью исполнения закона движения (то есть попадания в цель).

© ООО "Компьютерра-Онлайн", 1997-2024
При цитировании и использовании любых материалов ссылка на "Компьютерру" обязательна.