Действительно ли квантовое преобразование Фурье экспоненциально быстрее классического преобразования, и почему оно позволяет квантовому компьютеру решать сложные задачи?

/ / Опубликовано в Квантовая информация, EITC/QI/QIF Основы квантовой информации, Квантовое преобразование Фурье, Свойства квантового преобразования Фурье.

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

## Классическое дискретное преобразование Фурье (ДПФ)

Классическое дискретное преобразование Фурье (ДПФ) — это математическая операция, преобразующая вектор комплексных чисел в другой вектор той же размерности, представляющий частотные компоненты исходного вектора. ДПФ N-мерный вектор х = (х_0, х_1, ..., х_{N-1}) дан кем-то:

    \[ \tilde{x}_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{2\pi i jk/N}, \quad k = 0, 1, ..., N-1 \]

Наивная реализация ДПФ требует О (N ^ 2) время, потому что каждый выходной элемент включает сумму по всем N входные элементы, и есть N выходы.

Однако быстрое преобразование Фурье (БПФ), классический алгоритм, уменьшает эту сложность до O(N \log N) путём рекурсивного разложения ДПФ на более мелкие ДПФ. БПФ — один из самых известных алгоритмов в вычислительной науке, лежащий в основе приложений от обработки сигналов до численного анализа.

## Квантовое преобразование Фурье (КПФ): определение и сложность схемы

Квантовое преобразование Фурье — это квантовый аналог классического ДПФ, действующий на квантовые состояния. n-кубитная система, где N = 2^n, QFT — это линейный оператор, определяемый следующим образом:

    \[ |x\rangle \mapsto \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i xk/N} |k\rangle \]

для x in 0, 1, ..., N-1.

Реализация квантовой теории поля (КТП) в виде квантовой схемы особенно эффективна. Её можно разложить на последовательность вентилей Адамара и вентилей с управляемым фазовым сдвигом. Глубина и размер схемы могут быть различными. O (N ^ 2)т.е. O((\log N)^2), Где n это количество кубитов и N = 2^n — размерность гильбертова пространства.

Подробное описание схемы

Для n-кубитный регистр, схема QFT обычно состоит из:

1. Вентиль Адамара на самом значимом кубите.
2. Контролируемые фазовые сдвиги между наиболее значимым кубитом и каждым менее значимым кубитом с фазой е^{2\пи i/2^k} для k-й контроль.
3. Рекурсия по оставшемуся п-1 кубиты.
4. Окончательное изменение порядка кубитов (обменные вентили).

Общее количество вентилей для точного квантового преобразования Фурье равно O (N ^ 2)Однако, если допустима небольшая ошибка (что часто достаточно для квантовых алгоритмов), можно аппроксимировать КТП с точностью \эпсилон с использованием только O(n \log n + \log n \log(1/\epsilon)) шлюзы, что еще больше снижает потребность в ресурсах.

Сравнение вычислительной сложности

– Классическое БПФ: O(N \log N) = О(2^нн)
– Квантовая КТП: O (N ^ 2) Ворота

Переводя эти сложности в те же единицы, QFT работает в O(\log^2 N) квантовых вентилей, тогда как для БПФ требуется O(N \log N) Классические операции. Это экспоненциальное увеличение количества необходимых базовых операций, по крайней мере, относительно размера входных данных, измеряемого в битах (n = \log N).

## QFT сам по себе экспоненциально быстрее?

Хотя квантовое преобразование Фурье (КТФ) может быть реализовано экспоненциально быстрее классического БПФ при измерении ресурсов по количеству базовых квантовых вентилей в сравнении с классическими операциями, важно проанализировать, что это означает для практических вычислений. Экспоненциальное ускорение относится к сложности внутренней схемы: КТФ отображает всю суперпозицию N амплитуды, используя только O (N ^ 2) вентили. Однако квантовое измерение сводит квантовое состояние к единственному результату, ограничивая прямое извлечение всех выходных амплитуд.

Если кто-то заинтересован в вычислении всех N Для выходных амплитуд квантовой теории поля (КТП) это не было бы быстрее на квантовом компьютере, поскольку за один запуск можно наблюдать только один результат измерения, а реконструкция полного спектра потребовала бы экспоненциально большего числа повторений. Следовательно, экспоненциальное ускорение заключается не в вычислении *всех* выходных значений, а в преобразовании квантовой информации в рамках квантового алгоритма.

## Роль КТП в квантовых алгоритмах

