Квантовое преобразование Фурье (сокр. КПФ) — линейное преобразование квантовых битов (кубитов), являющееся квантовым аналогом дискретного преобразования Фурье (ДПФ). КПФ входит во множество квантовых алгоритмов, в особенности в алгоритм Шора разложения числа на множители и вычисления дискретного логарифма, в квантовый алгоритм оценки фазы для нахождения собственных чисел унитарного оператора и алгоритмы для нахождения скрытой подгруппы.
Квантовое преобразование Фурье эффективно исполняется на квантовых компьютерах путём специального разложения матрицы в произведение более простых унитарных матриц. С помощью такого разложения, дискретное преобразование Фурье на входных амплитудах может быть осуществлено квантовой сетью, состоящей из вентилей Адамара и контролируемых квантовых вентилей, где — число кубитов[1]. По сравнению с классическим ДПФ, использующим элементов памяти ( — количество бит), что экспоненциально больше, чем квантовых вентилей КПФ.
Наилучшие из известных алгоритмов квантового преобразования Фурье (по состоянию на конец 2000) задействуют только вентилей для достижения желаемого приближения результата[2].
Определение
Квантовое преобразование Фурье — классическое дискретное преобразование Фурье, применённое к вектору амплитуд квантовых состояний. Обычно рассматривают такие вектора, имеющие длину . Классическое преобразование Фурье действует на вектор и отображает его в вектор по формуле:
Из унитарных свойств следует, что обратное к КПФ преобразование имеет матрицу, эрмитово-сопряжённую к матрице преобразования Фурье, поэтому . Если существует эффективная квантовая сеть, осуществляющая КПФ, то эта же сеть может быть запущена в обратную сторону для проведения обратного квантового преобразования Фурье. А это значит, что оба преобразования могут работать эффективно на квантовом компьютере.
Симуляции квантовых сетей двух возможных вариантов 2-кубитового КПФ, использующего и , показаны для демонстрации идентичного результата (используется Q-Kit).
Квантовая сеть КПФ с n кубитами (без изменения порядка выходных состояний). Использует понятие двоичного разложения, введённое ниже.
В преобразовании используются только линейные квантовые операции, чтобы задание функции для каждого из базисных состояний позволяло определить смешанные состояния из линейности. Это отличается от определения состояний в обычном преобразовании Фурье. Задать преобразование Фурье в обычном смысле — описать то, как получается результат для произвольных входных данных. Но здесь, как и во многих других случаях, проще описать поведение конкретного базисного состояния и вычислять результат из линейности.
Сеть КПФ можно построить для любого числа входных амплитуд N; однако, это проще всего сделать в случае . Тогда получается Ортонормированная система из векторов
Базисные состояния перечисляют все возможные состояния кубитов:
где, по правилу тензорного суммирования, означает, что кубит находится в состоянии , с 0 либо 1. По соглашению, индекс базисного состояния указывает на возможные состояния этого кубита, то есть является двоичным разложением:
Также удобно использовать дробную двоичную нотацию:
Например, и
Используя эти обозначения, КПФ записывается коротко[5]:
или
Краткость налицо, представив двоичное разложение обратно в виде суммы
Видно, что выходной кубит 1 находится в суперпозиции состояний и , кубит 2 — в суперпозиции и и т. д. для остальных кубитов (см. схему-рисунок выше).
Другими словами, ДПФ, операция над n кубитами, может быть разложена в тензорное произведениеn однокубитных операций,
Действительно, каждая из таких однокубитных операций эффективным образом реализуется на вентилях с контролируемой фазой и вентилях Адамара. Первый кубит потребует один вентиль Адамара и (n-1) вентилей с контролируемой фазой, второй потребует два вентиля Адамара и (n-2) вентилей с контролируемой фазой, и так далее (см. схему выше). В итоге потребуется вентилей, что квадратично полиномиально по отношению к количеству кубитов.
Пример
Рассмотрим квантовое преобразование Фурье на трёх кубитах. Математически оно записывается
где — простейший восьмой корень из единицы, удовлетворяющий (поскольку ).
Для сокращения, установим , тогда матричное представление КПФ на трёх кубитах
Это можно упростить, заметив , , , , и .
3-кубитное квантовое преобразование Фурье перепишется в виде
или
Для использования сети составим разложение КПФ в обратном порядке, а именно
На рисунке ниже представлена сеть для (с обратным порядком выходных кубитов по отношению к прямому КПФ).
КПФ для 3 кубитов (инвертированный порядок выходных кубитов)Возможная реализация 3-кубитной сети КПФ в Q-Kit
Как подсчитано выше, используется вентилей, что соответствует .
Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.
2019-2025 WikiSort.ru - проект по пересортировке и дополнению контента Википедии