Документ взят из кэша поисковой машины. Адрес оригинального документа : http://sqi.cs.msu.su/store/storage/th25kzj_quantum_computer.pdf Дата изменения: Tue Nov 25 17:44:03 2014 Дата индексирования: Sun Apr 10 22:25:06 2016 Кодировка: Windows-1251

Квантовая информатика и квантовый компьютер
Учебное пособие
Д.А.Кронберг, Ю.И.Ожигов, А.Ю.Чернявский МГУ имени М.В.Ломоносова, факультет ВМК

1


Пособие предназначено для самостоятельной работы студентов, слушающих курс ?Квантовые вычисления? или любой другой курс по основам квантовой информатики. Проработка данного пособия означает освоение основами квантовой информатики, что дает возможность дальнейшей специализации в этом направлении, включая поступление в аспирантуру. Работа с данным пособием заключается в самостоятельном решении предлагаемых в конце задач с использованием сведений, изложенных в регулярном курсе. В случае необходимости в качестве источника теоретических сведений можно вместо курса можно также использовать пособие [65]. Все теоретические сведения, формально необходимые для решения задач, кратко задач излагаются можно, в в данном пособии. При решении случае необходимости, пользоваться

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

2


Оглавление
1 Квантовые процессы 4

1.1

Основные 1.1.1 1.1.2

положения

одночастичной 5 12 19 22 26 29 33
38

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

1.2

Унитарная динамика и измерения . . . . . . 1.2.1 компьютера . . . . . . . . . . . . . . .

1.3

Роль запутанности . . . . . . . . . . . . . . . 1.3.1 Моделирование квантовых систем . .

2

Задачи

2.1

Физические компьютеров

реализации

квантовых 56
59

..................

Литература

3


Глава 1 Квантовые процессы
В данном с разделе с описывается точки часть формализм так квантовой студент, сможет Обычно физики кубитовой любую по из ее зрения, на что

знакомый переписать в обозначения

основами физике

квантовой этом

теории, языке.

литературе

используется

традиционные волновую

теории

функций,

например,

функцию записывают как

(x)

, что вызывает коллизию

со значением волновой функции в конкретной точке

x

,и

потому для него используется интегральное представление

(y )x (y ) dy
коллизий не

. Эти традиционные обозначения удобны проблемы для человека. Однако

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

4


1.1

Основные одночастичной механики

положения квантовой

Главный постулат квантовой механики состоит в том, что вся динамика любой системы определяется ее волновой функцией, которая является комплексной функцией от координат все частиц, составляющих эту систему:

(t, r1 , r2 , . . . , rn ).
Здесь

rj

есть координаты частицы

j

(имеются в виду не

только пространственные координаты частиц, но и их спиновые координаты). Эта волновая функция должна рассматриваться как вектор в гильбертовом пространстве состояний функции

n

частичной

системы.

Значения

этой

называются при

амплитудами, для

соответствующими

пребыванию частицы в данный момент времени состоянии, частица котором каждого

t в таком j = 1, 2, . . . , n
трактовка

j

имеет

координаты

rj

.

Такая

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

,

должно

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

физике (не считая волновую физику, где интерференция проявляется вернемся). Интерференцию амплитуд проще всего коллективный эффект,

5


продемонстрировать,

применяя

матрицы.

Представим

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



в виде некоего состояние в

столбца координат этого вектора в данном базисе. Тогда что следующий момент времени к состоянию в момент

t + t можно найти, применив времени t некий линейный оператор

U

, называемый оператором унитарной эволюции (дальше

мы увидим, что он должен быть не только линейным, но и унитарным). Этот факт можно выразить на языке матричного умножения так:

u1,1 u2,1 ... un,1

u1,2 u2,2 ... un,2

. . . .

. . . .

. . . .

u1,n u2,n ... un,n

1 (t) 2 (t) ... n (t)

=

1 (t + t) 2 (t + t) ... n (t + t)
(1.1)

То есть любая амлитуда формуле

j (t + t)
n

может быть найдена по

j (t + t) =
i=1

i (t)uj,i .

(1.2)

Формула (1.2) означает, что для нахождения амплитуды в некоторой точке в следующий момент времени надо просуммировать предыдущий все амплитуды во всех точках их в на момент, предварительно умножив

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

вносят

этой

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

6


А теперь рассмотрим два последовательных перехода, которые осуществляются с помощью того же оператора эволюции

U

: от момента

нас получится: мы получим

t до момента t + 2 t. Тогда у (t + 2 t) = U 2 (t). Выписав подробнее, j (t + 2 t) = i,k i (t)ui,k uk,j . Это означает,

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

получается умножением элементов матрицы эволюции

U

,

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

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

разницей,

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

x

соответствует оператор умножения на эту координату:

x : f (x) - xf (x), вектору r = (x, y , z ) - оператор ? r : f (x, y , z ) - (xf (x, y , z ), y f (x, y , z ), z f (x, y , z )), ? импульсу px вдоль координатной оси x - оператор
7


импульса

p

x

p = h( ? i где V -

p2 , энергии - оператор энергии + V (x), x y 2m потенциальная энергия частицы. Оператор энергии
правила перехода к векторым модуля 2 2 величинам, координаты z 2 )f (x, y , z ), 2 скалярный взятия

= , z ),

h , полному импульсу i x

p ?

- оператор

называется гамильтонианом. При этом мы принимаем обычные например оператор 2 действует как |r | : (то есть квадрат квадрата

оператор квадрата импульса - как трактуется квадрат), моменту импульса координаты которого

f (x, y , z ) - (x + y + p2 : f - -h f
нами по как

rЧp ? ?

- оператор момента, правилу

получаются

векторного произведения из координат его сомножителей - операторов, и т.д. Преобразование называется функции: Фурье от волновой функции волновой импульсным представлением
ipx h

(p) =
R

e

-

(x)dx,

(1.3)

где обратный оператор выглядит так:

(x) =

1 2 h
R

e

ipx h

(p)dp.

Полный переход к импульсному представлению и обратно в трехмерном пространстве имеет вид

(p)

=
R
3

e

-

ipћR h

(R)d3 R, e
ipћR h

(R) =
При этом если можно по

1 (2 h)3 R

(p)d3 p,
зависит от 3

3

волновая каждой из

функция к ее

переменных, от других,

переходить можно

импульсному независимоо функцию

представлению

координат

например,

рассмотреть

8


вида

(x, py , z )

,

или

(px , y , pz ),

и

т.д.

Подчеркнем,

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

exp(ipR).

Мы могли бы выбрать какой-

либо иной базис, например, соответствующий собственным векторам эрмитова оператора суммы координата, и завести

R+p

импульс плюс представление

соответствующее

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

обнаружения частицы в точке

x

: (1.4) базиса

p(x) = |(x)|2
Это правило инвариантно в том относительно смысле, что

пространства квадрат функции.

состояний

плотность

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

p

есть

волновой

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

9

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

1

имеет смысл только в рамках аппарата, лежащего в в

математического трактовку части

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

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

рассматриваемой системы, причем не существует точного определения изолированности. В случае изолированной системы динамика описывается уравнением Шредингера, в случае контакта функции. с окружением в из функций значения есть измерениями базисе этого случайная волновой величина, Борна. Измерение данном векторов

пространства

волновых

принимающая

базиса с плотностью вероятности, задаваемой правилом Окружение всегда считается классической системой, подчиняющейся законам классической физики, и измерение системы дает вероятностное распределение ее состояний, подчиняющееся правилу Борна. Уравнение

1 Другим постулатом того же статуса является представление о
тождественности элементарных частиц одного типа.

10


Шредингера имеет вид

ih
где

= H t
частицы (или

(1.5)

H

есть

оператор

энергии

системы

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

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

i (x, t) = exp - H t (x, 0) h
Экспонента от оператора определяется

(1.6)

как

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

возможностей квантовой

выбора

базисов),

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

изложенным в этом параграфе.

11


1.1.1
А от

Кубитовый формализм
займемся функции называется важным к моментом к перехода Эта

сейчас волновой

конечному

вектору.

процедура

переходом

кубитовому

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

наличием

возможного

конфигурационном что

пространстве.

предположим,

конфигурационное

пространство

является делимым до бесконечности, а в нем существует наименьшая ненулевая длина что вместо непрерывной ее рассматривать

d > 0,

то у нас получится, функции надо которое

волновой

дискретное

приближение,

на самом деле будет уже не приближением, а точным выражением, то есть приближением надо будет считать как раз непрерывный такой вариант волновой функции. Существование дискретизации пространства

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

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

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

d=
а

(dx , dt )

может

и

не

быть

абсолютной

величиной,

зависеть от рассматриваемого процесса. Оно фактически

12

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

R

(для

одномерной

частицы

это

вещественные числа, но в данном случае структура не очень важна). Разобъем

R

нам

R

на конечное число сегментов

D1 , D2 , . . . , D
ступенчатой сегменте

m и рассмотрим приближение функции
функцией некоторое


на

|

,

которая

принимает . Пусть

Dj

значение



j

C

обозначает характеристическую функцию сегмента Тогда мы можем записать формальное равенство

|j Dj

.

m

| =
j =1
Рассмотрим функциями линейное

j |j
пространство,

(1.7)

порожденное произведение

|j

.

Если

ввести

скалярное

функций по стандартному правилу у нас получится, что сделать, (1.7) фиксировав являться

(g , f ) =

? f (x)g (x)dx

,

|j
j

образуют ортогональный базис и подбирая нужные вектора

этого пространства. Если мы нормируем их (это можно

D

j ),

то по

этот базис будет ортонормированным. Тогда равенство будет разложением

|

ортонормированному базису, состоящему из векторов

|j

.

Представление волновой функции в виде (1.7) является корректным, в отличие от двусмысленного выражения

(x), поскольку в последнем выражении переменная x является свободной, и потому неясно, что выражает запись (x) - функцию или ее значение в конкретной
13


точке

x

. Подобные тонкости не важны в классической так как при аналитических вычислениях

математике,

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

|a
его

понимать координат

вектора

a

в

конечномерном

гильбертовом действие где под

пространстве

состояний заранее

выбранном оператора

линейного

A A

на в

выразится как результат матричного умножения

A|a

,

A

понимается также полученная

матрица из

базисе. вектор и

Договоримся строка,

считать,

что

a|

есть

|a

транспонированем

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

a

b

запишется как либо матрица

вдояко: если

как

a|b . Запись a|A|b можно толковать a|(A|b ), либо как ( a|A )|b . Но A самосопряженная, то есть A = A ,
исчезает, называют и мы можем использовать вида без скобок. Самосопряженные Матрицы унитарными.

двойственность выписанное матрицы еще где

выражение

эрмитовыми.

exp(iH )

,

H

-

эрмитова,

называются

Приведением к диагональному виду легко доказывается,

U

что матрица U унитарна тогда и только тогда, когда -1 = U , или, что то же самое, когда матрица U Можно определить измерение состояния

сохраняет все расстояния в гильбертовом пространстве.

|

в

14


ортонормированном случайную величину, вероятностями случайный волновой причем

базисе

|1 , |2 , . . . , |N

как

| j |

принимающую значения |j с 2 | . Это есть переформулировка который при этом называется процессе коллапсом происходит

борновского правила. Таким образом, измерение задает процесс, функции: каждого

переход от состояния для

| к j=

одному из состояний

|j

,

1, 2, . . . , N

нам

известна

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

|

еще и некоторые другие (так называемые и при

состояние аппарата аппарата

скрытые параметры) неизменно приводит к отказу от использования отсутствии стандартного вообще, такая альтернативного квантовая попытка всей

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

A,

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

A.

Если

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

z

). Если могут