КТП — ключевая подпрограмма в нескольких квантовых алгоритмах, обеспечивающих экспоненциальное или суперполиномиальное ускорение по сравнению с наиболее известными классическими алгоритмами. Наиболее ярким примером является алгоритм Шора для факторизации целых чисел.

Алгоритм Шора

Алгоритм Шора использует квантовую теорию поля (КТП) для нахождения периода функции (нахождение периода), который затем применяется для разложения больших целых чисел на множители. Алгоритм работает следующим образом:

1. Подготовить равномерную суперпозицию по N состояния.
2. Вычислить функцию f(x) = a^x \mod N в суперпозиции.
3. Измерьте второй регистр, свернув состояние в суперпозицию входов, все из которых соответствуют измеренному выходу.
4. Применяем квантовое преобразование Фурье к первому регистру, которое преобразует периодическую структуру в суперпозицию, где измерение дает информацию о периоде.
5. Используйте измеренный результат и классическую постобработку (цепные дроби) для восстановления периода и разложения целого числа на множители.

КТФ экспоненциально быстрее классического БПФ с точки зрения количества базовых операций преобразования. Эта эффективность *важна* для полиномиальной производительности алгоритма Шора.

Скрытые проблемы подгрупп

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

## Ограничения и заблуждения

Важно осознавать тонкости утверждения о том, что КТП экспоненциально быстрее классического БПФ:

– Эффективное преобразование, а не эффективная выборка: КТП эффективно преобразует квантовое состояние, но квантовый компьютер не может вывести всё преобразованное состояние. Измерение даёт выборку из распределения вероятностей, определяемого квадратами амплитуд. Для многих приложений этого достаточно, поскольку квантовый алгоритм разработан таким образом, чтобы вероятность измерения полезного результата была высокой.
– Классическая реконструкция выходных данных: Если цель состоит в том, чтобы вычислить и вывести все N В классическом смысле квантовая теория поля (КТП) не помогает; за один прогон можно получить только квантовую выборку. Таким образом, экспоненциальная эффективность КТП полезна в квантовых алгоритмах, а не для прямого классического вычисления всех значений преобразования.
– Не все проблемы: Сама по себе квантовая теория поля (КТП) не делает все классически сложные задачи разрешимыми. Её применение специфично для тех классов задач, где квантовая когерентность и интерференция в сочетании с КТП позволяют эффективно извлекать глобальные свойства (например, период).

## Пример: Поиск порядка и периодичность

Рассмотрим задачу нахождения периода, лежащую в основе алгоритма Шора:

Предположим, что дана функция f: \mathbb{Z}_N \to S который является периодическим с периодом rт.е. f(x) = f(x + r) для всех xЦель состоит в том, чтобы определить r.

Классически, находя r требуется О(\sqrt{N}) оценки f В худшем случае (для общих функций) этот процесс включает в себя:

1. Приготовление равномерной суперпозиции \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle.
2. Вычисления F (X) в суперпозиции: \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle|f(x)\rangle.
3. Измерение второго регистра дает значение y, связывая первый регистр с подмножеством x с f(x) = y: \sum_{j} |x_0 + jr\rangle.
4. Применение квантовой теории поля преобразует это в суперпозицию с острым пиком в точках, кратных Н/р. Измерение урожайности k такой, что к/н приближает рациональное число со знаменателем r.
5. Классическая постобработка позволяет восстановить r.

Здесь решающее значение имеет экспоненциальная эффективность КТП: преобразование от периодичности во временной области к пикам в частотной области осуществляется с помощью полиномиально большого числа квантовых вентилей, тогда как классический поиск потребовал бы экспоненциально возрастающего времени по количеству входных битов.

## Приближенное квантовое преобразование Фурье

В практических приложениях, особенно с увеличением числа кубитов, часто достаточно использовать приближенный квантовый метод поля (КТП). Исключая вентили с управляемой фазой и очень малыми углами, КТП можно реализовать с помощью значительно меньшего количества вентилей, сохраняя при этом высокую точность. Это особенно полезно для устройств NISQ (Noisy Intermediate-Scale Quantum), где уменьшение количества вентилей помогает снизить влияние шума и декогеренции.

## Дальнейшие выводы

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

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

## Заключительные замечания

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

Другие недавние вопросы и ответы, касающиеся EITC/QI/QIF Основы квантовой информации:

Посмотреть больше вопросов и ответов в EITC/QI/QIF Quantum Information Fundamentals

Еще вопросы и ответы:

Теги: , , , , ,