Реферат: Квантовые компьютеры

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

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

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

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

Его можно представить в виде тензорного произведения опера­торов, которые действуют на каж­дый из кубитов такой матрицей:

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

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

Для вы­числения ДЛ числа, записанного N битами, нужно потратить N ³ еди­ниц времени. Вполне реализуе­мо - на КК, естественно. Но здесь надо заметить, что никто пока не доказал, что не существует столь же быстрого алгоритма для вы­числения ДЛ на обычной машине.

Вторая задача предложена Гровером (L. Grover) [9].Рассмотрим базу дан­ных, содержащую 2 ^N записей. Мы хотим найти ровно одну запись. Имеется некая процедура опреде­ления того, нужную запись мы взяли или нет. Записи не упоря­дочены. С какой скоростью мы можем решить эту задачу на обыч­ном компьютере? В худшем слу­чае нам придется перебрать все 2 ^N записей - это очевидно. Оказывается, что на КК достаточно числа запросов по­рядка корня из числа записей – 2 ^N/2 .

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

Так вот, точно установлено, что KB находятся где-то между обыч­ными вероятностными вычисле­ниями и PSPACE. Если все же ока­жется, что KB можно эффективно реализовать на классических ве­роятностных машинах, не будет смысла в физической реализации квантовых машин. Если же выяс­нится, что при помощи KB можно эффективно решать те или иные PSPACE-задачи, то физическая реализация КК откроет принци­пиально новые возможности.

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

Давайте посмотрим на такой вопрос: как можно эволюцию квантовой системы изучать на обычном компьютере? Это посто­янно делается, так как это задача важна для химии, молеку­лярной биологии, физики и т.п. Но, за счет эк­споненциального роста размер­ности при тензорном произведе­нии, для моделирования десяти спинов вам нужно оперировать с тысячемерным пространством, сто спинов - это уже конец. А если вспомнить, что в молекуле белка десятки тысяч атомов, то... Там, правда, не всюду существенно именно квантовое моделирование, но в целом ясно, что есть очень серьезные препятствия для моде­лирования квантовых систем на классических компьютерах. Так что если создать вычислительное устройство, которое ведет себя квантовым образом, то по край­ней мере один важный класс за­дач на нем есть смысл решать - можно моделировать реальные квантовые системы, возникающие в физике, химии, биологии.

Проблемы создания КК.

Когда начался бум вокруг квантовых вычислений, физики высказывались об этом бо­лее чем скептически. Модель кван­товых вычислений не противоре­чит законам природы, но это еще не значит, что ее можно реализовать. К примеру, можно вспомнить создание атом­ного оружия и управляемый термояд.

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

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

Так что проблема надежности довольно сложна, даже на уровне чистой теории. Те люди, которые активно занимаются KB, активно ее решали и добились успеха: доказано, что, как и в классике, можно делать вычисления на элементах с за­данной надежностью сколь угод­но точно. Это реализовано с по­мощью некоего аналога кодов, ис­правляющих ошибки.

Что касается технической сто­роны появляются сообщения, что созда­ются реальные квантовые систе­мы с небольшим числом битов - с двумя, скажем. Эксперименталь­ные, в железе, так сказать.

Так что эксперименты есть, но пока очень далекие от реальнос­ти. Два бита - это и для класси­ческого и для квантового компь­ютера слишком мало! Чтобы мо­делировать молекулу белка, нуж­но порядка ста тысяч кубитов. Для ДЛ, чтобы вскрывать шифры, достаточно примерно тысячи кубитов.

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

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

Физической системе, реализующей квантовый компьютер, можно предъявить пять требований:

1. Система должна состоять из точно известного числа частиц.

2. Должна быть возможность привести систему в точно известное начальное состояние.

3. Степень изоляции от внешней среды должна быть очень высока.

4. Надо уметь менять состояние системы согласно заданной последовательности унитарных преобразований ее фазового пространства.

5. Необходимо иметь возможность выполнять «сильные измерения» состояния системы (то есть такие, которые переводят ее в одно из чистых состояний).

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

Физические основы организации КК.

Итак, что же это за тайное оружие такое - КК? Остроумная идея за­ключается в использовании для хра­нения, передачи и обработки ин­формации существенно квантовых свойств вещества. В основном такие свойства проявляют объекты мик­ромира: элементарные частицы, атомы, молекулы и небольшие сгу­стки молекул, так называемые кла­стеры. (Хотя, конечно, и в жизни макромира квантовая механика иг­рает важную роль. В частности, только с ее помощью можно объяснить та­кое явление, как ферромагнетизм.) Одним из квантовых свойств веще­ства является то, что некоторые ве­личины при измерении (наблюде­нии) могут принимать значения лишь из заранее определенного дискрет­ного набора. Такой величиной, на­пример, является проекция собст­венного момента импульса, или, ина­че говоря, спина элементарной час­тицы, на любую заданную ось. На­пример, у электрона возможно только два значения проекции: +1/2 или –1/2 . Таким образом, количество информации, необходимое для со­общения о проекции, равно одному биту. Записав в классическую одно­битную ячейку памяти определен­ное значение, мы именно его оттуда и прочтем, если не произойдет ка­кой-нибудь ошибки.