собственных не

15

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

Dj x

как последовательные будет иметь вид

отрезки равной длины, то с точностью до коэффициента матрица оператора координаты



1 0 0 ...

0 2 0 ...

... 0 ... 0 3 ... ... ...

(1.8)

в то время как матрица оператора импульса для той же координатной оси имеет вид

DF T DF T
для

-h2 12 /2m 0 0 ...

0 -h2 22 /2m 0 ...

... ... -h2 32 /2m ...

0 0 ... ...

DF T

-1

(1.9) где здесь обозначает примера. или Это дискретное преобразование Фурье (см. Приложение координаты определений импульса первое

QF T
в

). Числа

1, 2, . . .

взяты

просто

числовые

значения из

двоичном а для

представлении. вытекает доказательства

Действительно,

утверждение

непосредственно,

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

исходного,

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

импульса вдоль другой оси, например,

x p

и

оператор

y , то у таких

16

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

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

Борна. Рассмотрим, для примера, двумерное гильбертово пространство, в котором измеряется ?координата?, а затем ?импульс? частицы. Я заключаю название физических величин что из в кавычки для не того, чтобы подчеркнуть, или два рассматриваются того, что частица настоящая координата только

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

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

|1 , |2

, а преобразование Фурье в двумерном

случае имеет матрицу Адамара (с точностью до фазового

2 1/2 1/ 1/ 2 -1/ 2 1
или

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

2,

будет равен

1/2. |0

Импульс частицы или

при условии, что эта частица способна занимать только два пространственных положения: что эта частица либо совершает

|1

, означает, из одного

прыжок

положения в другое, либо стоит на месте. Физическая

17

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

дает

нам

верное

понимание Как и не

этого видим,

понятия можно к

необычной понятию

ситуации. импульса пусть

частицы

совершенно

определенное

понимание,

сводящееся

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

2

Кубитовый чем Он как

формализм,

мы

надежен, функций. операторы таким приемы. чем содержит

стандартный обладает так явно как

формализм позволяет эрмитовы более так

большими

выразительными

возможностями, образом,

конкретные техника

использовать

алгебраические требовательна, как она явно

Кубитовая некое зерно Любой

традиционная

аналитическая, разрешения изъян

конфигурационного который

пространства.

формализма,

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

является объектом;

манипуляция

математическим

2 Я предлагая читателю рассмотреть возможности применения
для такой задачи эвристику стандартного математического анализа (то есть того, что принято понимать под физической интуицией), когда скорость рассматривается как предел

s/t

, и т.д.

18


все

то,

что

понимают должно

под

физической к такой некой

интуицией, физической

обязательно

сводиться

манипуляции.

Самостоятельное

существование

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

частицы начала в

качестве масс.

системы

координат

Однако

применима.

Трудности

начинаются

формально означает

одночастичных

задачах,

содержащих частицы с

измерения, см. Пример 2 из 2.4.2. Физически измерение взаимодейтсвие рассматриваемой окружением, состоящим из очень болшого числа частиц, и потому проявляющего классические свойства. То есть фактически, задача об измерении Это не является в виде уже так одночастичной задачей. проявляется

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

1.1.2

Тензорные произведения

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

возможность подхода:

которое

невозможно

строго

стандартного

существование

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

19

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

фундаментальное состояний

квантовой теории от классической. Пусть пространства частиц квантовых Тогда соответственно. данных квантовые

H1 , H2 , . . . , Hn частиц 1, 2, . . . , n
ансамбля произведение

состояние

составляют

тензорное

H = H1 H2 . . . jj j Пусть b1 , b2 , . . . , bk j Hj , j = 1, 2, . . . , n
вида

Hn

, которое мы сейчас определим.

есть некоторый базис пространства . Тогда базисом пространства

H

, по

определению, будет набор всех формальных произведений

b
где и знак оба Например, если

1 i1

b
у

2 i2

...
только

bnn , i
часто два опускается. кубитов пространства,

тензорного представляют

произведения нас собой

состояния Часто в

первого и второго, то в их произведении базис будет таким:

|0 |0 , |0 |1 , |1 |0 , |1 |1 . обозначениях | также опускается (r1 , r2 , . . . , rn ) H = H1 H2 . . .
вида

дираковских

и пишут просто

|00

и

т.д. Теперь мы можем отождествить волновую функцию с вектором в тензорном пространстве где всевозможные значения

принадлежат базису

|j |1

Hn H1 , и Hj j = 1, 2, . . . , n, |2 . . . |n

r

1

т.д. Если у нас есть состояния то их тензорное произведение определяется так. Надо

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

20


коммутативности, то есть дистрибутивен по отношению к сложению, и допускает вынесение числового множителя. Такое произведение состояний принадлежит тензорному произведению пространств. j Если A : Hj - Hj мы 1 есть линейные операторы, произведение определим

A

определим 2

A

...

A

их n

тензорное так.

A

=
этот

Сначала

оператор естественным образом на базисных векторах

H : A(b = A1 (b11 ) i
все пространство Не всякий в произведения Например,

1 i1

b

2 i2

... ...

bnn ) = i An (bnn ), i

A2 (b22 ) i
. из из

а затем распространим этот оператор по линейности на

H

вектор векторов случае

H

имеет

вид

тензорного пространств.

отдельных

двух

кубитов

вектор

|00 + |11

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

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

представляли частицу как точечную, то есть классически. Таким образом, запутанность есть удивительное, чисто квантовое приводит явление. к В главе 6 мы увидим, что оно макроскопическим следствиям. Таким

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

(r1 , . . . , rn ),

тензорное

произведение

21


трактовать как обычное произведение

1 (r1 )2 (r2 ) . . . n (rn )
определения,

.

Смысл нами состоит

математического в том, что оно

данного

действует в кубитовом формализме, который полностью адекватен квантовой теории, поскольку включает в себя разрешения: мы используем j это зерно для выбора базиса b1 , . . . для каждой частицы. 1 Например, мы можем считать, что b1 означает нахождение 1 первой частицы в точке 1, b2 - нахождение ее в точке 2 и т.д. При этом зерна для разных частиц могут, вообще говоря, иметь разный размер. Также и частица сама по себе может быть целым ансамблем, состоящим из более мелких частиц, так что ее пространство тоже получается как тензорное произведение, и т.д. зерно пространственного

1.2

Унитарная измерения

динамика

и

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

унитарная

динамика

особенность любого

фундаментальна, к вычислениям

видимому, должна быть в той или иной форме сохранена нового базе квантовой теории. Рассмотрим эти два вида динамики отдельно.
Унитарная динамика. Считается, что возможные

состояния

|

квантовой

системы

образуют

некое

гильбертово пространство состояний к моменту

H

, так что изменение

любого состояния во времени при переходе от момента

t0

t1

задается унитарным оператором

Ut0

,t1

: H - H
22

(1.10)


Можно еще детализировать это утверждение, сказав, что i этот оператор имеет вид U = exp(- H (t1 - t0 )), где h H называется гамильтонианом данной системы, и равен оператору ее полной энергии (зависящей от самой этой системы и от внешних потенциалов), что является просто переформулировкой того обстоятельства, что эволюция конкретного состояния

|(t)

определяется уравнением

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

|

|1

в пространстве

бы его в те же самые условия, что и

Hи | ,

поставили то мы бы

получили результат применения того же самого оператора

Ut0

,t1 .
Как это утверждение можно проверить ? Для этого единственный путь: качестве надо брать всевозможные состояний и

есть

состояния

|

в

начальных

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

U

t0 ,t1

|

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

насколько эта аксиома верна. совершенно только систем, само собой нельзя квантовые сделать состояния.

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

счетом

ничего

означает о том,

пор, пока мы не применили к нашей системе измерение. принципиальный
чисто

факт

говорит

существует

квантовой

механики,

которая

бы не опиралась бы на классическую механику, описывающую процесс измерения. Измерения.

Зафиксируем

некоторый

базис

23


{|1 , . . . , |n }
базисе

в

пространстве случайная

H

,

о

котором

будем

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

|j
в

с

вероятностями вычисления

| j | |2

Борна

квантовых формализме иного состоянии, измерения. в выборе

стандартном Нет о его этом от квантовом процедуре

аксиома.

никакого

способа

информацию подвергнуть выбор он при

Единственный

заключается измерение.

? |j
на

зависит

экспериментальной Чаще

установки, всего

которой

проводится

выбирают величин, (и

измерение базисе тогда в

каких-либо пространстве об

дополнительных состояний), либо в

например, координаты (и тогда говорят о координатном импульса говорят импульсном базисе пространстве

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

остаются

единственная квантовой

узнать

состояние

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

24

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

|j

1

или

|j

2

. Если мы по каким-либо причинам не настройку и о вообще аппаратуры возможность для характере

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

макроскопическими

приборами

квантовом

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

(макроскопический качестве

одновременно системы,

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

|

времени

займет

процедура измерения ? Если предположить, что частицы одного типа идентичны, можно произвести одновременно очень много экспериментов квантовой (как это и делается в статистической теории). Можно напрямую

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

адресоваться непосредственно к индивидуальным атомам,

25


поэтому для постановки такого рода экспериментов нет принципиальных трудностей, кроме времени.

1.2.1

Абстрактная компьютера

модель

квантового

Теперь

мы

опишем которая

абстрактную может из уже

модель

квантового для

компьютера, Эта в

использоваться

подсчета его сложности, то есть времени модель состоит двух

Tq

ua .
классической унитраных

частей:

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

U1 , U2 , . . .

простых 1-2

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

состоянием

|0

.

Если

квантовые состояния заполняют части компьютера таков:

содержит n кубит, то ее 2n мерное гильбертово

пространство состояний. Общий вид состояния квантовой

N -1

| =
j =0
где

j |j

(1.11)

N =2

n

, а коэффициенты

j есть комплексные числа,

называемые амплитудами соответствующих состояний

|j

.

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

26


пространстве

состояний,

размерность

которого

N

нам

недоступна, хотя число кубитов мы мы назвали кубитовым

n

есть вполне доступная волновой выражает

величина. Мы видим, что (1.11) совпадает с тем, что представлением компьютер функции. Поэтому квантовый

стандартную формализма.

форму

многочастичного

гильбертова

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

j

над состоянием

|j U

выполняется преобразование вида

V

W

...
операторы

(1.12)

где коды

данные которых

элементарные стоят в

U, V , W . . .
части

регистрах

классической

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

N -1

|(t) =
j =0
то есть сводится к

j (t)|j
во времени амплитуд

изменению

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

27


некоторый где

унитарный

оператор

U

:

H1

-

H2

,

H1

-

m

и

k
из

кубитное

гильбертово и

пространство регистр вопроса Если

состояний. Заведем на ленте определенное место: набор кубит в (регистр)

m

кубит,

специальный регистром

классической вычисления

части,

называемый в

(query). Условимся что если регистр вопроса содержит

0,

происходят

обычном

порядке.

же регистр вопроса содержит частью компьютера, где

1,

мы вместо обычного к оракулу, нами

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

I

U

,

U

применяется Нетрудно

выделенному что это

m

кубитному регистру, а идентичное преобразование - ко всем прочим. понять, определение понятия на является непосредственным понятие распространением квантового

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

f : {0, 1}m - {0, 1}k
Заведем на квантовой ленте ответа. Пусть

m

и

k

кубитные регистры, из нулей и единиц,

назвав первый регистром вопроса, а второй - регистром

a
в

и

b

-

кортежи регистрах.

содержащиеся

этих

Введем

унитарное

преобразование, определенное таким его действием на базисных векторах:

Quf |a, b - |a, b
где означает и побитовое он

f (a)
по

(1.13) модулю 2. до

сложение

Такой оператор является просто перестановкой базисных векторов, потому линейно продолжается унитарного оператора во всем пространстве квантовых 2 состояний. Он инволютивен, то есть Quf = I. В 28


Приложении

описано,

как

с

помощью

этого

приема

построить быстрый квантовый алгоритм перебора.

1.3
Как

Роль запутанности
мы знаем, и запутанное , это виде в состояние двух Это в квантовых невозможно точности записи всей ее

систем

S1

S2
в

состояние,

которое .

представить соответствует,

|S1

|S2

обычной произведения

аналитической волновой волновых с

невозможности системы частей в

представления

функции

виде

функций

S

1и

S

2 . Можно ввести меру такой запутанности
путями. Например, использованием

различными

относительной матрицы плотности которая равна



S1 . Определим меру

запутанности как квантовую энтропию тому же выражению,

H = tr(S1 ln S1 ), взятому для S2 .

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

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

времени, квантовых

сложностью, на

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

H

. Возможность состояний

запутанных

29


даже

с

максимальной примера

степенью

запутанности класса

совсем

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

GH Z

и

W

GH Z : 1 |11 . . . 1 + 2 |22 . . . 2 + . . . + k |k k . . . k , W : 1 |100 . . . 0 + 2 |010 . . . 0 + . . . + k |00 . . . 1 .
(1.14) Мы видим, что для хранения таких состояний в памяти компьютера достаточно выделить порядка памяти, где на

n

ячеек

n

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

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

GH Z

и

W

можно

свести к одночастичным состояниям. Рассмотрим сначала

GH Z

. Его аналогом для

n=2

является так

называемое шмидтовское состояние двух частиц, то есть состояние двух частиц вида

j |
j
где в

1 j

2 |j

(1.15)

1 {|j }

и

2 {|j }

есть

ортонормированные первой (1.15 и второй

базисы частиц

пространствах числами, где

состояний Состояние

соответственно.

характеризуется гильбертовых

N

N

есть

размерность

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

30


Состояние для

GH Z

есть форма шмидтовского состояния Такое состояние означает

нескольких

частиц.

следующее. У нас реально имеется только одна частица, но она состоит из нескольких частей, ведущих себя просто как одно целое. Рассмотрим

GH Z

состояние при

k=2

:

| = |00 + |11

. Будем трактовать

0

и

1

как положения

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

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

будет тот же: его у любой

|00 + |11
из них.

. Это означает, что и импульс и объясняет то, что такое

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

GH Z

типа.

образом,

тип

запутанности

является

достаточно широко распространенным. Более интересно детектирование такого типа запутанности на больших расстояниях. Для ионов в ловушках Пауля оно составляет несколько миллиметров, для фотонов - до нескольких километров. Не зависимо от числа бы точек было конфигурационного не меньше двух) пространства (лишь оно

31

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

|100

+ |010

+ |001 W

или

аналог

амплитыдами, с

является

простейшим унитарных

примером состояния типа сводимости

(и универсальным в смысле одночастичных

применением

операторов, запутываний отдельных кубитов с анциллами и измерений, т.н. LOCC- сводимости). Теперь типа. его если при мы Это состоянию можно обратимся состояние никакими трактовать к не общему может как виду состояния к быть сведено

W GH Z

LOCC каждый

операциями. кубит как

Однако элемент что точки что функции

одночастичное

состояние,

рассматривать кубитовом

конфигурационного договаривались

пространства. кодировать в

Напомним, волновой кубитами том

представлении пространства

конфигурационного положения А теперь точки мы

смысле,

каждый следующий кубит был уточнением в два раза конфигурационного примем иное пространства. соглашение: временно

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

|100

будет

1

(а точки 2 и 3

|010

означает нахождение частицы

в точке 2 (а точки 1 и 3 свободны), и т.д. Тогда состояние

GH Z

типа вида (1.14) будет соответствовать волновой k функции одной частицы вида j |j . j =1

32

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

1.3.1

Моделирование квантовых систем

Теперь обратимся к задаче квантового моделирования физических систем. Это как раз и есть та задача, которую имел быть в виду Р.Фейнман, набором и т.д. выдвигая идею квантового значение от компьютера. Состояние многочастичной системы может описано чисел, Эти выражающих массы, (в и числа физических скорости, величин, таких как координаты, отличие

время

амплитуд) вещественные. Более того, при надлежащем ограничении измеряющего области прибора рассмотрения разрешимости можно считать, что все они l , где n разумной величины представляются в виде 2n число. Тогда базисное состояние рассматриваемой многочастичной памяти из состояние для системы можно представить как базисный же вектор в пространстве состояний квантовой

n

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

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

моделируемой

естественного

физического

смысла.

Однако

компьютере, к

который

моделировать систем можно

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

многочастичных

33


процессов

на

классических

компьютерах.

Для

этого

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

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

независимой как

переменной Эта для что

Фурье-образа известная уравнение, компьютера. связанным будет Это с

коэффициентом, импульс. и вручную

переменная хорошо волновое

идея,

физикам, Надо Фурье

решающим

великолепно лишь

работает убедиться,

квантового свойством,

квантовое

преобразование

обладает

аналогичным

операцией дифференцирования (для нашего квантового симулятора из того, что роль QFT дифференцирования конечная является разность). Фурье при играть следует к соответствующая настоящего Нашей квантового

приближением

оператора

преобразования целью будет

переходе

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

изучаемой системы в некоторый момент времени

t.

Нам

нужно с помощью рабочих преобразований приблизить действие оператора эволюции e-iH t/h на волновую p2 , Hx = V (x), p = функцию 0 , где H = Hp + Hx , Hp = 2m h и потенциал V (x) есть вещественная функция. Для i x простоты возьмем время t равным единице. Реализовать на квантовом компьютере действие

Hx

просто. Поскольку

34


матрица этого оператора (а значит и

e

iHx

) диагональна,

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

Hp

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

t

представим приближенно

наш эволюционный оператор через формулу Троттера:

e
В

-iH

(e

-iHx t

e-

iHp t 1/t

)

.

(1.16) убедиться, выбрали

справедливости

этой

формулы в ряд.

легко Мы

раскладывая вид.

экспоненту

координатный базис, так что

Hx

имеет диагональный

Применяя квантовое преобразование Фурье: + -ipx QFT : f - - e f (x) dx и его свойство переводить дифференцирование / x в умножение на ip, мы можем представить действие импульсной части оператора как 2 e-iHp = FT-1 e-ip t/2m FT, где средний оператор имеет диагональный вид. Теперь последовательные применения 2 QFT и фазового сдвига на -p /2m при реализации последовательности (1.16) дают требуемое приближение. Примененное в данном методе преобразование Фурье осуществляется по каждой из координат отдельно, и если у нас несколько частиц - то по каждой из координат каждой частицы отдельно. Некоторую совершенно техническую квантовом проблему представляет унитарного реализация на e-iHx , Если

компьютере

оператора энергии.

соответствующего

потенциальной

потенциальная энергия просто равна

p

, то реализация

35


такого

диагонального

оператора

может

быть

сделана,

если мы просто совершаем последовательные повороты фазы вида |0 - |0 , |1 - ei |1 , в зависимости от места очередного кубита в регистре, содержащем значение координаты. В случае произвольного вида потенциальной энергии, мы будем предполагать, что ее можно разложить в ряд Тейлора с коэффициентами, которые определяются с помощь достаточно быстрого алгоритма. Например, если этот потенциал получается как сумма кулоновских потенциалов от

n

разных частиц, то такой алгоритм будет

иметь сложность линейную в зависимости от числа

n

при условии, что координаты частиц также выдаются некоторым фиксированным алгоритмом (который можно -ihHx можно рассматривать как оракул). Тогда оператор e представить в виде схемы квантовых вентилей (quantum gate array) размера, линейно зависящего от

n

.

t

Сложность данного метода в зависимости от времени реальной физической системы будет O(t2 ). Это

непосредственно вытекает из того, что точность формулы Троттера имеет второй порядок, поскольку она вытекает из для тейлоровского любого (см. разложения если Итак, экспоненты до члена. Можно понизить сложность до знеачения первого 1+

O(t

)

> 0,
[65]).

вместо на

формулы более -

Троттера высоких решения

использовать порядков можно

тейлоровское

разложение

квантовом эволюции

компьютере

моделировать

унитарные

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

3

пропорциональной

размеру

рассматриваемой

В то время как на обычном компьютере это компьютере мы получаем кубитовым лишь квантовое

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

3 Предсказывать состояния системы в момент

t

за меньшее время

t
можно только в специальных случаях, см., например, [32].

36


реального, Заметим

в

то

время

как

классическое

вычисление можно

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

движущихся с

нереляривистском этого надо

электромагнитного

A.

Для

заменить где не

p
мы

любой частицы на света. Проследив что это увидим,

p - e A, c
никак

e

ее заряд,

c

- скорость конечном

вышеизложенные

рассуждения, на

отразится

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

37


Глава 2 Задачи
1). с Доказать, естественным что пространство квантовых состоний это?) скалярным произведением (что

является гильбертовым (доказать линейность скалярного произведения, неравенство треугольника). 2). Как определить скалярное произведение в случае непрерывных функций пространстве. 3). Экспонента от матрицы а) Показать, что равенство имеет место для

|

? Доказать, что это определение

переходит в естественное на конечномерном гильбертовом

A: exp(A)

определяется как

сумма ряда Маклорена для экспоненты (что это такое?).

exp(A + B ) = exp(A)exp(B ) коммутирующих матриц A и B (что это

такое?) и может нарушаться для некоммутирующих. б). Показать, что производную матричной функции

