ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 6, с. 65-79
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^ МЕТОДЫ
УДК 510.56, 510.647
ВЫЧИСЛЕНИЯ НА КВАНТОВЫХ КОМПЬЮТЕРАХ НА ОСНОВЕ НЕКЛАССИЧЕСКОЙ ТЕОРИИ ВЕРОЯТНОСТЕЙ
© 2014 г. Н. Н. Попов, В. И. Цурков
Москва, ВЦ РАН Поступила в редакцию 01.07.14 г., после доработки 21.07.14 г.
Рассматриваются основные понятия теории квантовых вероятностей. Изучаются некоторые свойства априорных и апостериорных квантовых вероятностей. Анализируются понятия регулярных и неразрушающих процедур измерений. Исследуются эффекты, связанные с совместимостью и некоррелированностью квантовых процедур. Дается определение марковских последовательностей квантовых процедур для квантовых систем с конечным или счетным числом состояний. Показывается, что процесс вычислений на и-кубитном квантовом компьютере представляет собой операции, подчиняющиеся законам квантовой теории вероятности.
Б01: 10.7868/80002338814060109
Введение. Как известно, квантовый компьютер представляет собой вычислительное устройство, работающее на принципах квантовой механики. В квантовых компьютерах для вычислений применяются не обычные алгоритмы, а процессы квантовой природы, так называемые квантовые алгоритмы, использующие квантовомеханические эффекты, такие как квантовый параллелизм и квантовая суперпозиция. Принципиальное отличие классического компьютера от квантового состоит в том, что если классический процессор в каждый момент времени может находиться ровно в одном из возможных состояний уь ..., уи, то квантовый процессор в каждый момент одновременно находится во всех этих базисных состояниях, причем в каждом состоянии у] со своей комплексной амплитудой вероятности Х]. Это квантовое состояние называется "квантовой суперпозицией" данных классических состояний и обозначается как
п
у = х ^А,
1=1
причем вероятность обнаружить квантовый процессор в классическом состоянии у. вычисляется по формуле р. = \Х]\2.
Квантовое состояние у может изменяться во времени двумя принципиально различными способами, возникающими в результате применения:
1) унитарной квантовой операции,
2) операции измерения.
Унитарная квантовая операция осуществляет процедуру квантового вычисления, т.е. процедуру унитарного преобразования вектора состояния квантового регистра. Квантовый регистр состояний из и двухуровневых квантовых элементов, называемых кубитами, имеет 2и линейно независимых состояний, представляющих базис 2и-мерного гильбертова пространства. Операция в квантовых вычислениях соответствует унитарному повороту вектора состояния регистра в гильбертовом пространстве, т.е. в квантовом 2и-кубитном регистре одновременно преобразуются 2и классических состояний.
Теоретически получается, что квантовый компьютер может работать для некоторых алгоритмов существенно быстрее классического. Измерение, проводимое над конечным состоянием квантового регистра, представляет собой конечный результат процедуры квантовых вычислений. Математически процедура измерения осуществляется за счет действия некоторого самосопряженного оператора, соответствующего физической наблюдаемой, на квантовое состояние. После применения процедуры измерения квантовый регистр переходит в новое состояние.
5
65
Итак, весь процесс вычислений на квантовом компьютере сводится к выполнению поочередно двух действий: операции унитарного преобразования вектора состояния квантового регистра и операции измерения. Результат измерения представляется в виде некоторого значения случайной величины. Для повышения достоверности получаемого результата можно проводить дополнительные операции измерений, однако при этом нужно учитывать изменение состояния квантового регистра после очередной операции измерения.
Из вышеизложенного следует, что работа квантового компьютера описывается некоторым стохастическим процессом, который не может быть сведен к уже известным процессам, исследуемым в рамках классической теории вероятностей.
В теории квантовых компьютеров можно выделить три важных направления исследований:
1) построение математического аппарата, описывающего процесс работы квантового компьютера;
2) разработка квантовых алгоритмов вычислений [1—4];
3) разработка языков программирования для квантовых компьютеров [5].
Следует отметить еще одно наиболее важное направление — это техническая реализация квантовых компьютеров. Практические результаты, наметившиеся в этом направлении за последние годы, вселяют определенные надежды на реальное развитие этой области [6—8].
В данной статье представленные в [9] основы математического аппарата теории квантовых вероятностей демонстрируются в работе квантовых компьютеров.
1. Аксиомы теории квантовых вероятностей. Квантовую систему формально можно охарактеризовать, задав состояние S, в котором система приготовлена непосредственно перед началом измерения, процедуру измерения SE, пространство элементарных событий Q, состоящее из всех теоретически допустимых событий, которые, в принципе, могут наблюдаться при исследовании квантовой системы, и множество событий F, реально наблюдаемых в результате измерений.
Пусть Q. — множество элементов ю, которые будем называть элементарными событиями, F— множество подмножеств из Q. Элементы множества F будем называть событиями, а Q. — пространством элементарных событий. Процедура измерения SE полностью характеризуется некоторым отображением E, определенным на множестве F. Каждому событию A е F соответствует пара элементов E*(A), E(A), где E*(A) — сопряженный элемент к E(A). Совокупность всевозможных таких элементов обозначим как {E, F}. Построим из элементов совокупности (E, F) векторное пространство р над полем комплексных чисел С, наделенное операцией умножения и сопряжения *. Другими словами, для любых а, ß е C и N, K е р имеем aN + ßK е р, N • K е р и N* • K* е р. Векторное пространство р наделено структурой С*-алгебры.
Самосопряженные элементы С*-алгебры р будем называть наблюдаемыми. Элемент E*(A), E(A) называется наблюдаемой, соответствующей событию A е F, в условиях проведения процедуры измерения SE. Теория квантовых вероятностей имеет дело с семейством наблюдаемых, соответствующих событиям.
Математическая структура системы множеств F и пространства р определяется следующими постулатами:
I. Множество событий F — полуалгебра множеств.
Это значит, что 0, Q. е F. Если A, B е F, то A n B е F. Если A, B е Fи A с B, то найдется конечное число непересекающихся с A и между собой множеств A1, ..., An е F, таких, что A + A1 + ... + + A„ = B.
II. Векторное пространство р есть С*-алгебра с единицей.
Процедура измерения SE, задаваемая отображением E : F ^ р, удовлетворяет следующему постулату:
III. 1) E(Q) = I, где I — единица в С*-алгебре р,
2) E(A) + E(B) = E(A + B) для любых непересекающихся A, B е F, таких, что A + B е F.
Условие 1) можно назвать свойством полноты, а условие 2) — свойством аддитивности процедуры измерения.
Помимо алгебры наблюдаемых квантовая система характеризуется заданием состояния.
На С*-алгебре р всегда можно ввести линейный положительный функционал р, такой, что:
IV. 1) р(1) = 1,
2) p(E*(A)E(A)) < 1 для любого A е F.
В этом случае р называется кантовым состоянием, а неотрицательное число p(E*(A)E(A)) — квантовой вероятностью события A в состоянии р при проведении процедуры измерения SE и
обозначается как РГр (А). Квантовая вероятность есть среднее значение наблюдаемой Е*(А)Е(А) в состоянии р.
Совокупность объектов (О, Е, Е, р), удовлетворяющих постулатам Г—ГУ, будем называть полем. Квантовая система, в частности квантовый компьютер, считается определенной, если задано поле (О, Е, Е, р). Естественно поставить вопрос о существовании таких объектов и о согласованности системы постулатов Г—ГУ. Введем следующие понятия.
Представление С*-алгебры р — это пара (Н, п), состоящая из комплексного гильбертова пространства Ни отображения п алгебры р в операторную алгебру Z(И), действующую в гильбертовом пространстве Н. Вектор у е Нназывается циклическим для п( р), если {^у : N е п( р)} плотно в Н.
Определение 1. Циклическим представлением С*-алгебры р называют тройку (Н, п, у), где (Н, п) — представление р, а у — вектор из Н, циклический для п в Н.
Те о р е м а 1 (о представлении). Пусть задано поле (О, Е, Е, р) и пусть р есть С*-алгебра, порождаемая парой (Е, Е). Тогда существует циклическое представление (Нр, пр, ур) алгебры р, ассоциированное с р, где Нр — гильбертово пространство, пр — отображение алгебры р в алгебру ограниченных операторов, действующих в Нр, и ур — циклический вектор для пр в Нр, такие, что {О, Е, пр(Е), } удовлетворяет постулатам Г—ГУ, где ру — векторное состояние, порождаемое циклическим вектором ур.
Для любого А е Еимеет место
РГр (А) = <у р,п*( Е* (А ))пр ( Е (А ))ур),
где (, ) — скалярное произведение в Нр. Такое представление определено единственным образом с точностью до унитарной эквивалентности. Доказательство строится по той же схеме, что приведена в [10].
Если:
1) С*-алгебра р реализована в терминах ограниченных операторов в гильбертовом пространстве Н;
2) Е — борелева алгебра В на вещественной оси Я;
3) Е — ортогональная проекторнозначная мера на (Я, В), действующая в Н;
4) р — нормальное состояние на р, находящиеся во взаимно однозначном соответствии с
нормализованным вектором ур е Н, так что (А) = (ур, Е(А)ур), где Е(А) е р, то предложенная система постулатов теории квантовых вероятностей сводится к стандартной формулировке квантовой механики, если не учитывать постулат динамической эволюции.
Проиллюстрируем, как работают введенные понятия на примере двухкубитного квантового регистра.
Пример 1. Пространство элементарных событий О двухкубитного квантового регистра состоит из следующих множеств:
А00 — первый и второй кубиты находятся в состоянии 0;
А01 — первый кубит находится в состоянии 0, а второй — в состоянии 1;
А10 — первый кубит находится в состоянии 1, а второй — в состоянии 0;
А11 — первый и второй кубиты находятся в состоянии 1.
Пусть Е — булева алгебра на множестве элементарных событий О. Это значит, что Ау и Ак1 е Е для любых I,у, к, I =
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.