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

Изменение основы, применяемой в квантовых вычислениях

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

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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}}}$

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

${\displaystyle 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}}}$

Характеристики

Унитарность

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

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

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

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

${\displaystyle 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}}}$

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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).}$

Чтобы получить это состояние из схемы, изображенной выше, необходимо выполнить операцию замены кубитов, чтобы изменить их порядок. В большинстве случаев требуются замены. ^[2] ${\displaystyle n/2}$

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

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

Пример

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

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

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

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

${\displaystyle 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-кубитное квантовое преобразование Фурье можно переписать как:

${\displaystyle {\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).}$

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

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

Связь с квантовым преобразованием Адамара

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

Рекомендации

1. Копперсмит, Д. (1994). «Приблизительное преобразование Фурье, полезное при квантовом факторинге». Технический отчет RC19642, IBM . arXiv : Quant-ph/0201067 .
2. Майкл Нильсен и Исаак Чуанг (2000). Квантовые вычисления и квантовая информация . Кембридж: Издательство Кембриджского университета. ISBN 0-521-63503-9. ОКЛК  174527496.
3. Хейлз, Л.; Халлгрен, С. (12–14 ноября 2000 г.). «Улучшенный алгоритм квантового преобразования Фурье и его приложения». Материалы 41-го ежегодного симпозиума по основам информатики . стр. 515–525. CiteSeerX 10.1.1.29.4161 . дои : 10.1109/SFCS.2000.892139. ISBN  0-7695-0850-2. S2CID  424297.
4. Фаулер, AG; Девитт, С.Дж.; Холленберг, LCL (1 июля 2004 г.). «Реализация алгоритма Шора на линейном массиве кубитов ближайшего соседа». Квантовая информация и вычисления . 4 (4): 237–251. дои : 10.26421/QIC4.4-1. ISSN  1533-7146.
5. Маслов, Дмитрий (15 ноября 2007 г.). «Линейный стабилизатор глубины и схемы квантового преобразования Фурье без вспомогательных кубитов в квантовых архитектурах с конечными соседями». Физический обзор А. 76 (5): 052310. arXiv : quant-ph/0703211 . doi : 10.1103/PhysRevA.76.052310. S2CID  18645435.
6. Фурье-анализ булевых карт – Учебное пособие –, стр. 12-13.
7. Лекция 5: Основные квантовые алгоритмы, Раджат Миттал, стр. 4-5.

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

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

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