exp(A t) можно A exp(A t).
3). формулой

найти по обычному правилу линейный оператор для

(exp(A t)) =
определяется векторов

Эрмитов

H

(H f , g )
есть

=

(f , H g )

любых

пространства определению длины всех

состояний. векторов.

Унитарный что

оператор а) для

U

по

линейный

оператор,

сохраняющий любого

Доказать,

38


эрмитова

оператора б) 1) для

H

оператор

exp(iH )

является

унитарным, (Указание: к

любого

унитарного

оператора о

существует эрмитов оператор диагональному виду, 2)

H

, такой что теоремой

U U = exp(iH ).
приведении определение

воспользоваться

использовать

матричной экспоненты). 4). Почему запись 5). по В квантовой с

|H |

является корректной только

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

H

? величинам строятся является состоянии которые в

измеряемым

операторы,

обычными

величинами состояние

классической

Если

некоторое оператору

|
в

собственным для оператора соответствующая

A, A

то говорят, что величина, принимает соответствующему

|

определенное

значение,

равное

собственному числу будут эрмитовыми:

A.

Какие из следующих операторов

а) оператор градиента (что это такое?), h где h б) оператор импульса p = i постоянная Планка, в) оператор координаты

10-

27

эрг сек -

x : (x) - x (x)

?

