Файл: деп_тукс_10_11.doc

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

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

Теперь давайте подумаем о характеристиках локального вероятностного компьютера, который может моделировать природу (под природой будем понимать квантовые системы). Одна из характеристик - это то, как какая-то величина ведет себя в локальной области в пренебрежении тем, что происходит в других областях. Например, предположим, что имеются переменные в системе, которые описывают весь мир , причем, переменныеx_A - это те, которыми интересуемся мы - вокруг нас, а x_B - остальные переменные вселенной. Если нас интересует вероятность того, что что-то произойдет “вокруг нас”, т.е. в т. х_А , мы должны проинтегрировать общую вероятность по “лишним” переменным. Если мы уже вычислили эту вероятность, то нам осталось выполнить интегрирование:

,

что само по себе довольно трудно. Однако если мы сымитировали вероятность, это становится очень просто: нам ничего не нужно делать для вычисления интеграла - мы просто отбросим все значения вероятности от переменной х_В, просто глядя на нужную нам область х_А. Следовательно такая величина будет иметь природные характеристики: если она локальна, то можно обнаружить, что происходит в данной области, не посредством интегрирования или какой-нибудь другой процедуры, а просто отбрасывая все, что происходит в других местах, что вообще не является операцией.

Итак, мы подошли к вопросу о том, как моделировать с помощью компьютера квантово-механические эффекты. Квантовая механика описывает эффекты посредством дифференциальных уравнений относительно волновой функции . Если у нас имеется одна частица,является функциейx и t и такое дифференциальное уравнение можно смоделировать. Так можно моделировать уравнение Шредингера для одной частицы. Но полное описание квантовой механики дается волновой функцией , которая является амплитудой вероятности найти частицы в точкахи поэтому не может быть смоделирована на обычном компьютере, как имеющая слишком много переменных. В этом обычном компьютере число элементов пропорциональноR или N. Такая же проблема возникает и с вероятностным описанием в классической физике. Как же можно моделировать квантовую механику? Есть два способа это сделать. Можно отказаться от правила, по которому работает компьютер. Мы говорим: давайте сделаем компьютер из квантово-механических элементов, которые удовлетворяют законам квантовой механики. Другой путь такой - пусть компьютер будет логическим универсальным автоматом.

Прежде всего, заметим, что законы квантовой механики обратимы во времени, поэтому мы должны рассматривать квантовые вычислительные устройства, подчиняющиеся законам обратимости. Напомним, что одним из выводов науки о вычислениях является факт, что универсальное вычислительное устройство может быть сделано на основе соответствующей сложной сети элементарных логических элементов. В классическом компьютере проводники, соединяющие ЛЭ, должны быть идеальными, и переносить токи, вызывающие падения напряжения на сопротивлениях, которые соответствуют двум уровням “1” и “0”.

7.4.3. Алгоритм разложения на простые множители или алгоритм Шора

Алгоритмы факторизации числа на простые множители и дискретного логарифмирования были предложены Питером Шором. Сами по себе эти квантовые алгоритмы, действительно приводящие к выходу из NP-класса сложности, не являются прорывом в области вычислительной техники, в том смысле, что эти методы, не являются основными в решении вычислительных задач. Единственная причина, по которой они интересны - то, что такие методы (односторонние функции) используются при распределении ключа. Заметим, однако, что к настоящему времени найден классический алгоритм, позволяющий определить, является ли данное число простым или нет за полиномиальное время.

7.5. Общие требования к квантовым компьютерам Практическая реализация

Каким же образом кубиты реализуются в физических системах и, прежде всего, в качестве ячеек памяти (регистров) квантового компьютера?

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

1. Создание квантового процессора;

2. Создание устройства для хранения квантовой информации (квантовая память);

3. Разработка квантовой шины для обмена информацией.

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

1. Физическая система, представляющая собой квантовый процессор, должна содержать достаточно большое число N > 100 хорошо различаемых кубитов для выполнения соответствующих квантовых операций.

2. Необходимо обеспечить условие для приготовления входного регистра в исходном основном базисном состоянии, т.е. есть должна существовать достаточно легко реализуемая возможность зануления регистра и перевода кубитов в чистое состояние.

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

4. Необходимо обеспечить за время такта выполнение требуемой совокупности квантовых логических операций, определяющей унитарное преобразование. Как известно, любую математическую операцию – арифметическую, т.е. сложение, вычитание, умножение, деление и т. д., и логическую - «и», «или» и т. д., можно свести к ограниченному числу логических операций. Из них основные всего лишь три: операция CNOT (контролируемое НЕ, Controlled NOT, аналог исключающего ИЛИ в классических компьютерах) - это двухкубитная операция, а также две однокубитные операции — операция НЕ и преобразование Адамара. Умея выполнять эти операции над кубитами, можно реализовать любую программу для квантового компьютера.

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

Т.о., кратко, для реализации квантового компьютера необходимо:

1. Реализация системы кубитов;

2. Осуществление механизма “перепутывания” кубитов;

3. Осуществление контролируемым образом логических операций над кубитами. Реализация логического элемента (ЛЭ).

4. Система должна быть масштабируемой, т.е. логические операции должны распространяться на N кубитов.

5. Физическая система должна быть квантово-механически стабильна.

6. Необходим механизм, осуществляющий запись, чтение и сброс данных.

В последнее время ведутся работы над следующими основными вариантами физической основы (элементной базы) квантового процессора.

1. Использование в качестве квантового процессора пробирки с органической жидкостью, где кубитами являются ядра отдельных атомов со спинами 1/2, связанные косвенными спин-спиновыми взаимодействиями. Органическая жидкость в пробирке ведет себя как одна молекула этого вещества, точнее, все молекулы ведут себя одинаково в тех взаимодействиях, которые необходимы. Таким образом, появляется возможность применить к макроскопическим объёмам жидкости отработанные методики и техники ядерного магнитного резонанса (ЯМР). Индивидуальное обращение к отдельным кубитам заменяется обращением к соответствующим кубитам одновременно во всех молекулах большого ансамбля. Логические операции над кубитами (с помощью радиочастотных импульсов) и вывод результата осуществляется стандартными методами ЯМР. Компьютер такого рода получил название ансамблевого квантового компьютера. Он может работать и при комнатной температуре. Время декогеренции квантовых состояний ядерных спинов в жидкости достаточно велико и может составлять несколько секунд. Именно при использовании этой элементной базы в настоящее время достигнут самый значительный успех в практической реализации квантовых вычислений. В 1998 году впервые в мире группой И.Чуанга создан 2-кубитный квантовый компьютер; в 1999 году — 3-кубитный, который с использованием алгоритма Гровера совершал поиск в базе данных; в 2000 году — 5-кубитный. Последнее достижение этой группы — 7-кубитный квантовый компьютер. 7 кубитов оказалось достаточно, чтобы на практике осуществить реализацию квантового алгоритма П. Шора по разложению на простые множители числа 15, были получены 3 и 5. На первый взгляд, достижения скромные, однако не стоит забывать, что N кубитов заменяет 2^N обычных битов, то есть зависимость здесь экспоненциальная — добавление одного кубита увеличивает возможности квантового компьютера в два раза. Если 7 кубитов — это всего лишь 128 классических битов, то, например, 30 кубитов — уже 10⁹ классических единиц информации, а 100 кубитов заменят 10³⁰ классических битов. 30-кубитный квантовый компьютер был бы, по оценкам, эквивалентен обычному компьютеру, выполняющему 10 триллионов операций в секунду. Такое быстродействие сопоставимо с производительностью самых мощных суперкомпьютеров, состоящих из тысяч процессоров.