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

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

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

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

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

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

Определение

Квантовое преобразование Фурье — это классическое дискретное преобразование Фурье, применяемое к вектору амплитуд квантового состояния, который имеет длину, если он применяется к регистру кубитов. ${\displaystyle N=2^{n}}$ ${\displaystyle 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 _{j=0}^{N-1}x_{j}\omega _{N}^{-jk},\quad k=0,1,2,\ldots ,N-1,}$

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

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

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

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

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

${\displaystyle x_{j}={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}y_{k}\omega _{N}^{-jk},\quad j=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 .}$

Эквивалентно, квантовое преобразование Фурье можно рассматривать как унитарную матрицу (или квантовый вентиль ), действующую на векторы квантового состояния, где унитарная матрица является матрицей DFT ${\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_{j}\rangle =\left({\frac {1}{\sqrt {2}}}\right)\left(|0\rangle +e^{2\pi ix_{j}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).}$

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

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

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

Пример

Квантовое преобразование Фурье на трех кубитах, при этом , представлено следующим преобразованием: ${\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 кубитов параллельно. ^{[10] [11]} Алгоритм Шора использует оба типа преобразований Фурье, начальное преобразование Адамара, а также QFT. ${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$ ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$

Для других групп

Преобразование Фурье можно сформулировать для групп, отличных от циклической группы , и распространить на квантовую среду. ^[12] Например, рассмотрим симметрическую группу . ^{[13] [14]} Преобразование Фурье можно выразить в матричной форме ${\displaystyle S_{n}}$

${\displaystyle {\mathfrak {F}}_{n}=\sum _{\lambda \in \Lambda _{n}}\sum _{p,q\in {\mathcal {P}}(\lambda )}\sum _{g\in S_{n}}{\sqrt {\frac {d_{\lambda }}{n!}}}[\lambda (g)]_{q,p}|\lambda ,p,q\rangle \langle g|}$

где — элемент матричного представления , — множество путей от корневого узла до в диаграмме Браттели , — множество представлений , индексированных диаграммами Юнга, и — перестановка. ${\displaystyle [\lambda (g)]_{q,p}}$ ${\displaystyle (q,p)}$ ${\displaystyle \lambda (g)}$ ${\displaystyle {\mathcal {P}}(\lambda )}$ ${\displaystyle \lambda }$ ${\displaystyle S_{n}}$ ${\displaystyle \Lambda _{n}}$ ${\displaystyle S_{n}}$ ${\displaystyle g}$

Над конечным полем

Дискретное преобразование Фурье также может быть сформулировано над конечным полем , и может быть определена квантовая версия. ^[15] Здесь . Пусть будет произвольным линейным отображением (например, следом). Тогда для каждого определить ${\displaystyle F_{q}}$ ${\displaystyle N=q=p^{n}}$ ${\displaystyle \phi :GF(q)\rightarrow GF(p)}$ ${\displaystyle x\in GF(q)}$

${\displaystyle F_{q,\phi }:|x\rangle \mapsto {\frac {1}{\sqrt {q}}}\sum _{y\in GF(q)}\omega ^{\phi (xy)}|y\rangle }$

для и расширяются линейно. ${\displaystyle \omega =e^{2\pi i/p}}$ ${\displaystyle F_{q,\phi }}$

Ссылки

1. Копперсмит, Д. (2002). Приближенное преобразование Фурье, полезное в квантовой факторизации (Препринт). arXiv : quant-ph/0201067 .
2. Дрейпер, Томас Г. (7 августа 2000 г.). «Сложение на квантовом компьютере». arXiv : quant-ph/0008033 .
3. Руис-Перес, Лидия; Хуан Карлос, Гарсия-Эскартин (2 мая 2017 г.). «Квантовая арифметика с квантовым преобразованием Фурье». Квантовая обработка информации . 16 (6): 152. arXiv : 1411.5949v2 . Bibcode : 2017QuIP...16..152R. doi : 10.1007/s11128-017-1603-1. S2CID  10948948.
4. Шахин, Энгин (2020). «Квантовые арифметические операции, основанные на квантовом преобразовании Фурье над знаковыми целыми числами». Международный журнал квантовой информации . 18 (6): 2050035. arXiv : 2005.00443v3 . doi : 10.1142/s0219749920500355. ISSN  1793-6918.
5. Нильсен, Майкл А.; Чуан, Айзек Л. (2012). Квантовые вычисления и квантовая информация . doi :10.1017/CBO9780511976667. ISBN 978-1-107-00217-3.
6. Хейлз, Л.; Холлгрен, С. (12–14 ноября 2000 г.). «Улучшенный алгоритм квантового преобразования Фурье и его применение». Труды 41-го ежегодного симпозиума по основам компьютерной науки . С. 515–525. CiteSeerX 10.1.1.29.4161 . doi :10.1109/SFCS.2000.892139. ISBN  0-7695-0850-2. S2CID  424297.
7. Кургалин, Сергей; Борзунов, Сергей (2021). Краткое руководство по квантовым вычислениям: алгоритмы, упражнения и реализации . Тексты по информатике. Cham: Springer. ISBN 978-3-030-65054-4.
8. Фаулер, AG; Девитт, SJ; Холленберг, LCL (июль 2004 г.). «Реализация алгоритма Шора на линейном массиве кубитов ближайшего соседа». Квантовая информация и вычисления . 4 (4): 237–251. doi :10.26421/QIC4.4-1.
9. Маслов, Дмитрий (15 ноября 2007 г.). "Линейный стабилизатор глубины и квантовые схемы преобразования Фурье без вспомогательных кубитов в квантовых архитектурах с конечным числом соседей". Physical Review A. 76 ( 5): 052310. arXiv : quant-ph/0703211 . Bibcode : 2007PhRvA..76e2310M. doi : 10.1103/PhysRevA.76.052310. S2CID  18645435.
10. Анализ Фурье булевых отображений – Учебное пособие –, стр. 12-13 ^{[ необходима полная ссылка ]}
11. Лекция 5: Базовые квантовые алгоритмы, Раджат Миттал, стр. 4-5 ^{[ мертвая ссылка ]}
12. Мур, Кристофер; Рокмор, Дэниел; Рассел, Александр (2003). Общие квантовые преобразования Фурье (Препринт). arXiv : quant-ph/0304064 .
13. Кавано, Ясухито; Сэкигав, Хироши (июль 2016 г.). «Квантовое преобразование Фурье над симметричными группами — улучшенный результат». Журнал символических вычислений . 75 : 219–243. doi :10.1016/j.jsc.2015.11.016.
14. Билс, Роберт (1997). "Квантовое вычисление преобразований Фурье над симметричными группами". Труды двадцать девятого ежегодного симпозиума ACM по теории вычислений - STOC '97 . стр. 48–53. doi :10.1145/258533.258548. ISBN 0-89791-888-6.
15. de Beaudrap, Niel; Cleve, Richard; Waltrous, John (8 ноября 2002 г.). «Точные квантовые и классические разделения сложности запросов». Algorithmica . 34 (4): 449–461. doi :10.1007/s00453-002-0978-1.

Дальнейшее чтение

• Партасарати, КР (2006). Лекции по квантовым вычислениям, квантовым кодам коррекции ошибок и теории информации . Институт фундаментальных исследований Тата. ISBN 978-81-7319-688-1.
• Прескилл, Джон (сентябрь 1998 г.). «Конспект лекций по физике 229: Квантовая информация и вычисления» (PDF) .

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

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