Квантовое преобразование Фурье

В квантовых вычислениях квантовое преобразование Фурье (QFT) представляет собой линейное преобразование квантовых битов и является квантовым аналогом дискретного преобразования Фурье . Квантовое преобразование Фурье является частью многих квантовых алгоритмов , в частности алгоритма Шора для факторизации и вычисления дискретного логарифма , алгоритма оценки квантовой фазы для оценки собственных значений унитарного оператора и алгоритмов для проблемы скрытой подгруппы . Квантовое преобразование Фурье было открыто Доном Копперсмитом .

Квантовое преобразование Фурье можно эффективно выполнить на квантовом компьютере с разложением в произведение более простых унитарных матриц . Дискретное преобразование Фурье на $2^{n}$ амплитуды могут быть реализованы как квантовая схема, состоящая только из $O(n^{2})$ Ворота Адамара и с управляемым вентили фазовым сдвигом , где $n$ это количество кубитов. Это можно сравнить с классическим дискретным преобразованием Фурье, которое принимает $O(n2^{n})$ ворота (где $n$ — количество бит), что экспоненциально больше, чем $O(n^{2})$.

Квантовое преобразование Фурье действует на вектор квантового состояния ( квантовый регистр ), а классическое дискретное преобразование Фурье действует на вектор. Оба типа векторов можно записать в виде списков комплексных чисел. В квантовом случае это последовательность амплитуд вероятности для всех возможных результатов измерения (результатами являются базисные состояния или собственные состояния ). Поскольку измерение сводит квантовое состояние к одному базисному состоянию, не каждая задача, использующая классическое преобразование Фурье, может воспользоваться преимуществами экспоненциального ускорения квантового преобразования Фурье.

Лучшие алгоритмы квантового преобразования Фурье, известные (по состоянию на конец 2000 г.), требуют всего лишь $O(n\log n)$ вентили для достижения эффективной аппроксимации при условии, что управляемый фазовый вентиль реализован как собственная операция.

Определение

Квантовое преобразование Фурье — это классическое дискретное преобразование Фурье, применяемое к вектору амплитуд квантового состояния, который обычно имеет длину $N=2^{n}$.

Классическое преобразование Фурье действует на вектор $(x_{0},x_{1},\ldots ,x_{N-1})\in \mathbb {C} ^{N}$ и сопоставляет его с вектором $(y_{0},y_{1},\ldots ,y_{N-1})\in \mathbb {C} ^{N}$ по формуле:

$y_{k}={\frac {1}{\sqrt {N}}}\sum _{n=0}^{N-1}x_{n}\omega _{N}^{-nk},\quad k=0,1,2,\ldots ,N-1,$

где $\omega _{N}=e^{\frac {2\pi i}{N}}$ и $\omega _{N}^{n}$ является корнем N-й степени из единицы .

Аналогично квантовое преобразование Фурье действует на квантовое состояние. ${\textstyle |x\rangle =\sum _{i=0}^{N-1}x_{i}|i\rangle }$ и отображает его в квантовое состояние ${\textstyle \sum _{i=0}^{N-1}y_{i}|i\rangle }$ по формуле:

$y_{k}={\frac {1}{\sqrt {N}}}\sum _{n=0}^{N-1}x_{n}\omega _{N}^{nk},\quad k=0,1,2,\ldots ,N-1,$

(Условия относительно знака показателя фазового фактора различаются; здесь квантовое преобразование Фурье имеет тот же эффект, что и обратное дискретное преобразование Фурье, и наоборот.)

С $\omega _{N}^{n}$ является вращением, обратное квантовое преобразование Фурье действует аналогично, но с:

$x_{n}={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}y_{k}\omega _{N}^{-nk},\quad n=0,1,2,\ldots ,N-1,$

В случае, если $|x\rangle$ является базовым состоянием, квантовое преобразование Фурье также можно выразить как отображение

${\text{QFT}}:|x\rangle \mapsto {\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}\omega _{N}^{xk}|k\rangle .$

Эквивалентно, квантовое преобразование Фурье можно рассматривать как унитарную матрицу (или квантовый вентиль ), действующую на векторы квантового состояния, где унитарная матрица $F_{N}$ это матрица ДПФ