г) оператор кинетической энергии (выписать его)? д) оператор потенциальной энергии (выписать его для частицы в кулоновском поле точечного заряда)? 6). По аналогии набора с задачей 5) построить момента вид квантово энергии, импульса. операторов перейти 5) и 6) механические трехмерного 7). над к Как операторы: кинетической

координат

r

,

Какие их этих операторов будут эрмитовыми? определить диагональный непрерывными кубитовому функциями? из (Указание: задач

представлению Какие

конфигурационного

пространства).

операторов

имеют диагональный вид? 8). Найти собственные значения и собственные векторы

39


операторов Паули

x =
и

0 1

1 0
их

, y =
к

0 i

-i 0

, z =
виду.

1 0

0 -1
ли

привести

диагональному

Являются где

эти

операторы

эрмитовыми?

унитарными?

Получить

коммутационные соотношения вида 9). Оператор

[A, B ] = C

A, B

- матрицы Паули. Найти экспоненты от этих операторов.

H

в уравнении Шредингера называется

Гамильтонианом и является оператором энергии. а). Написать его явный вид для одномерной частицы. (Указание: использовать результаты задач 5) и 6), а также 2 классическую формулу для полной энергии E = p /2m + V где

p

- импульс,

V

- потенциальная энергия.

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

собственных векторов Гамильтониана. Сформулировать ее в виде задачи поиска решений некоторого уравнения (Указание: это уравнение имеет вид

H |

j

=

j

Ej
-

называются

энергетическими

уровнями,

| |

j. j

соответствующими

стационарными

состояниями.

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

40


в) трехмерной свободной частицы г)*** и трехмерной заряженной частицы массой

