Кулик Введение в теорию квантовых вычислений Книга 2 2008

Схема (рис. 5.8) позволяет наглядно схематично представить возможные переходы из одного состояния в другое для квантовой

схемы из двух квантовых элементов not .

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

Следует еще раз обратить внимание на то, что аналогичная схема (см. в книге 1, рис. 1.61в), построенная на классических вероятностных логических элементах НЕ (т.е. на элементах R), эквивалентна одному элементу R (см. в книге 1, рис. 1.61а).

Вслучае же квантовых элементов такая же схема обладает уже другим свойством.

Два последовательно соединенных квантовых элемента not уже не приводят к аналогичному эффекту как с элементом R, несмотря на то, что для квантового элемента not (как и для клас-

сического вероятностного элемента R) выполняется следующее соотношение для вероятностей переходов:

| a00|2 =| a01|2 =| a10|2 =| a11|2 =1/2.

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

Два последовательно соединенных квантовых элемента not

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

P01 =P10 =1, P00 = P11 =0,

что как раз и соответствует детерминированному логическому элементу НЕ. При последовательно соединенных 2-х квантовых

элементах not в итоговой квантовой схеме [7] случайность ис-

чезает!!! В классической схеме (т.е. в комбинационной схеме на классических логических элементах) подобный эффект не возможен.

351

5.3. Квантовые схемы

«…В науке самые глубокие озарения часто приходят тогда, когда разрабатывается метод для исследования новой области Природы.»

М. Нильсен, И. Чанг [1, с.21]

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

| A X M

| B	Z	N

Рис. 5.9

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

В теории квантовых вычислений приняты следующие важные соглашения [1, с.45]. Квантовую схему необходимо читать именно слева направо. Горизонтальные линии на квантовой схеме — это «квантовые провода». На практике эти провода не всегда есть реальные физические провода (как, например, в комбинационных схемах), однако они могут соответствовать, например, течению времени или физической частице, которая перемещается из одной точки пространства в другую точку. В качестве такой частицы может быть фотон. Обычно принято, что исходное состояние всех кубитов (т.е. входное состояние квантовой схемы) — это одно из состояний вычислительного базиса. Часто таким вычислительным базисом является именно | 0 и |1 . В качестве входного состояния

квантовой схемы обычно принимают то состояние, когда все кубиты находятся в | 0 . Если это соглашение не выдерживается, то

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

352

расположены в начале квантовых проводов (т.е. горизонтальных линий, причем число этих линий совпадает с числом кубитов). На рис. 5.9 кубиты (всего их 2) обозначены как начала квантовых проводов (слева) и находятся соответственно — верхний кубит (1-я система) в состоянии | A , а нижний кубит (2-я система) в состоя-

нии | B . Самый верхний провод (1-й кубит или 1-я система) соот-

ветствует старшему двоичному разряду, а самый нижний (последний, т.е. n-й кубит) — наименьшему двоичному разряду.

Можно обозначать преобразования H над квантовой системой из n кубитов как H{n}, так и H n . В случае, когда в квантовой

схеме используется много кубитов и соответственно квантовых проводов и гейтов, применяют специальное обозначение [1, с.59, 282, 289, 341, 567, 593], как показано на рис. 5.10, 5.11, 5.12.

Первый регистр

(n кубитов)

H n

| 0

Второй регистр

(m кубитов)

| 0

Рис. 5.10

| 0

H

| 0

H 3

| 0

H

| 0

H

Рис. 5.11

Рис. 5.12

353

Квантовая схема на рис. 5.11 представляет то же самое, что квантовая схема на рис. 5.12. Эти две квантовые схемы эквивалентны.

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

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

Отметим следующие особенности квантовых схем [1, с.46].

Во-первых, в квантовых схемах (в отличие от классических схем) нет обратных связей.

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

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

В-четвертых, для квантовых схем полагают [1, с.47, 238-239], что измерение можно представлять в них (выполнять или производить) только в конце всех вычислений, т.е. например так, как показано на рис. 5.9, где элементы в виде измерителей находятся в самом конце квантовых проводов. За самим измерителем начинается обычный провод, изображенный на рис. 5.9 двойной линией (т.е. провод в классическом смысле для представления (передачи) обычного классического бита M и N). Можно полагать, что в схеме на концах квантовых проводов имеются измерители. С этой спе-

354

цифической особенностью тесно связаны следующие два очень важных принципа [1, с.238-239]:

Принцип отложенного измерения

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

Принцип неявного измерения

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

Рассмотрим теперь подробнее квантовую схему на рис. 5.9. На этой схеме операции выполняются над 2-мя кубитами, один из которых (верхний или 1-й кубит) находится в состоянии | A , а ниж-

ний (или 2-й) кубит — в состоянии | B .

Входом схемы являются отдельные состояния кубитов | A , | B ,

(а также и состояние системы из 2-х кубитов).

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

