Итак, вход - двоичное слово, определяющее один из базисных векторов. Сам же алгоритм - предписанная последовательность элементарных операторов. Применяем эту последовательность к вектору на входе, в результате получаем некоторый вектор на выходе.
Так вот, согласно квантовой механике (КМ), пока система эволюционирует под действием наших унитарных операторов, мы не можем сказать, в каком именно классическом состоянии она находится. То есть она находится в каком- то квантовом состоянии, но измеряем-то мы, когда общаемся с системой, все равно какие-то классические значения. Как это понимается в КМ? В фазовом пространстве фиксируется некоторый базис, и вектор состояния разлагается по этому базису. Это математическая формализация процедуры измерения в КМ. То есть если мы имеем дело с системой, у которой «то ли спин влево, то ли спин вправо», и если мы все-таки посмотрим, какой спин, то мы получим одно из двух в любом случае. А вот вероятности того, что мы получим тот или другой результат, - это как раз квадраты модуля коэффициентов разложения. КМ утверждает, что точно предсказать результат измерения нельзя, но вероятности возможных результатов вычислить можно.
Вероятность возникает в процессе измерения. А пока система живет, для нас существенно, что там есть сам этот вектор.
Другими словами, существенно, что система «находится одновременно во всех возможных состояниях». Как пишут многие авторы популярных введений в KB, возникает совершенно чудовищный параллелизм вычислении: к примеру, в случае нашей системы из двух кубитов мы как бы оперируем одновременно со всеми возможными ее состояниями: 00, 01, 11, 10.
Чтобы интерпретировать ответ, надо заранее условиться, что какой-то бит - допустим, первый - это бит ответа. Пусть алгоритм проработал, у нас получился какой-то вектор, не обязательно базисный. Тогда мы можем сказать, что первый бит с некоторой вероятностью равен 1. И требование к алгоритму такое: если ответ «да», то вероятность того, что первый бит равен 1, должна быть больше двух третей. А если ответ «нет», вероятность того, что будет ноль, должна быть тоже больше двух третей.
Задачи, реализуемые на КВ.
Известно два примера нетривиальных задач, в которых KB дают радикальный выигрыш.
Первый из них - задача разложения целых чисел на простые множители и, как следствие, вычисления дискретного логарифма (ДЛ). Дальше речь пойдет именно о ДЛ.
Пусть у нас есть поле вычетов по модулю простого числа. В нем есть первообразные корни - такие вычеты, чьи степени порождают все ненулевые элементы. Если задан такой корень и задана степень, то возвести в степень можно быстро (например, сначала возводим в квадрат, потом получаем четвертую степень, и т. д.) Дискретный логарифм - это обратная задача. Дан первообразный корень и какой-то элемент поля; найти, в какую степень нужно возвести этот корень, чтобы получить данный элемент. Вот эта задача уже считается сложной. Настолько сложной, что ряд современных криптографических систем основан на том предположении, что вычислить ДЛ за приемлемое время невозможно, если модуль - достаточно большое простое число.
Так вот, для дискретного логарифма есть эффективный квантовый алгоритм. Его придумал Шор в конце 1994 года. После его статьи и начался взрыв публикаций по КВ. Независимо от него, Алексей Китаев из ИТФ им. Ландау построил квантовый алгоритм для этой и некоторых более общих задач [8]. Идеи у них были разные.
Шор использовал примерно такую идею, она существенно квантовая: рассмотрим базис в фазовом пространстве. Он состоит из классических состояний. Но в линейном пространстве много базисов. Мы можем найти некий оператор, который эффективно строит другой базис; мы можем к нему перейти, сделать там какие-то вычисления, вернуться обратно и получить нечто совершенно отличное от того, что мы имели бы в классическом базисе. Одна из возможностей использовать квантовость состоит в том, что мы строим какой-то странный базис, в нем что-то делаем, возвращаемся обратно и интерпретируем результат. Шор именно эту идею и реализовал. Причем преобразование оказалось такое, которое и в физике, и в математике имеет принципиальное значение - дискретное преобразование Фурье.
Его можно представить в виде тензорного произведения операторов, которые действуют на каждый из кубитов такой матрицей:
[pic]
Китаев придумал примерно следующее. Есть некоторая ячейка - основной регистр, где мы записываем наши данные нулями и единицами. И еще есть один управляющий кубит. Мы работаем так: у нас реализована процедура умножения на первообразный корень, на квадрат первообразного корня, и т. д. Управляющий кубит переводим в некоторое смешанное состояние, дальше строим такой оператор, который, в зависимости оттого, ноль или единица в этом управляющем кубите, либо применяет умножение к нашему основному регистру, либо не применяет. А потом кубит опять возвращаем в смешанное состояние. Оказывается, что это эффективный способ проделать некоторое измерение. То есть Китаев заметил, что одна из вещей, которые мы можем эффективно делать на квантовом компьютере, - это имитировать процесс квантового измерения. В данной задаче из результатов этих измерений эффективно извлекается ответ.
Сам процесс вычислений, происходит так: мы все время умножаем одну и ту же ячейку на некие константы, результаты измерений записываем, а потом производим своего рода обработку результатов эксперимента - уже чисто классическими вычислениями. Вся квантовая часть заключается в том, что где- то рядом с нашим регистром находится в некоем смешанном состоянии коррелированный с ним кубит, и мы его периодически наблюдаем.
Для вычисления ДЛ числа, записанного N битами, нужно потратить N 3 единиц времени. Вполне реализуемо - на КК, естественно. Но здесь надо заметить, что никто пока не доказал, что не существует столь же быстрого алгоритма для вычисления ДЛ на обычной машине.
Вторая задача предложена Гровером (L. Grover) [9]. Рассмотрим базу данных, содержащую 2N записей. Мы хотим найти ровно одну запись. Имеется некая процедура определения того, нужную запись мы взяли или нет. Записи не упорядочены. С какой скоростью мы можем решить эту задачу на обычном компьютере? В худшем случае нам придется перебрать все 2N записей - это очевидно. Оказывается, что на КК достаточно числа запросов порядка корня из числа записей – 2N/2.
Интересная задача - создание оптимальных микросхем. Пусть есть функция, которую нужно реализовать микросхемой, и эта функция задана программой, использующей полиномиально ограниченную память. Построение нужной микросхемы с минимальным числом функциональных элементов - задача PSPACE. Поэтому появление устройств, эффективно решающих PSPACE-задачи, позволило бы единообразно проектировать оптимальные по своим показателям вычислительные устройства обычного типа. Кроме того, в PSPACE попадает большинство задач «искусственного интеллекта»: машинное обучение, распознавание образов и т.д.
Так вот, точно установлено, что KB находятся где-то между обычными вероятностными вычислениями и PSPACE. Если все же окажется, что KB можно эффективно реализовать на классических вероятностных машинах, не будет смысла в физической реализации квантовых машин. Если же выяснится, что при помощи KB можно эффективно решать те или иные PSPACE-задачи, то физическая реализация КК откроет принципиально новые возможности.
Есть еще одна область применения КК, где заведомо возможен радикальный выигрыш у существующих технологий. Это моделирование самих квантовых систем.
Давайте посмотрим на такой вопрос: как можно эволюцию квантовой системы изучать на обычном компьютере? Это постоянно делается, так как это задача важна для химии, молекулярной биологии, физики и т.п. Но, за счет экспоненциального роста размерности при тензорном произведении, для моделирования десяти спинов вам нужно оперировать с тысячемерным пространством, сто спинов - это уже конец. А если вспомнить, что в молекуле белка десятки тысяч атомов, то... Там, правда, не всюду существенно именно квантовое моделирование, но в целом ясно, что есть очень серьезные препятствия для моделирования квантовых систем на классических компьютерах. Так что если создать вычислительное устройство, которое ведет себя квантовым образом, то по крайней мере один важный класс задач на нем есть смысл решать - можно моделировать реальные квантовые системы, возникающие в физике, химии, биологии.
Проблемы создания КК.
Когда начался бум вокруг квантовых вычислений, физики высказывались об этом более чем скептически. Модель квантовых вычислений не противоречит законам природы, но это еще не значит, что ее можно реализовать. К примеру, можно вспомнить создание атомного оружия и управляемый термояд.
А если говорить о КК, надо отметить одну очень серьезную проблему. Дело в том, что любая физическая реализация будет приближенной. Во-первых, мы не сможем сделать прибор, который будет давать нам произвольный вектор фазового пространства. Во-вторых, работа любого устройства подвержена всяческим случайным ошибкам. А уж в квантовой системе - пролетит какой- нибудь фотон, провзаимодействует с одним из спинов, и все поменяется. Поэтому сразу возник вопрос, можно ли, хотя бы в принципе, организовать вычисления на ненадежных квантовых элементах, чтобы результат получался со сколь угодно большой достоверностью. Такая задача для обычных компьютеров решается просто - например, за счет введения дополнительных битов.
В случае КК эта проблема гораздо глубже. То место, где возникает новое качество KB по сравнению с обычными вычислениями, - это как раз сцепленные состояния - линейные комбинации базисных векторов фазового пространства. У вас есть биты, но они не сами по себе живут в каких-то состояниях - это был бы просто вероятностный компьютер (компьютер, дающий тот или иной ответ с определенной вероятностью), - а они находятся в некоем смешанном состоянии, причем согласованно-смешанном. Из-за этого в КК нельзя, например, просто взять и скопировать один бит в другой! Обычная интуиция из теории алгоритмов здесь неприменима.
Так что проблема надежности довольно сложна, даже на уровне чистой теории. Те люди, которые активно занимаются KB, активно ее решали и добились успеха: доказано, что, как и в классике, можно делать вычисления на элементах с заданной надежностью сколь угодно точно. Это реализовано с помощью некоего аналога кодов, исправляющих ошибки.
Что касается технической стороны появляются сообщения, что создаются реальные квантовые системы с небольшим числом битов - с двумя, скажем. Экспериментальные, в железе, так сказать.
Страницы: 1, 2, 3
