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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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