Выходом схемы (см. рис. 5.9) являются новые состояния кубитов и новое состояние системы из 2-х кубитов. Измерение состояния этих кубитов дает с некоторой вероятностью два классических бита M и N.

На схеме (см. рис. 5.9) последовательно один за одним изображены 5 квантовых элементов (гейтов), из которых 3 элемента — это гейты CNOT (2 включены одинаково, а 1 — наоборот), один — это гейт NOT, обозначенный как X и последний — это гейт элемент Паули Z, обозначенный как Z.

На схеме (см. рис. 5.9) элементы CNOT являются двухкубитовами (двухвходовыми) гейтами, а элементы X и Z — однокубитовыми (одновходовыми) гейтами.

355

Остановимся несколько подробнее на состояниях в квантовых схемах. При рассмотрении квантовых схем надо отчетливо себе представлять, что:

•каждый кубит имеет свое какое-то состояние;

•набор из нескольких (не из всех) кубитов имеет свое состояние;

•квантовый регистр (т.е. набор из всех кубитов) имеет также свое состояние.

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

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

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

В итоге и сам квантовый регистр (как составная квантовая система) приобретает новое, но не обязательно измененное состояние.

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

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

Кубиты и квантовый регистр (согласно квантовой механике) могут быть как в чистом состоянии, так и в смешанном состоянии. Суперпозиция состояний кубита или суперпозиция состояний квантового регистра является чистым состоянием. В чистых состояниях выделяют базисные состояния, например для кубита — | 0 и |1 , а для квантового регистра из 2-х кубитов —

| 00 , | 01 , |10 , |11 . Возможен случай, когда квантовый регистр на-

ходится в чистом состоянии, а отдельные кубиты (например, не все кубиты) — в смешанном состоянии. Отметим, что смешанное состояние описывается матрицей плотности. Среди чистых состоянийсоставных систем выделяют перепутанные состояния ее

356

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

Для квантовых схем из содержания главы 2 следует, что при выбранном базисе для любого вектора состояния кубита | ψ ком-

плексные коэффициенты (т.е. амплитуды) a и b в суперпозиции | ψ = a | 0 +b |1 определяются однозначно.

На основании принципа суперпозиции произвольное состояние | ϕ рассматриваемого n-кубитового регистра имеет вид ( N =2n−1 ):

| ϕ = a0 | 0...00 + a1 | 0...01 +...+ aN |1...11 .

Для каждого из базисных состояний | CN CN −1...C0 , где Cm=0, 1 в

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

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

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

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

357

Отметим, что под действием гейта CNOT факторизованное состояние a b переходит в перепутанное двухкубитовое состоя-

ние.

С помощью гейта CNOT можно совершить и обратную операцию, т.е. факторизовать перепутанное состояние.

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

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

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

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

1 | 0 = 0 ,

а в качестве двоичной единицы — состояние, описываемое вектором

0 |1 = .

1

Вычислительным базисом могут быть также следующие состояния:

	| 0		1	1		| 1 =	1		1
		=			,			.
			2				2
				1					−1

Вообще говоря, при решении некоторых задач (см. Пример 5.6, 5.7, 5.8 и др.) не требуется вводить и тем более знать вычислительный базис.

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

358

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

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

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

3)задача синтеза квантовой схемы.

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

Определение 5.8

Задача прямого анализа квантовой схемы — по известному входному вектору | ψ и заданной матрице U, описывающей пре-

образование над | ψ , требуется найти выходной вектор | ψ′.

Определение 5.9

Задача обратного анализа квантовой схемы — по известному выходному вектору | ψ′ и заданной матрице U, описывающей выполненное преобразование над входным вектором, требуется найти (восстановить) входной вектор | ψ .

Определение 5.10

Задача синтеза квантовой схемы — по известному входному вектору | ψ и выходному вектору | ψ′ требуется найти (синтезировать) матрицу U, описывающую необходимое преобразование над входным вектором | ψ , чтобы получить | ψ′.

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

359

5.4. Однокубитовые схемы

«…в новаторской статье Шумахера … появился широко используемый теперь термин кубит, который возник в дискуссии Шумахера с Вуттерсом .»

М. Нильсен, И. Чанг [1, с.735]

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

•один кубит;

•набор одокубитовых гейтов;

•квантовый провод;

•измеритель (иногда на квантовых схемах не показывают).

Кубит, сфера Блоха и фаза Для квантовой схемотехники важно научиться рассматривать сами

кубиты как [1, с.33] «абстрактные математические объекты».

Определение 5.11

Кубит [1, с.224] — это вектор | ψ = a | 0 +b |1 , параметризованный

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

|a|2+|b|2=1.

В общем случае состояние кубита как квантового объекта — это [1, с.34] единичный вектор в двумерном комплексном векторном пространстве. Среди всех возможных состояний выделены два состояния | 0 и |1 , которые являются [1, с.34] специальными

состояниями. Эти состояния | 0 и |1 в теории квантовых вычис-

лений называют [1, с.34] состояниями вычислительного базиса.

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

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

360