$F_{N}={\frac {1}{\sqrt {N}}}{\begin{bmatrix}1&1&1&1&\cdots &1\\1&\omega &\omega ^{2}&\omega ^{3}&\cdots &\omega ^{N-1}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&\cdots &\omega ^{2(N-1)}\\1&\omega ^{3}&\omega ^{6}&\omega ^{9}&\cdots &\omega ^{3(N-1)}\\\vdots &\vdots &\vdots &\vdots &&\vdots \\1&\omega ^{N-1}&\omega ^{2(N-1)}&\omega ^{3(N-1)}&\cdots &\omega ^{(N-1)(N-1)}\end{bmatrix}}$

где $\omega =\omega _{N}$. Например, в случае $N=4=2^{2}$ и фаза $\omega =i$ матрица преобразования

$F_{4}={\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix}}$

См. Также: Обобщения матриц Паули § Конструкция: матрицы часов и сдвига.

Свойства

Унитарность

Большинство свойств квантового преобразования Фурье вытекают из того факта, что это унитарное преобразование . Это можно проверить, выполнив умножение матриц и убедившись, что соотношение $FF^{\dagger }=F^{\dagger }F=I$ держится, где $F^{\dagger }$ является сопряжением эрмитовым $F$. Альтернативно можно проверить, что ортогональные векторы нормы 1 отображаются в ортогональные векторы нормы 1.

Из унитарного свойства следует, что обратное квантовому преобразованию Фурье является эрмитовым сопряженным к матрице Фурье, таким образом $F^{-1}=F^{\dagger }$. Поскольку существует эффективная квантовая схема, реализующая квантовое преобразование Фурье, схему можно запустить в обратном порядке, чтобы выполнить обратное квантовое преобразование Фурье. Таким образом, оба преобразования могут быть эффективно выполнены на квантовом компьютере.

Схемная реализация

Квантовые вентили, используемые в схеме $n$ кубиты — это ворота Адамара и фазовые ворота. $R_{k}$:

$H={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}\qquad {\text{and}}\qquad R_{k}={\begin{pmatrix}1&0\\0&e^{i2\pi /2^{k}}\end{pmatrix}}$

Схема состоит из $H$ ворота и управляемая версия $R_{k}$:

Ортонормированный базис состоит из базисных состояний

$|0\rangle ,\ldots ,|2^{n}-1\rangle .$

Эти базисные состояния охватывают все возможные состояния кубитов:

$|x\rangle =|x_{1}x_{2}\ldots x_{n}\rangle =|x_{1}\rangle \otimes |x_{2}\rangle \otimes \cdots \otimes |x_{n}\rangle$

где с тензорного произведения обозначением $\otimes$, $|x_{j}\rangle$ указывает на то, что кубит $j$ находится в состоянии $x_{j}$, с $x_{j}$ либо 0, либо 1. По соглашению индекс базового состояния $x$ двоичное число, закодированное $x_{j}$, с $x_{1}$ самый значимый бит.

Действие ворот Адамара $H|x_{i}\rangle =\left({\frac {1}{\sqrt {2}}}\right)\left(|0\rangle +e^{2\pi ix_{i}2^{-1}}|1\rangle \right)$, где знак зависит от $x_{i}$.

Квантовое преобразование Фурье можно записать как тензорное произведение ряда слагаемых:

${\text{QFT}}(|x\rangle )={\frac {1}{\sqrt {N}}}\bigotimes _{j=1}^{n}\left(|0\rangle +\omega _{N}^{x2^{n-j}}|1\rangle \right).$

Использование дробной двоичной записи

$[0.x_{1}\ldots x_{m}]=\sum _{k=1}^{m}x_{k}2^{-k}.$

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

${\text{QFT}}(|x_{1}x_{2}\ldots x_{n}\rangle )={\frac {1}{\sqrt {N}}}\ \left(|0\rangle +e^{2\pi i\,[0.x_{n}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{n-1}x_{n}]}|1\rangle \right)\otimes \cdots \otimes \left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}\ldots x_{n}]}|1\rangle \right).$

Чтобы получить это состояние из схемы, изображенной выше, необходимо выполнить операцию замены кубитов, чтобы изменить их порядок. Максимум $n/2$ обмен обязателен.

Поскольку дискретное преобразование Фурье, операция над n кубитами, может быть учтено в тензорном произведении n однокубитных операций, его легко представить как квантовую схему (с точностью до изменения порядка вывода). Каждая из этих однокубитных операций может быть эффективно реализована с использованием одного вентиля Адамара и линейного числа управляемых фазовых вентилей . Первый член требует одного вентиля Адамара и $(n-1)$ управляемых фазовых вентилей, следующий член требует одного вентиля Адамара и $(n-2)$ управляемый фазовый вентиль, и каждый следующий член требует на один управляемый фазовый вентиль меньше. Суммирование количества вентилей, исключая те, которые необходимы для разворота выхода, дает $n+(n-1)+\cdots +1=n(n+1)/2=O(n^{2})$ Gates, который представляет собой квадратичный полином от числа кубитов.

