книги / Физические основы нанотехнологий фотоники и оптоинформатики.-1

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

Существует три класса квантовых алгоритмов:

1)алгоритмы с квантовыми скрытыми подгруппами преобразований абелевых групп;

2)алгортмы с усилением амплитуд состояний;

3)алгоритмы для моделирования квантовых систем на компьютере. Алгоритмы классов 1 и 3 предусматривают применение дискрет-

ного фурье-преобразования. На квантовом компьютере фурье-преоб- разование выполняется за полиномиальное число (n2) операций.

Алгоритм Гровера (2-й класс), поиска в базе данных, позволяет найти решение уравнения f (x) 1,0 x N за время О( N ). Предназначен для поиска некоторого объекта в неструктурированной базе данных. Достигается квадратичное ускорение решения задачи поиска.

Алгоритм Шора (1-й класс), факторизации чисел, позволяет разложить натуральное число n на простые множители за полиномиальное от log(n) время. Он является основой для работ по квантовой криптографии и демонстрирует экспоненциальное ускорение задачи раскодирования зашифрованных сообщений стандартом RCA. В основе криптосистемы с открытым ключом RCA лежит предположение, что решение математической задачи о разложении больших чисел на простые множители (например, произведение двух 200-значных чисел друг на друга) требует экспоненциально большого числа операций и астрономического времени на классическом компьютере. Квантовый алгортм Шора дает возможность вычислить простые множители больших чисел за полиномиальное время n3 и взломать шифры RCA криптосистем.

Алгоритм Залки – Визнера позволяет моделировать унитарную эволюцию квантовой системы n частиц за почти линейное время с использованием О(n) кубит. Относится к 3-му классу.

Алгоритм Дойча – Джоза по определению типа дискретной функции от дискретного аргумента позволяет «за одно вычисление» определить, является ли функция двоичной переменной f (n) постоян-

301

ной (f1 (n) = 0, f2 (n) = 1 независимо от n) или «сбалансированной»

(f3 (0) = 0, f3 (1) = 1; f4 (0) = 1, f4 (1) = 0).

Алгоритм Саймона решает проблему черного ящика экспоненциально быстрее, чем любой классический алгоритм, включая вероятностные алгоритмы.

11.8.ЭНТРОПИЯ ФОН НЕЙМАНА –ХАРАКТЕРИСТИКА ЗАПУТАННОСТИ ДВУХКУБИТОВЫХ СИСТЕМ7

Квантовая энтропия фон Неймана в абстрактном гильбертовом пространстве n имеет вид

S Tr ln ,

где – статистический оператор (матрица плотности).

Эволюция во времени статистического оператора определяется уравнением фон Неймана

tˆ iLˆ t ˆ i Hˆ t ,ˆ i Hˆ t ˆ ˆHˆ t ,

где Hˆ t – оператор Гамильтона (гамильтониан). Для кубитов А и В энтропия имеет вид

S A Tr A log2 A ,

S B Tr B log2 B ,

где«трек» Tr Sp «шпур»–этосуммадиагональныхэлементовматрицы.

Для чистого состояния двухкубитовой системы АВ, когда приведенные матрицы плотности для обоих кубитов имеют вид

7 По материалам работы [6].

302

В запутанном состоянии двухкубитовая система АВ характеризуется приведенными матрицами плотности A и B , которые описывают для обоих кубитов смешанные состояния:

Эти смешанные состояния (см. формулы (11.5) и (11.6)) состоят из чистых состояний, описываемых векторами с вероятностями

В запутанном состоянии максимальные значения приведенных матриц A и B следующие:

( A )max 12 0A0A 12 1A1A 12 IA ,

303

( B )max 12 0B 0B 12 1B 1B 12 IB .

Таким образом, квантовая энтропия фон Неймана может служит количественной мерой запутанности двухкубитовых систем. Сравните формулу (11.7) с формулой (11.4).

Список литературы

1.Манин Ю.И. Вычислимое и невычислимое. – М.: Сов. радио, 1980. – 15 с.