m

зарядом

e

в

кулоновском объект

потенциале

точечного для

неподвижного заряда (Это - трудная задача. Указание: какой физический является прообразом данной идеализации? Решение можно найти в любой книге по квантовой механике, а также в википедии). д)** пункта Дать можно г), если ли применять идеальную поле модель из кулоновское создается другой энергий

частицей с тем же зарядом, но массой грубую оценку точности

M 2000m?

нахождения

такой двухчастичной системы при применении идеальной модели пункта г). 12). а) Написать Решить уравнение задачу Бройля для для поиска собственых частицы векторов и значений оператора импульса. эту де свободной (Указание: задачу 5)). б) Как выглядит решение задачи Коши для уравнения Шредингера в случае свободной частицы с определенным начальным импульсом? (Указание: будет ли определенной также и ее энергия? Использовать результат задачи 11а)). 13). Сформулировать задачу Коши для уравнения Шредингера. Как решать эту задачу, если есть формула для общего решения уравнения Шредингера? 14). Предположим, что стационарная задача для уравнения Шредингера решена. Написать выражение для общего решения задачи Коши для уравнения Шредингера. 15). общего Написать решения что формулу Гамильтониан для это нахождения (Указание: число, просто уравнения Шредингера волна

exp(ipr/h). ??

Использовать

предположить,

а затем использовать понятие матричной экспоненты и результат решения задачи 3б). В каком случае удобно пользоваться найденной формулой? Можно ли применять

41


ее, если потенциал

V

зависит от времени? Как надо

понимать экспоненту для того, чтобы эту формулу можно было применять в случае нестационарного потенциала?*** (Это - трудная задача. Указание: использовать понятие хронологической экспоненты (см. [?]). 16). Найти собственные состояния (векторы) и собственные числа оператора координаты. Рассмотреть случай одной частицы и задачу к сначала Как в непрерывному случаю, выглядит

n

частиц. (Указание: решить форме. Затем дельта перейти функции используя

кубитовой

Дирака.)

разложение

произвольного

состояния в ряд по собственным функциям оператора координаты? Собственные вектора оператора координаты составляют 17). Фурье во что в Как так называемый координатный базис в гильбертова пространства состояний. выглядит преобразование (Указание: Фурье непрерывном случае? В дискретном? Написать оператор кубитовой форме Используя , написать, переводит из задачи Fouriназывается обратное кубитовое приближение волновой функции кубитовое вектор преобразование оператора преобразование QFT). Выписать, собственный 16)). er квантовым

|

Фурье Фурье во

координаты

Кубитовое -

преобразованием

Фурье

(Quantum что

Tranform

квантовое преобразование Фурье переводит произвольный базисный вектор. Выписать матрицу прямого и обратного квантового преобразования Фурье. 18). образуют 12), Cобственные так функции оператора импульса базис задачи от называемый для этот импульсный результат и оператора оператор

пространства написать координатного оператора.

состояний. выражение базиса ли к

Используя

перехода

импульсному

обратного унитарным?

Будет

Эрмитовым? Каково короткое название этого оператора?

42


(Указание:

Рассмотреть

кубитовый

и

непрерывный

случаи. Использовать результат задачи 17)). 19). Как выглядит QFT и обратное ему в случае одного кубита? 20). Найти базис пространства состояний, в котором матрица двумя б) с оператора импульса а) с диагональна. Фурье. факта, (Указание: задачу 18) и использовать преобразование того Решить задачи что

способами:

использованием

использованием

непрерывное

преобразование Фурье переводит дифференцирование в умножение на аргумент и мнимую единицу (см. [?]), и того, что QFT является дискретной версией преобразования Фурье). 21). Найти базис пространства состояний, в которой оператор кинетической энергии диагонален. (Указание: использовать задачу 20). Рассмотрим систему 2 кубитов. Измерение каждого из них может дать 0 или 1. Поэтому у системы есть 4 классических состояния: 00, 01, 10 и 11. Аналогичные им базовые квантовые состояния:

|00 , |01 , |10 , |11 .
И наконец, общее квантовое состояние системы имеет вид

| = a|00 + b|01 + c|10 + d|11 . |a|2 измерения |00
Теперь получить в 2 2 , и т.д. Отметим, что |a| + |b| + вероятность

|c| + |d| = 1

результате 2 2

как полная вероятность. Если мы измерим только первый кубит квантовой системы, находящейся в состоянии | , у нас получится: 2 2 1) с вероятностью p0 = |a| + |b| первый кубит перейдет в состояние

|0

а второй - в состояние

1 |a + |b|2 |2

(a|0 + b|1 ),

43


2) с вероятностью в состояние

p1 = |c|2 + |d|2 1

первый кубит перейдет

|1

а второй - в состояние

|c|2 + |d|2

(c|0 + d|1 ).

В первом случае измерение даст состояние

|0 = |0
во втором - состояние

1 |a|2 + |b|2

(a|0 + b|1 ),

|1 = |1
Мы снова видим, записать состояний.

1 |c|2 + |d|2
что как о

(c|0 + d|1 )
такого в измерения в котором результат

результат вектор том, Такое

невозможно пространстве участвует получится

гильбертовом же

состояние, какой называют

наше на

незнание первом

кубите,

смешанным на второй

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

|

кубит, и записывают в виде матрицы плотности вида

2 = p0 0 + p1
определяется как Рассмотрим состояние

1

где матрица плотности состояния ситуацию. У нас

|

| |.
имеется

следующую

A, про которое мы знаем, что для каждого j = 1, 2, . . . , k с вероятностью pj оно является состоянием | j для некоторого фиксированного списка состояний {| j , j = 1, 2, . . . , k }. Такое состояние можно
представить себе как случайную величину, принимающую значения Такое

|

j с вероятностями
называют

p

j . Таким образом,
в

A

не от

является элементом гильбертова пространства состояний. состояние смешанным, отличие чистых состояний - элементов гильбертова пространства.

44


Имея имеем

смешанное некоторое как

состояние, чистое меру

мы,

в

действительности, просто мы не

состояние, нашего

знаем, какое именно, и смешанность состояния можно трактовать плотности равна незнания. Матрица смешанного состояния

A

по

определению

pj j .
j
Матрицы квантовую квантовой плотности были впервые (позже введены также в

механику теории

Л.Д.Ландау

Дж. на

фон Нейманом). Их роль состоит в том, что все выводы можно сформулировать только языке матриц плотностей. 22). Написать общий вид матрицы плотности

=

| |

состояния

|

n

кубитов. Какой смысл имеют

диаготальные элементы этой матрицы? 23). Пусть состояние является плотности решением уравнение, которому

|(t)

зависит от времени, и Шредингера. его что доказать, Написать матрица формула

уравнения

подчиняется

(t).

(Указание:

дифференцирования произведения распространяются на матрицы и использовать ее для получения уравнения на матрицу плотности.) 24). Верно ли, что если два (смешанных) состояния имеют одинаковые матрицы плотности, то мы не можем никакими экспериментами отличить их друг от друга? Под экспериментом понимается выдача экспериментатору реальной системы, находящейся в заданном состоянии, и последующие действия экспериментатора над данной системой. (Указание: дать различные уточнения этой общей формулировки, и рассмотреть унитарные эволюции - решения уравнения Шредингера, и измерения.) 25). Доказать, что общий фазовый множитель

exp(i)

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

45