Реализация квантового преобразования Фурье на уровне схемы в линейной архитектуре ближайшего соседа изучалась ранее. Глубина схемы линейно зависит от количества кубитов.

Применение

Арифметические операции

С небольшими модификациями QFT его также можно использовать для выполнения быстрых целочисленных арифметических операций, таких как сложение и умножение, на квантовом компьютере . Он также работает с суперпозиции и т. д. операциями целочисленной арифметики

Пример

Квантовое преобразование Фурье на трех кубитах: $F_{8}$ с $n=3,N=8=2^{3}$, представляется следующим преобразованием:

${\text{QFT}}:|x\rangle \mapsto {\frac {1}{\sqrt {8}}}\sum _{k=0}^{7}\omega ^{xk}|k\rangle ,$

где $\omega =\omega _{8}$ является корнем восьмой степени из единицы, удовлетворяющим $\omega ^{8}=\left(e^{\frac {i2\pi }{8}}\right)^{8}=1$.

Матричное представление преобразования Фурье для трех кубитов:

$F_{8}={\frac {1}{\sqrt {8}}}{\begin{bmatrix}1&1&1&1&1&1&1&1\\1&\omega &\omega ^{2}&\omega ^{3}&\omega ^{4}&\omega ^{5}&\omega ^{6}&\omega ^{7}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&1&\omega ^{2}&\omega ^{4}&\omega ^{6}\\1&\omega ^{3}&\omega ^{6}&\omega &\omega ^{4}&\omega ^{7}&\omega ^{2}&\omega ^{5}\\1&\omega ^{4}&1&\omega ^{4}&1&\omega ^{4}&1&\omega ^{4}\\1&\omega ^{5}&\omega ^{2}&\omega ^{7}&\omega ^{4}&\omega &\omega ^{6}&\omega ^{3}\\1&\omega ^{6}&\omega ^{4}&\omega ^{2}&1&\omega ^{6}&\omega ^{4}&\omega ^{2}\\1&\omega ^{7}&\omega ^{6}&\omega ^{5}&\omega ^{4}&\omega ^{3}&\omega ^{2}&\omega \\\end{bmatrix}}.$

3-кубитное квантовое преобразование Фурье можно переписать как:

${\text{QFT}}(|x_{1},x_{2},x_{3}\rangle )={\frac {1}{\sqrt {8}}}\ \left(|0\rangle +e^{2\pi i\,[0.x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{2}x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}x_{3}]}|1\rangle \right).$

На следующем эскизе показана соответствующая схема для $n=3$ (с обратным порядком выходных кубитов относительно правильного QFT):

Как подсчитано выше, количество используемых ворот равно $n(n+1)/2$ что равно $6$, для $n=3$.

Связь с

См. Также: Преобразование Адамара § Приложения квантовых вычислений

Используя обобщенное преобразование Фурье на конечных (абелевых) группах , на самом деле существует два естественных способа определить квантовое преобразование Фурье в с n -кубитами квантовом регистре . QFT, как определено выше, эквивалентно DFT, которое рассматривает эти n кубитов как индексированные циклической группой. $\mathbb {Z} /2^{n}\mathbb {Z}$. Однако также имеет смысл рассматривать кубиты как индексированные булевой группой. $(\mathbb {Z} /2\mathbb {Z} )^{n}$, и в этом случае преобразование Фурье является преобразованием Адамара . Это достигается путем применения вентиля Адамара к каждому из n кубитов. параллельного Алгоритм Шора использует оба типа преобразований Фурье: исходное преобразование Адамара, а также КТП.

Ссылки

• К. Р. Партасарати , Лекции по квантовым вычислениям и кодам, исправляющим квантовые ошибки (Индийский статистический институт, Делийский центр, июнь 2001 г.)
• Джон Прескилл , Конспект лекций по физике 229: Квантовая информация и вычисления (CIT, сентябрь 1998 г.)

Внешние ссылки

• Демонстрационный проект Wolfram: квантовая схема, реализующая алгоритм поиска Гровера
• Демонстрационный проект Wolfram: квантовая схема, реализующая квантовое преобразование Фурье
• Квантовое преобразование Фурье причуды онлайн-жизни