1. Введение 3
2. Постановка задачи 5
3. Предварительные сведения 6
4. Переход к новому вычислительному базису 9
5. Математическая модель квантового процессора и математическая модель квантового шума 12
6. Формализация понятия квантовой ошибки 14
7. Алгоритм квантового хеширования 17
8. Методы коррекции ошибок 20
9. Программная реализация 38
Вывод
Приложения: 41
Список литературы: 62
В настоящее время существует большое количество вычислительных задач, решение которых с помощью классических компьютеров требует значительных вычислительных ресурсов (памяти, времени). На данный момент, как альтернативу классическому, рассматривают создание квантового компьютера. Квантовым компьютером называют вычислительную машину, которая использует запутанные состояния и явления квантовой суперпозиции для работы с информацией. Вместо классических битов квантовый компьютер использует его квантовые аналоги - квантовые биты (от quantum bit, qubit).
Если в классических битах информация может кодироваться одним из двух значений - 0 или 1, то кубиты могут находиться и в 1, и в 0 одновременно, т е в суперпозиции своих базовых состояний. Именно за счет этого явления вычислительная мощь квантовых компьютеров ожидается существенно выше в сравнении с классическими аналогами. Вместе с техническим прогрессом, с каждым годом появляются все новые и новые задачи, для решения которых вычислительной мощи современных компьютеров явно недостаточно. Поэтому создание такого вычислительного устройства является чрезвычайно важной фундаментальной проблемой современности.
Но тут не все так гладко. Между квантовым компьютером и окружающей средой всегда происходит взаимодействие, приводящее к разрушению информации. Это может быть тепловое воздействие, воздействие электромагнитных волн и т.д. Изолировать большую квантовую систему от внешних факторов полностью невозможно, а они напрямую влияют на процесс утери и искажения передаваемых данных, поскольку посредством взаимодействия вся квантовая информация оказывается закодированной в корреляциях между квантовым вычислителем и окружающей средой. Этот процесс (процесс искажения и разрушения передаваемых данных, происходящий в результате взаимодействия системы с ее окружением) носит название декогеренции.
В виду описанных выше особенностей, в отличие от классического компьютера, в котором может произойти ошибка только одного типа - ошибка инверсии бита, вычисления в квантовом его аналоге в дополнение к таким ошибкам страдают и от так называемых фазовых ошибок. Фазовые ошибки свойственны исключительно квантовым компьютерам и отсутствуют в классических вычислениях, поэтому классическое кодирование не обеспечивает защиты от них. Также существует еще один тип ошибок, присущий исключительно квантовым вычислителям, а именно смешанные битофазовые ошибки, приводящие одновременно и к перебросу кубита и перевороту фазы.
Помимо этого в квантовой теории информации есть некоторые барьеры на пути защиты от шума, усложняющие применение методов классической коррекции ошибок в квантовой системе. Это и теорема о невозможности копирования (мы не можем дублировать неизвестные состояния), и непрерывность квантовой ошибки, и разрушение квантовой информации при измерении, а также и сам факт наличия специфичных для квантовой информации ошибок.
Ученые давно бьются над проблемой коррекции ошибок в квантовых машинах, и на данный момент уже существует большое количество методов, в какой-то мере справляющихся с ней. Все из них используют добавочные кубиты (аналог для добавочных битов в стандартных вычислителях), отвечающие за сохранность передаваемой информации и помогающие отследить и исправить ошибку. Однако применение даже самых прогрессивных из этих методов, как правило, накладывает серьезный отпечаток как на ресурс используемой памяти и времени, так и на вычислительную мощь квантового процессора, поскольку больше 90 процентов этой мощи расходуется на коррекцию ошибок, а не на вычисление поставленной компьютеру задачи. А оставшиеся 10 сравнимы с мощью обычного среднестатисческого классического компьютера.
Поэтому, можно смело сказать, что на данный момент не существует метода предотвращения или исправления влияния шумов на квантовую систему приемлемо оптимального и по времени, и по используемой памяти, при этом позволяющего сохранить весь объем вычислительной мощи квантового вычислителя. Да и все существующие методы показывают какие бы то ни было результаты лишь на ограниченном наборе кубитов, для более крупной системы они просто оказываются не действенными. Поэтому разработка методов исправления и предотвращения ошибок является актуальной и весьма практически значимой задачей.
В ходе выполнения работы мной были изучены особенности квантовых вычислений, существующие модели шумов и методы исправления и предотвращения ошибок. Была разработана математическая модель квантового процессора, разрабатываемого в Казанском квантовом центре с упором на влияние шумов и обеспечение помехоустойчивости. Была спроектирована и реализована математическая модель процессора, эмулирующая его работу, а также эмулирующая возникновение квантовых шумов.
Реализована математическая модель квантового алгоритма, а также реализован модуль для проектирования и реализации квантовых алгоритмов, приспособленный для оценки влияния шумов на них. Была реализована математическая модель квантовых шумов и модуль обеспечения помехоустойчивости, а также произведена реализация квантового хеширования в полученной системе и произведено исследование влияния классической и фазовой ошибок на данный алгоритм. Также было произведено исследование состоятельности существующих методов коррекции в зависимости от длины входных данных и уровня шума в устройстве применительно к этому алгоритму, а также модифицированы наиболее эффективные методы коррекции квантовых ошибок, в соответствии с предложенной архитектурой устройства. В результате проведенных исследований было выяснено, что применение простых методов коррекции на небольшом количестве кубит для алгоритма хеширования не оправдывает себя должным образом. Однако модифицированный метод коррекции Стина показывает хороший результат на большом количестве кубит, и его использование не нивелирует преимущество от использования квантовых вычислителей, в связи с большими затратами на память и время обработки информации, поскольку используется достаточно малое количество добавочных кубит.