физического смысла. (Использовать результат задачи 24). 26). означает Есть на ли физический смысл в прибавлении уравнения константы к потенциальной энергии? Что эта операция уровне матричной записи Шредингера? 27). Рассмотрим пространства, где координат? Как

N

- мерное гильбертово пространство

состояний. Как записать базисное состояние

|j

из этого объект ; надо

j {0, 1, . . . , N - 1}
записать в матричной состояний

в виде столбца форме

j |?
бы

(Указание: надо, чтобы выражение скалярное произведение

j |k |j

обозначало и

|k

применить определение скалярного произведениия - см. задачи 1 и 2). Как записать в дираковских обозначениях матрицу плотности чистого состояния эрмитовой? матрицы Каков канонический чистого

|

? вид

28). Верно ли, что матрица плотности всегда является (диагональный) плотности состояния? Смешанного

состояния? Привести алгоритм, распознающий чистоту состояния по заданной его матрице плотности. 29). Чему равен след матрицы плотности? Обосновать ответ. (Указание: использовать правило Борна и аксиомы вероятности). 30). Доказать формулу

trace | | = |
среднее

. значения

31). Наблюдаемой называется любой эрмитов оператор

H

.

Как

определить

понятие

H



наблюдаемой 32).

H

в состоянии

|

? (Указание: использовать

набор собственных чисел). Доказать формулу

H

=

trace ( H )

=

trace (H )
состоянии?

. (Указание: использовать задачу 31). Как

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

46


наложить теорему о

на

чистые

компоненты, любой

чтобы

их

можно к

было восстановить однозначно? (Указание: использовать приведении эрмитовой матрицы каноническому виду). Рассморим два пространства в них ортонормированные

A

и

B

, и зафиксируем

базисы

a1 , a2 , . . . , a

N

и

b1 , b2 , . . . , bM . Тензорным произведением этих пространств A B называется линейная оболочка формальных выражений ai bj , i = 1, 2, . . . , N , j = 1, 2, . . . , M ,
которые считаются ортонормированным базисом в тензорном произведении. Условимся, что знак дистрибутивностью. состояний Тогда тензорным обладает

свойствами ассоциативности, и по отношению к сложению произведением

aA ?

и

?B b

называется

a ?

?A b

B A

. Такое и

состояние называется не запутанным. Тензорным вектора Эти по произведением операторов

B

называется оператор правилу: определения

A A

B

, действующий на базисные

Ba

i

b

j

=

A(ai )
на

B (bj ).
случай знак

естественно

переносятся

нескольких пространств. При 34). использовании Существуют дираковских ли обозначений тензорного произведения часто опускается. запутанные состояния? Обосновать ответ. 35). Пусть общий вид. плотности

|

- состояние 2 кубитов. Написать его как будет выглядеть матрица

Написать,



1 смешанного состояния первого кубита после

измерения второго. Доказать, что состояние 36). системы не



1 является матрицей

плотности чистого состояния тогда и только тогда, когда

|

было не запутанным. называется запутанные. оператор не запутывающим, ли, что если

Оператор в не

он переводит не запутанные состояния двух кубитной Верно для 2 любой запутывающий кубитов является

47


тензорным произведением? 36). Оператор CNOT (control , not) действует так:

|x y - |x x

y , x, y {0, 1}

есть сложение по

модулю 2. Будет ли этот оператор запутывающим? Будет ли он тензорным произведением? Написать его матрицу. Аналогичные вопросы про оператор Тоффоли на трех кубитах:

|x y z - |x y z xy . 36). Пусть | - не запутанное

состояние двух кубитов,

один из которых находится в распоряжении Алисы, а другой - у Боба. Может ли Боб без обмена информацией с Алисой определить, какие дейтсвия (унитарные операции и измерения) она делает над свойм кубитом? Изменится ли вывод, если у Алисы и Боба есть еще дополнительные кубиты (которыми они не могут обмениваться), которые они могут запутывать с основными? 37). Пусть

A

и

B

заданы

матрицами.

Написать

короткую формулу для вычисления элементов матрицы их тензорного произведения. Обобщить эту формулу на случай многих кубитов. 38). Написать матрицу оператора Адамара H 1 (|0 - |1 ). 2 39)*. Оператор Уолша Адамара W есть

: |0 - n
я

1 2

(|0 + |1 ), |1 -

тензорная степень матрицы

H

(что это такое и почему это понятие

корректно?). Выписать короткую формулу для элементов

W

. (Указание: Используем задачи 37) и 38) и

рассмотрим элемент

w

ij . Написать разложение чисел

i

и

j

в двоичной системе счисления и наложить их друг на

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

48


состоянии, После

а

затем можно

проводит

над

ней

(и

нулевыми данные, первом

анциллами) некоторые операции - унитарные и измерения. этого статистически данного будет обработать на полученные на всех шагах. Можно ли ограничиться только однократной шаге? ответ. 41). Существует ли унитарный оператор что для любого состояния выдачей состояния ли такая Иными словами, ограниченная

формулировка эквивалентна первоначальной? Обосновать

| U |

U |0 = |

,

такой

|

?

(теорема о запрете клонирования квантовых состояний). Применить результат к задаче 40). Упрощ?нная компьютере на которой состояние посредством схема вычисления так: или берется е? начальное на квантовом кубитов, Затем конце выглядит системы базовых система

записывается

состояние. В

подсистем операций.

изменяется

квантовых

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

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

49


быстрее, 42).

чем

любой

классический вдоль

компьютер.

Это

и

называется квантовым ускорением. Отражением вектора

|a

называется

отображение, действие которого на базисных векторах задается формулой

Ia : |b -

|b , -|a ,

if b|a = 0, if |b = |a .

Доказать, что это отображение унитарно. Построить его матрицу. Что оно означает геометрически? 43). Пусть

? |0

- базисный вектор вида

|00 . . . 0

,

~ |0 =

W |? 0
Как

. Написать разложение |~ 0 выразить I~ через I? и W ? 0 0 (Указание: мусора, а сканировать результат в

по стандартному базису.

44)**. Реализовать на квантовом компьютере оператор

I? 0

.

кубиты

аргумента хотя бы

слева одной

направо, одновременно с нулевой анциллой, нужной для сбора выявления единицы накапливать специальном кубите, который

после сканирования использовать для изменения знака. После этого сделать все операторы в сканировании в обратном порядке.) 45). Пусть функция.

f : {0, 1}n - {0, 1} - n
оракул,

- местная булевская ей,

Квантовый

соответствующий

действует на базисные векторы так:

Qu

f

: |x, y

-

|x, y
схемы

f (x)
из

(явно указаны только разряды аргумента и

значения функции. Пусть

f

задана в виде классической элементов. Построить

функциональных

квантовый алгоритм, реализующий Сколько вызовов обойтись одним?

Quf

, а также

Ixtar

.

f

необходимо для этого? Можно ли

46). Пусть xtar - единственный корень уравнения f (x) = R 2 - вещественная линейная оболочка (что это такое?) R векторов |~ и |xtar . Доказать, что L2 есть инвариант 0

1, L

отражений

Ix

tar

и

I~ 0

.

50


47). Каков геометрический смысл оператора Гровера G = -Ixtar I~ ? (Указание: рассмотреть действие G на LR и 0 2 его ортогональном дополнении (что это?). 48). Пусть уравнение

f ( x) = 1

имеет не один, а

l

корней. Какой геометрический смысл тогда будет иметь R ограничение G на L2 ? t 49). Найти натуральное t, такое что G |~ максимально 0 близко к состояние

|xtar Gt |~ 0

.

Если

для

этого

значения

t

измерить

, с какой вероятностью получится

|x

tar ?

Как ответ зависит от числа корней l ? 50). Построить алгоритм для нахождения какого-либо корня уравнения сложность? 51). Решить задачу 50) в случае неизвестного числа всех корней. 52)***. ниже Доказать, схема что квантовая помещенная реализует QF T -1 .

f (x) = 1

на квантовом компьютере.

Если известно общее число корней, то какова будет его

51


a

0

r

r

r

r

i

b

4

a

1

r

r

r

i

r

b

3

a

2

r

r

i

r

r

b

2

a

3

r

i

r

r

r

b

1

a

4

ir

r

r

r

b
1

0

Рисунок 1. Квантовая схема для

QFT-

.

Кружки обозначают оператор Адамара, двухкубитные операторы имеют вид:

Uk,j =
Указание: состояния с какой

1 0 0 0

0 1 0 0

0 0 0 0 1 0 i /2k 0e

, k > j.
(2.1)

-j

a=

Зафиксировать два произвольных базисных aj 2j и b = bk 2k и рассмотреть, j k

амплитудой

a

переходит

в

b