2.Feynman R.P. Simulating physics with computers // International Journal of Theoretical Physics. – 1982. – Vol. 21, nо. 6. – P. 467–488.

3.Кайе Ф., Лафламм Р., Моска М. Введение в квантовые вычисления / НИЦ «Регулярная и хаотическая динамика», Ин-т комп. исследований. – М.; Ижевск, 2009. – 360 с.

4.Перри Р. Элементарное введение в квантовые вычисления: учеб. пособие. – Долгопрудный: Интеллект, 2015. – 208 с.

5.Нильсен М.А., Чанг И.Л. Квантовые вычисления и квантовая информация. – М.: Мир, 2006. – 826 с.

6.Байков Ю.А., Кузнецов В.М. Квантовая механика: учеб. пособие. – М.: БИНОМ. Лаборатория знаний, 2019. – 291 с.

304

ГЛАВА 12. КВАНТОВЫЙ КОМПЬЮТЕР

12.1.СТРУКТУРА КВАНТОВОГО КОМПЬЮТЕРА1

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

1)необходимо обеспечить высокую точность измерений 10–5–10–4 параметров управляющих кубитами сигналов;

2)внешние воздействия могут разрушить квантовую систему или внести в нее искажения.

Чтобы использовать квантовую схему для вычисления, нужно уметь вводить входные данные, делать вычисления и считывать результат, поэтому принципиальная схема любого квантового компьютера (рис. 12.1) должна включать следующие функциональные блоки:

– квантовый регистр для ввода данных;

– квантовый процессор для преобразования данных;

– устройство для считывания данных.

Квантовый регистр представляет собой совокупность некоторого числа L кубитов. До ввода информации в компьютер все кубиты кван-

тового регистра должны быть приведены в базисные состояния |0 . Эта операция называется подготовкой или инициализацией.

Рис. 12.1. Схема квантового компьютера [1]

1 По материалам работ [1].

305

Далее определенные кубиты (не все) подвергаются селективному внешнему воздействию (например, с помощью импульсов внешнего электромагнитного поля, управляемых классическим компьютером), которое изменяет значение кубитов, т.е. из состояния |0 они переходят в состояние |1 . При этом состояние всего квантового регистра перейдет в суперпозицию базисных состояний cn n, т.е. состоя-

ние квантового регистра в начальный момент времени t = 0 будет определяться функцией

2L 1

0 cn n .

n 0

Понятно, что данное состояние суперпозиции можно использовать для бинарного (двоичного) представления числа n.

В квантовом процессоре введенные данные подвергаются последовательности квантовых логических операций, которые с математи-

ческой точки зрения описываются унитарным преобразованием Uˆmn ,

действующим на состояние всего регистра.

В результате через некоторое количество тактов работы квантового процессора исходное квантовое состояние системы становится новой суперпозицией вида

Для построения любого вычисления достаточно всего двух базовых логических булевых операций. С помощью базовых квантовых операций можно имитировать работу обычных логических элементов, из которых сделаны компьютеры. Поскольку законы квантовой физики на микроскопическом уровне являются линейными и обратимыми, соответствующие квантовые логические устройства, производящие операции с квантовыми состояниями отдельных кубитов (квантовые вентили), оказываются логически и термодинамически обратимыми.

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

306

После реализации преобразований в квантовом компьютере новая функция суперпозиции представляет собой результат вычислений

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

Витоге образуется последовательность нулей и единиц, причем

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

Впамяти квантового компьютера (регистр состояния) хранятся значения L кубитов, однако квантовая система находится в состоянии, являющемся суперпозицией всех базовых 2L состояний, и изменение квантового состояния системы, производимое квантовым процессором, касается всех 2L базовых состояний одновременно. Соответственно,

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

Программируемый квантовый компьютер в смысле архитектуры фон Неймана построить нельзя в силу теоремы о запрете программирования.

Теорема о запрете программирования:

Разные унитарные операторы U0,U1,...,Un требуют ортогональных программ U0, U1,..., Un.

