Файл: sem9.pdf

2. Второй шаг.

Сопоставим

x

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

|

0

i

и

|

1

i

|

y

i

=

|

y

N

−

1

, y

N

−

2

. . . y

0

i

и аналогичную цепочку

x

-му результирующему состоянию, получаемую в результате второй

унитарной операции Уолша-Адамара. Фаза результирующей конфигурации изменится на

π

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

|

1

i

, оставляя его в том же

состоянии

x

·

y

=

N

−

1

X

n

=0

x

n

∧

y

n

.

(9.11)

3. Третий шаг: выборочное вращение фазы амплитуды в определенных состояниях.

–

инверсия

U

0

, сохраняющая вектор

|

0

i

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

|

0

i

.

U

0

≡

2

|

0

i h

0

| −

1

(9.12)

или

U

S

≡

2

|

S

i h

S

| −

1

(9.13)

Такое преобразование называется

преобразованием диффузии

.

Учитывая, что

S

S

= 1

/N

и

S

x

= 0

при

S

6

=

x

получим:

U

S

|

x

i

=

2

N

|

S

i − |

x

i

(9.14)

Основной алгоритм Гровера является повторением над начальным состоянием двух
унитарных операций:

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

v

ˆ

U

v

= 1

−

2

|

v

i h

v

|

(9.15)

- применения преобразования диффузии для всех амплитуд состояния

U

S

.

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

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

∼

1

/

√

N

, кроме одной, соответствующей

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

N

−

1

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

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

∼

2

/

√

N

.

Таким образом, необходимо повторение указанных операций

∼

√

N

раз для того, чтобы

амплитуда искомого состояния достигла значений

∼

1

1

/

√

N

, при которых она может быть

измерена.

84