(это

есть

соответствующий элемент матрицы оператора, о котором -1 надо доказать, что он равен QF T - см. определение

52

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

j>k между j a
j

k

кубитами. Обратить внимание на обратный порядок и

a

j

b

k

на входе и выходе. Использовать, то, что

переходит в

b

n-j +1 только в результате определенного

оператора Адамара. Просуммировать все вклады в фазу и убедиться, что они дают то, что требуется оператором QF T -1 . При необходимости использовать пособие ([65]) а также первоисточник ([40]). 53). Дана схема квантовых вентилей, реализующая унитарный оператор оператор

Useq |, a

U . Построить = (U a | |a ,

схему, реализующую где

a-

один

кубит

(оператор условного применения, типа CNOT). Указание: расширить набор элементарный вентилей, включив в него условные вентили типа CNOT для всех использующихся вентилей. 54)**. В условиях задачи 53) реализовать

Useq

для

a

- произвольное число кубитов. Какова сложность этого 55). Пусть

квантового алгоритма?

U

имеют

a- n-кубитный регистр, а собственные числа n вид exp(2 iwk ) где wk имеют вид k /2 , k RevU = QF T2 Useq

натуральное. Показать, что применение оператора

где

последний

оператор

применяется вида

к и

анцилле,

к

начальному

состоянию

| , ~ 0

последующее

53


измерение анциллы даст одно из чисел вычислить результат применения

wk

. (Указание: Этот

оператора.)

алгоритм принадлежит Абрамсу и Ллойду. В частном случае, когда 56)***.

U

есть умножение на натуральное число, что процедура из

его использовал Шор. задачи 55) n способна дать приближение с точностью до s/2 одного из Показать,

w

k

с

вероятностью ошибки, с

1 - 1/s,
цель n

даже

если в

wk

не

имеют указанного в задаче 55) вида. (Указание: оценить вероятность приближения если состоит для получении точностью

s/2

натурального

s

.

Можно воспользоваться пособием ([?]). )

q - натуральное число, такое что 2n-1 < q mod(q )) (r - мультипликативный период x по модулю q ), оператор Ux действует на n кубитное базисное состояние как Ux |y = |y x mod(q ) если y < q и Ux |y = |y если y = q , q + 1, . . . , 2n - 1. Доказать, что применение RevUx к состоянию из задачи 55) и
57)***. Пусть < 2n , xr = 1 ( последующее измерение анциллы позволяет вычислить

r

. (Указание: использовать результат задачи 56). Какова 58)***. Показать, что сложость алгоритма из задачи

сложность данного алгоритма? 57) можно радикально уменьшить, если сделать используя

реализацию

Ux

seq

экономным

последовательное умножение вида Из целого чисел результатов числа по 2 задач Для 56)-58) этого алгоритм П.Шора

x , d = 0, 1, 2, . . ..
вытекает уметь этого квантовый находить выбранных алгоритма произвольного

образом, 2d

факторизации надо периоды

q

.

мультипликативные

случайно

O(log q ) log (log q )
простого

не намного превышает сложность 2 умножения целых чисел (l og q ). Алгоритм

модулю 3

q

;

сложность

Шора является самым быстрым из известных квантовых алгоритмов. К сожалению, до сих пор не доказано, что не

54


существует столь же быстрого классического алгоритма. Самый быстрый из известных классических алгоритмов 1/3 ). требует времени O (q 59). Используя результат задачи 52), доказать, что приближенное преобразование Фурье можно реализовать за время

O(n)

где

n

- число кубитов. (Указание: отбросить

двухкубитные вентили с большим значением оценить возникающую при этом ошибку.)

|j - k |

и

60). Доказать формулу Троттера exp(A + B ) 1 1 m (exp( m A)exp( m B )) для эрмитовых матриц A и B (важна ли здесь эрмитовость?). Оценить ошибку этой формулы. (Указание: применить разложение в ряд экспоненты). 61). Вывести более точное выражене для чем формула Троттера. 62)***. можно кубитовым уравнения реальных потенциалы Доказать, что на из квантовом компьютере служащее получить состояние для

exp(A + B )

O(n)

кубит,

приближением Шредингера частиц за время

точного

решения

квантовой системы O(t2 ), при условии, между частицами

(t, r) из n
что

взаимодействия

имеют

простой алгоритм вычисления (схему из функциональных элементов). Указание: используя результаты задач 18), 20) и 52), представить гамильтониан формулу 18) и в виде суммы Затем кинетической и потенциальной энергий и применить к возникающим примерить экспонентым Троттера. 20) к результаты задач импульсной

части. Использовать также имеющиеся схемы вычисления потенциалов. Было возможно возможность произвольного показано, что не для всякого алгоритма того, для ?квантовое получения ускорение?. квантового Более ускорения

классического

алгоритма

является

большой редкостью ([30]) Применение идей квантовой механики уже открыли

55

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

сообщений. Прототипы систем подобного рода находятся на стадии разработки

2.1

Физические

реализации

квантовых компьютеров
Построение квантового компьютера в виде реального

физического прибора является фундаментальной задачей физики 21 века. В настоящее время построены только ограниченные его варианты (в пределах 10 кубит). Вопрос о том, до какой степени возможно масштабирование квантовой такого устройства, является предметом новой интенсивно развивающейся области многочастичной механики. Центральным здесь является вопрос о природе декогерентности (точнее, о коллапсе волновой функции), который пока остается открытым. Различные трактовки этого процесса можно найти в списке операции литературы. CNOT на Приведем пример реализации

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

|0

означает нахождение

|1

- в правой. Это называется кубит на

зарядовых состояниях. Общий вид квантового состояния

| = 0 |0 + 1 |1 .
Зависимость его от времени есть зависимость от времени амплитуд вида

0 ,

1 ; она задается уравнением Шредингера

ih

= H , t
56


где гамильтониан эрмитовости вид

H

имеет в силу одинакового вида ям и

a -a
для некоторой константы

-a a

a

, так что вектор

1 |~ = (|0 + |1 ) 0 2
есть собственный вектор 0 этого (так гамильтониана с собственным состояние), а значением называемое основное