Комментарий: пусть программа квантового компьютера состоит из нескольких унитарных операторов. Поскольку существует бесконечное множество унитарных операторов, программный регистр должен быть бесконечного размера.

12.1.1. Идеальный квантовый компьютер

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

307

ляющих эволюцией кубитов и средствами измерения состояний куби-

тов (см. рис. 12.1).

Идеальный квантовый компьютер имеет состояния, которые все-

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

Вектор состояния квантового регистра, состоящего из n кубитов, представляет собой разложение по 2n базисных состояния регистра i1,i2,...,in , где i1,...,in 0,1 .

ai1,i2 ,...,in i1,i2,...,in . i1,..,in

Здесь ai1,...,in –проекциивектора нанаправленияортов i1,i2,...,in. Процесс вычисления на квантовом компьютере состоит в преобразовании начального вектора состояния in компьютера в конечный

вектор состояния f путем умножения начального вектора на унитарную матрицу U размерности 2n 2n :

f U 2n 2n in.

Вначальном состоянии компьютера все кубиты квантового регистра должны находиться в основном состоянии

in 01,02,...,0n ),

которое не содержит никакой информации о задаче и ее решении. Конечный вектор состояния

2n 1

f axi x x 0

содержит всю информацию о решении задачи. Измерив в базисе состояние каждого из n кубитов, в конечном состоянии получаем любое

из значений 0 x (2n 1) с вероятностями axi 2 . Квантовый алгоритм должен приводить к такому конечному состоянию f , чтобы веро-

ятность правильного решения ps as 2 1 была близка к единице,

308

лась к нулю.

Квантовый компьютер является цифровым вероятностным компьютером, так как дает решение задачи s с определенной вероятностью.

В квантовых вычислениях происходит преобразование начального вектора состояния в конечный вектор через непрерывный ряд состояний. Базисный набор состояний остается неизменным. Динамика состояния компьютера передается изменениями во времени амплитуд, которые являются аналоговыми величинами, принимающими непрерывный ряд значений в интервале 0 ax 1. По способу управления

этими величинами квантовый компьютер является аналоговым компьютером. Параметры сигналов (импульсов), управляющих кубитами, должны контролироваться с погрешностью 10–4–10–5.

Таким образом, квантовый компьютер является цифровым ве-

роятностным компьютером с аналоговым управлением, что отличает его от всех типов классических компьютеров.

Матрицу U можно разложить в упорядоченное произведение матриц второго и четвертого порядка с точностью, достаточной для вычислений:

U2n 2n Ui 2 2 U j 22 22 .

i,j

состояний пар кубитов

in a00 00 a10 10 a01 01 a11 11 f

a00 00 a10 10 a01 01 a11 11.

Числа сомножителей второго и четвертого порядка в разложении определяют число однокубитовых и двухкубитовых операций, необхо-

309

димых для реализации алгоритма. Алгоритм считается эффективным, если полное число операций является полиномиальным от числа задействованных в вычислениях кубитах компьютера. Если число операций растет экспоненциально, алгоритм считается неэффективным.

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

Соловей – Китаева [2]:

Если G – конечное множество однокубитовых элементов (поворотных) G Rl ,Rm – удовлетворяет условиям

i) l и m – непараллельные оси блоховской сферы, а

i) , 0,2 – действительные числа, так что измерения конеч-

(iii) для любого элемента g G его обратный элемент g 1 можно

точно вопроизвести конечной последовательностью элементов из G, тогда любой однокубитовый элемент можно аппроксимировать с по-

положительная константа.

Согласно этой теореме любой однокубитовый элемент можно ап-

элементов из конечного множества G.

12.2.СРАВНЕНИЕ КВАНТОВОГО КОМПЬЮТЕРА

СОПТИЧЕСКИМ КОМПЬЮТЕРОМ

Вектор состояния квантового компьютера при вычислениях содержит как цифровую информацию в квантовом регистре x, так

и аналоговую ax информацию в амплитудах квантовых состояний:

310