Современные информационные технологии /1. Компьютерная инженерия

К.т.н., доц. Аждер Т.Б., к.т.н., доц. Зеленко Г.В., к.т.н., проф. Рощин А.В.

Московский технологический университет, Россия

Квантовые компьютеры – задачи квантовых вычислений

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

Прототипы квантовых компьютеров существуют уже сегодня. Правда, пока что экспериментально удается собирать лишь небольшие регистры, состоящие всего из нескольких квантовых битов. Так, недавно группа, возглавляемая американским физиком И. Чангом (IBM), объявила о сборке 5-битового квантового компьютера. Несомненно, это большой успех. К сожалению, существующие квантовые системы еще не способны обеспечить надежные вычисления, так как они либо недостаточно управляемы, либо очень подвержены влиянию шумов. Однако физических запретов на построение эффективного квантового компьютера нет, необходимо лишь преодолеть технологические трудности. Таким образом, исследования активно ведутся и можно предположить, что в самом недалеком будущем - лет через десять - эффективный квантовый компьютер будет создан.

Известно два примера задач, в которых квантовые вычисления дают радикальный выигрыш.

Первый из них - задача разложения целых чисел на простые множители и, как следствие, вычисления дискретного логарифма.

Пусть у нас есть поле вычетов по модулю простого числа. В нем есть первообразные корни - такие вычеты, чьи степени порождают все ненулевые элементы. Если задан такой корень и задана степень, то возвести в степень можно быстро (например, сначала возводим в квадрат, потом получаем четвертую степень, и т. д.) Дискретный логарифм - это обратная задача. Дан первообразный корень и какой-то элемент поля; найти, в какую степень нужно возвести этот корень, чтобы получить данный элемент. Вот эта задача уже считается сложной. Настолько сложной, что ряд современных криптографических систем основан на том предположении, что вычислить дискретный логарифм за приемлемое время невозможно, если модуль - достаточно большое простое число.

Так вот, для дискретного логарифма есть эффективный квантовый алгоритм. Его придумал Шор в конце 1994 года. После его статьи и начался взрыв публикаций по квантовым вычислениям. Независимо от него, Алексей Китаев из ИТФ им. Ландау построил квантовый алгоритм для этой и некоторых более общих задач. Идеи у них были разные.

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

Китаев придумал примерно следующее. Есть некоторая ячейка - основной регистр, где мы записываем наши данные нулями и единицами. И еще есть один управляющий кубит. Мы работаем так: у нас реализована процедура умножения на первообразный корень, на квадрат первообразного корня, и т. д. Управляющий кубит переводим в некоторое смешанное состояние, дальше строим такой оператор, который, в зависимости оттого, нуль или единица в этом управляющем кубите, либо применяет умножение к нашему основному регистру, либо не применяет. А потом кубит опять возвращаем в смешанное состояние. Оказывается, что это эффективный способ проделать некоторое измерение. То есть Китаев заметил, что одна из вещей, которые мы можем эффективно делать на квантовом компьютере, - это имитировать процесс квантового измерения. В данной задаче из результатов этих измерений эффективно извлекается ответ.

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

Литература:

1. Квантовый компьютер, перспективы практической реализации. Автор Доронин С.И. - [электронный ресурс] способ доступ к URL: http://physmag.h1.ru/theory.files/kk.html.

2. Квантовый компьютер. - [электронный ресурс]. Способ доступ к URL: http://allrefs.ru/prosmotr/5820-0.htm.