КОЛЛЕКТИВНЫЕ ОШИБКИ В АЛГОРИТМАХ УСИЛЕНИЯ АМПЛИТУДЫ

Сегодня активно обсуждаются различные версии квантового компьютера. Проблемой реализации идеи о быстрых квантовых вычислениях является недостаток разработок и существенная разница между экспериментальными и теоретическими квантовыми состояниями. В настоящее время она достигает более 20%. Зачем же нужны квантовые компьютеры? Изначально речь шла о шифровании сообщений. Ева стремится подслушать передаваемые шифрованные сообщения между Алисой и Бобом. Для этого Еве необходим закрытый ключ. Однако чтобы Ева смогла им воспользоваться, современные компьютеры должны уметь быстро раскладывать битные числа, чтобы вычислить алгоритм шифрования, но в реальности для этого потребуется достаточно много времени. В связи с этим ученые и заговорили о квантовых компьютерах, которые бы смогли запросто работать с большими числами. Но сможет ли квантовый компьютер использовать «правильно» свою вычислительную мощность для ускорения решения практических задач? С тех пор ученые и начали разрабатывать различные квантовые алгоритмы для быстрой факторизации больших чисел. В данном случае обычные компьютеры хорошо умеют перемножать числа, но с обратной задачей справляются плохо. Чтобы персональному компьютеру разложить число, состоящее из 256 символов, понадобится с десяток лет. А вот квантовый алгоритм справился с задачей за пару минут. Привычные вычисления работают с двумя состояниями – «0» и «1». Квантовый же алгоритм предназначен для выполнения операций на квантовом компьютере, данные в котором могут иметь бесконечное количество состояний. Из-за этого большинство квантовых алгоритмов основаны на принципе квантового параллелелизма, что подразумевает одновременное использование суперпозиции всех тех состояний квантового регистра, которые отвечают различным классическим битовым строкам. Для корректной работы все неклассические корреляции в таком состоянии должны быть сохранены вплоть до момента измерения. Поэтому при реализации квантовых вычислений проблемы декогерентизации становятся определяющими. Реальные квантовые системы не могут не испытывать взаимодействий с окружением, что в той или иной степени отражается на работе алгоритмов. Такого рода взаимодействия могут иметь различную физическую природу и в разной степени влиять на получение окончательного результата. По-видимому, не существует универсального подхода к проблеме наличия шума и борьбы с ним в системах квантовой обработки информации. Одним из разумных подходов является анализ влияния конкретных типов декогерентизации на работу тех или иных квантовых алгоритмов. Вместе со знаменитым открытием Шора алгоритм поиска Гровера является одним из фундаментальных алгоритмов для вычислений на квантовых компьютерах. Довольно скоро выяснилось, что алгоритм Гровера является оптимальным для неструктурированного поиска с обращениями к оракулу. Обращение к оракулу используется для вычисления неизвестной булевой функции для любой вводимой битовой строки. В настоящее время имеется целый класс квантовых алгоритмов, использующих квантовое усиление амплитуды искомых состояний. Именно это усиление является ключевым в работе алгоритма Гровера. Если полномасштабные квантовые вычисления будут действительно реализованы, то в силу повсеместного распространения задач поиска алгоритм Гровера и родственные ему станут незаменимым вычислительным инструментом. Следовательно, одной из приоритетных целей будет достижение устойчивой к ошибкам работы поисковых алгоритмов на квантовых компьютерах. Как известно, методы усиления амплитуды на квантовых компьютерах могли бы использоваться для криптоанализа классических блочных шифров, таких как стандарты AES и ГОСТ 28147-89. В подобных ситуациях неизбежна того или иного вида «вражеская» активность. Помимо собственных шумов, вызванных несовершенством устройств элементной базы, здесь следует учитывать помехи, намеренно вводимые в квантовые каналы противоборствующей стороной (сторонами). Одной из наиболее привлекательных для соперника возможностей является создание помех в канале обращений к оракулу. Вообще говоря, в регистрах из многих кубитов возможно появление ошибок многих типов. С другой стороны, оппонирующая сторона вряд ли будет иметь ресурсы оперировать с кубитами канала обращений индивидуально. Целью данной работы является анализ работы квантового алгоритма Гровера при наличии коллективных амплитудных ошибок при обращении к оракулу. Будет рассмотрена сравнительно простая, но достаточно содержательная модель амплитудных ошибок. В рамках этой модели удается получить замкнутые аналитические выражения и до конца проанализировать их ошибки при выполнении алгоритма Гровера.