Квантовые компьютеры: надежды и реальность - Валиев К.А.
Скачать (прямая ссылка):
Третьим элементарным преобразованием является выборочное вращение фазы амплитуды в определенных состояниях. Одним из операторов, описывающих такое преобразование, является оператор инверсии С/о, сохраняющий вектор состояния |0), но изменяющий знак всех векторов состояния, ортогональных |0) (так называемая инверсия относительно состояния |0)):
С/о = 2|0) <0| — Т.
(2.62)
94
Глава 2
Унитарный оператор, действующий на произвольный вектор состояния, который сохраняет известный вектор | з) и изменяет знак всех векторов в гильбертовой гиперплоскости, ортогональной |s), принимает вид
Us = 2|я)(я| -1 = WU0W. (2.63)
Такое преобразование называется также «преобразованием диффузии». Эта операция осуществляет инверсию всех амплитуд х-го состояния относительно всех амплитуд известного начального s-ro состояния. Учитывая, что (s\s) = 1/N и (s\x) = 0 при s ф х, получим
Us\х) = 2/N\s)-l\x). (2.64)
Основой алгоритма Гровера является повторение над начальным состоянием двух унитарных операций: инверсии амплитуды только у искомого состояния v, определяемой третьим оператором типа
Uv = l-2\v)(v\, (2.65)
и применения затем преобразования диффузии для всех амплитуд состояния U8. Операция диффузии действует на вектор состояния, у которого все составляющие имеют одинаковые амплитуды, равные среднему значению ~ 1 /л/iV, кроме одной, соответствующей искомому состоянию, амплитуда которой после первой операции стала отрицательна. Амплитуды N — 1 составляющих практически не изменят своей величины, а отрицательная амплитуда станет положительной и увеличит свою величину до ~ 2/y/N.
Таким образом, необходимо повторение указанных операций Vn раз для того, чтобы амплитуда искомого состояния достигла значений ~ 1 > 1/VN, при которых она может быть измерена. Указанная итерация осуществляется с помощью унитарного преобразования
G = U8UV. (2.66)
Квантовая схема оператора этого преобразования строится только из операторов типа Уолша-Адамара и, в отличие от фурье-
преобразования, оно не содержит двухкубитовых операторов типа контролируемого изменения фазы. Фаза отдельных состояний изменяется лишь на 0 или п при каждой последующей итерации. Поэтому для алгоритма Уолша-Адамара не возникает трудностей с экспоненциальным
2.3. Помехоустойчивость квантовых вычислительных процессов 95
ростом временной цены операции, с которыми встречаются при квантовом фурье-преобразовании.
Заметим, что база данных для осуществления квантового алгоритма поиска может быть представлена и классическими системами памяти, достаточно лишь иметь выход из нее в квантовую систему, где булевые состояния будут преобразовываться в когерентные суперпозиции.
Экспериментальное осуществление этой операции было впервые выполнено на простейших ЯМР квантовых компьютерах (см. гл. 4).
Строгому математическому обоснованию и развитию квантовых алгоритмов и, в частности, алгоритма Гровера посвящено большое число постоянно появляющихся работ, ряд существенных результатов принадлежит Ю. И. Ожегову [2.34-2.36].
2.3. Помехоустойчивость квантовых вычислительных процессов
2.3.1. Коррекция квантовых ошибок путем кодирования сигнала
Квантовые компьютеры значительно чувствительнее по сравнению с обычными классическими компьютерами к различного рода образующимся, накапливающимся и распространяющимся в них ошибкам, обусловленных случайным разбросом параметров кубитов, взаимодействием кубитов с окружением, внешними помехами и декоге-рентизацией квантовых состояний. Поэтому для их надежной работы очень важно иметь методы контроля и исправления этих ошибок. Для исправления ошибок в классических компьютерах существуют эффективные корректирующие схемы, однако, к сожалению, они не применимы непосредственно в случае квантовых вычислений, когда ошибки связаны в значительной степени с явлением декогерентизации квантовых состояний. Для исправления этих ошибок необходимо иметь достаточную информацию о природе окружения, определение которой потребовало бы измерений, разрушающих квантовую информацию, закодированную в квантовой системе. Использование кодов с повышенной избыточностью казалась также невозможной из-за невозможности клонирования информации в квантовых системах. После длительного пессимизма относительно возможности разработки соответствующих методов коррекции ошибок в квантовых компьютерах, в конце 1996 года
96
Глава 2
появились сообщения о том, что разработка таких методов все-таки возможна (см. обзор [2.37]). Были изучены механизмы, позволяющие не только подавлять декогерентизацию, но и обращать ее. Существование кодов, исправляющих квантовые ошибки впервые было продемонстрировано в работах Шора и Стина (P. Shor, A. Stean) в 1995 году [2.38, 2.39]. Шором и Китаевым в 1996 году [2.40-2.42] было указано на возможность так называемого помехоустойчивого восстановления (fault-tolerant recovery) информации с высокой точностью при наличии ошибок, в том числе и тех, которые вносятся в самом процессе восстановления, а также на возможность организации помехоустойчивых квантовых вычислительных процессов (fault-tolerant computation).