1 |~ = (|0 - |1 ) 1 2
собственный (с вектор со значением значением

2a

(первое здесь

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

|

переходит за время

t

в состояние

0 exp(0t)|~ + 1 exp(-2at/h)|~ , 0 1
то для реализации операции NOT (перехода и наоборот) достаточно просто подождать

|0 - > |1 время t =

h/2a

. То есть гейт NOT дается просто естественной

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

a

для первой (управляемой) пары ям того, в каком состоянии находится

от

электрон во второй (управляющей) паре ям: если ближе к первой,

a

будет больше, если дальше - меньше. Поэтому

57


состояние электрона во второй паре определяет время совершения NOT в первой яме, что позволяет снова выбрать нужную длительность времени для производства операции CNOT. Эта схема очень приблизительная и идеализирована; реальные схемы сложнее и их реализация представляет вызов экспериментальной физике.

58


Литература
[1] G. Adenier, A. Yu. Khrennikov. Is the Fair Sampling Assumption supp orted by EPR Exp eriments?, J. Phys. B 40 No 1 (2007) 131-141 [2] V.Akulin et al, Description of quantum entanglement with nilp otent p olynimials: extensive characterization of entanglement and canonical forms, Pro ceedings of SPIE, 2006, vol. 6264, pp. 02-1 - 02-11. [3] V.Akulin et al, Quantum computers and computing, 2006, vol. 6 N1, pp. 107-125. [4] V. Aho, J. E. Hop croft, and J. D. Ullman. The Design and Analysis of. Computer Algorithms. Addison-Wesley, 1974. [5] K.Arakelov, molecules. Y.Ozhigov, Simulation via Asso ciation Quantum of state two-atom selection,

accepted for publication on Vestnik of MGU, Computational mathematics and cyb ernetics, issue 2009. [6] Exp erimental Realization of Einstein-Po dolsky-RosenBohm Gedankenexp eriment: A New Violation of Bell's Inequalities, A. Asp ect, P. Grangier, and G. Roger, Physical Review Letters, Vol. 49, Iss. 2, pp.91-94 (1982) doi:10.1103/PhysRevLett.49.91

59


[7] P.Benio, Quantum mechanical hamiltonian mo dels of Turing machines, J. Stat. Phys. 29, 1982, 515-546. [8] C.H. Bennett, E. Bernstein, G. Brassard and U.V. Vazirani, Strengths and weaknesses of quantum computing SIAM J. on Computing, Vol. 26, No. 5, pp. 15101523, 1997. [9] G. Birkho, J. von Neumann, The Logic of Quantum Mechanics, ?Annals of Mathematics?, 37 (1936), p. 823843. [10] C.H.Bennett, G.Brassard, C.Crep eau, U.M.Maurer, Generalized privacy amplication, IEEE Trans. Inform. Teory, 41, 1915, 1995. [11] R.Blatt et al, Ion trap quantum computing with Ca+ ions, Quantum Information Pro cessing, vol.3, 1-5, pp. 6173, 2004. [12] D.V.Blohintsev, Principal topics of quantum theory,

1977, Moscow, Nauka (Phys-math. lit.). [13] M. Boyer, M., G. Brassard, P. Hyer, and A. Tapp, Tight b ounds on quantum searching, Pro c. 4th Workshop on Physics and Computation, pp. 3643, 1996. [14] Bravyi S.B., Kitaev A.Yu. Fermionic Quantum Computation, Ann. Phys. - 2002.- v.298, N.1. - p.210-226 [15] L. E. J. Brouer. Intuitionism and formalism. Amer. Math. So c. Bull., 20:8196, 1913. [16] Durr, C., Hoyer, P., A Quantum Algorithm for nding the Minimum, Pro c.Roy.So c.Lond. A455 (1999) 2165-2172 [17] R.Feynman, The theory of fundamental pro cesses, Caltex, W.A.Benjamin, Inc., NY, 1961.

60


[18] R.Feynman, Simulating physics with computers, J. Theoret. hys., 1982, 21, pp. 467-488. [19] R.Feynman, D.Hibbs, Quantum mechanics and path integrals, 1984, Moscow, Nauka (Phys-math. lit.). [20] M.Genovese, Research on hidden variable theories: A review of recent progress, Physics Rep orts, 413, 2005, pp.319-396 [21] L.Grover, A fast quantum mechanical algorithm for database search, Pro ceedings, 28th Annual ACM Symp osium on the Theory of Computing (STOC), May 1996, pages 212-219. Pro ceedings, Melville, NY, 2006, vol. 810, electronic version: xxx.lanl.gov, quant-ph/0610052. [22] M.A.Horne, A.Zeilinger, Sp eakable and Unsp eakable in Quantum Mechanics, Invited b o ok review, Amer.J.Phys., 42,630 (1989). [23] A.Khrennikov, Prequantum Classical Statistical Field Theory: Complex Representation, Hamilton-Schr?dinger Equation, and Interpretation of Stationary States, Foundations of Physics letters, vol. 19, N4, pp. 299-319 [24] Kleene, S. C. and Vesley, R. E., 1965, The Foundations of Intuitionistic Mathematics, Esp ecially in Relation to Recursive Functions, North-Holland, Amsterdam. [25] D.E.Knuth, The art of computer programming, AddisonWesley, 1997 [26] P.Kurakin, G.Malinetskii, H.Blo om, Dialogue mo del of quantum dynamics, Pro ccedings of SPIE, vol. 6264, 2005, Quantum Informatics - 2005 (ed. Y.Ozhigov)

61


[27] A.A.Markov, Ab out the continuity of constructive functions, Usp ehi Mat. Nauk (rus), 1954, 9, N 3 (61), pp. 226-229. [28] Yu.I.Ozhigov, A.Yu.Ozhigov, Algorithmic container for physics, AIP Conference Pro ceedings, vol. 962 (Quantum Theory, Reconsideration of Foundations) pp. 168-174 [29] Y.Ozhigov, Amplitude quanta in multi particle system simulation, Russian Micro electronics, 2006, vol. 35, 1, 5365. [30] Y.Ozhigov, Lower b ounds of a quantum search for an extreme p oint, Pro c.Roy.So c.Lond. A455 (1999) 2165-2172 [31] Y.I.Ozhigov.Quantum Computers Sp eed Up Classical with Probability Zero, Chaos Solitons Fractals 10 (1999) 1707-1714 [32] Y.Ozhigov, How b ehavior of systems with sparse sp ectrum can b e predicted on a quantum computer, Pis'ma v JETP, vol. 76, 11, pp. 799-804. [33] Y.Ozhigov, Dynamical diusion as the approximation of one quantum particle dynamics, lanl e-print, quantph/0702237 [34] Y.Ozhigov, Quantum recognition of eigenvalues, structure of devices and thermo dynamic prop erties. ZhETF, 2003, vol. 123, iss. 2, pp. 384-398. [35] Y.I.Ozhigov, Easy control on fermionic quantum computations, NATO Science Series, 2005, vol. 189, pp. 27-32. [36] A.Ozhigov, K.Arakelov, Y.Ozhigov, Principles of the numerical simulation of many b o dy quantum dynamics, Quantum computers and computing, 2006, vol. 6 N1, pp. 137-148.

62


[37] Y.Ozhigov, L.Fedichkin, Quantum Computer with Fixed Interaction is Universal, JETP Lett. 77, 328-330 (2003) [38] R. Penrose, The road to the reality, NY 2006. [39] J. Sheneld, Mathematical Logic, Nauka, Moscow (1975). [40] P.Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM J.Sci.Statist.Comput. 26 (1997) 1484-1512 [41] J.L. Andrade E Silva, J. Loshak, Fields, Particles, Quanta. Moscow, Science, 1972. [42] G.S.Tseitin, Algorithmic op erators in the constructive metric spaces, Doklady Academii Nauk USSR (rus), 1959, 128, N 1, pp.49-52. [43] J.A. Wheeler and W.H. Zurek, Quantum Theory and Measurement, Princeton UP, 1983 [44] Wolfram, S. Twenty Problems in the Theory of Cellular Automata. Physica Scripta T9, 170-183, 1985. [45] C. Zalka: Grover's quantum searching algorithm is optimal. Phys. Rev. A 60 (1999) 27462751. [46] V. Zarnitsyna , , J.Huang , , F.Zhang in , Y.Chien ,

D.Leckband Nov 8.

C.Zhu

Memory

receptor

ligand-

mediated cell adhesion, Pro c Natl Acad Sci U S A. 2007

[47] W.Zurek, Probabilities from entanglement, Born's rule from invariance, Phys. Rev. A 71, 052105 (2005) [48] Н.Боголюбов, Б.Ширков, Введение в теорию

квантованных полей, М.,Наука, 1974.

63


[49] Валиев

К.А.,

Квантовые

компьютеры:

смена

парадигмы вычислений, Вестн. МГУ,сер.15:Выч.мат.и киберн. 2005, N.2. cтр .3-16. [50] Валиев К.А., Квантовые компьютеры и квантовые вычисления, УФН, 175 1 (2005), стр. 3-39 [51] Валиев К.А., Кокин А.А. Квантовые компьютеры: надежды и реальность, Москва-Ижевск, РХД, 2000. [52] П. Витаньи, М. Ли, Колмогоровская сложность:

двадцать лет спустя, УМН, 1988, 43:6(264), 129166 [53] Владимиров В.С. Уравнения математической физики. М.: Наука, 1981. [54] П.Дирак, Математические основы теории

относительности, М., Мир, 1982. [55] В.М.Дубовик, частное сообщение [56] В.П.Кудря, частное сообщение. [57] Б. А. Кушнер. Лекции по конструктивному

математическому анализу. М.: Наука, 1973. [58] Л.Д.Ландау, Е.М.Лифшиц, Квантовая механика.

Нерелятивистская теория, Москва, Наука, 1974. [59] Л.Д.Ландау, Е.М.Лифшиц, Гидродинамика, М.Наука, 1988. [60] А.Н.Мальцев, Алгоритмы и рекурсивные функции, М., Наука, 1986. [61] Менский М. Б. Концепция сознания в контексте

квантовой механики, УФН 175 413 (2005)

64


[62] С.Н.Молотков, Квантовая криптография и теоремы В.А.Котельникова об одноразовых ключах и об отсчетах, УФН, 2006, т. 176, 7, стр. 777-788 [63] Новиков П. С. Конструктивная математическая

логика с точки зрения классической. М.: Наука. 1977 [64] Новосадов квантовой Б.К. химии: Методы Основы решения теории уравнений

молекулярных

орбиталей. Наука, Москва, 1988, 184 с. [65] Ю.И.Ожигов, Квантовые вычисления, учебное

пособие, Изд-во ВМК МГУ, 2003. [66] Д.Роджерс, Алгоритмы и рекурсивные функции, М., Мир, 1970. [67] А.Н.Тихонов, Методы решения некорректных задач, 1986, М.Наука, см. также ДАН СССР, 1963, т. 151, N3, стр. 501-504. [68] Р. Темам, Уравнение Навье-Стокса. Теория и

численный анализ, М.Мир, 1981. [69] Успенский В.А., Что такое нестандартный анализ? М.Наука, 1987. [70] Успенский В.А. Лекции о вычислимых функциях, Москва, Наука, 1960 [71] А.Ю.Хренников, Квантовая теория информации, М., Физматлит, 2008.

65