Квантове Фур’є Перетворення, Крок за Кроком

Та сама трансформація, зовсім інша машина

Квантова Фур’є Трансформація (QFT) обчислює точно дискретну Фурієву трансформацію, яку ви вже знаєте з обробки сигналів – вона відображає вектор N = 2ⁿ комплексних амплітуд у інший вектор із N амплітудами, пов’язаними тим самим комплексним експоненційним ядром, як і класична DFT. Що змінюється – це те, де живуть ці амплітуди. Класичний FFT зберігає N чисел в масиві; QFT діє на N амплітуд, закодованих неявно через суперпозицію лише n кубітів, і робить це за допомогою схеми з лише O(n²) елементарними гейтами – поліноміально відносно кількості кубітів, експоненційно менше ніж N log N = n·2ⁿ операцій, необхідних FFT для звернення до кожної амплітуди безпосередньо.

Визначення

Вхідні дані визначаються як базисна станом |j⟩, де j знаходиться в діапазоні від 0 до N-1. QFT виробляє конкретну суперпозицію над усіма базовими станами |k⟩, зважену комплексним фазом, що залежить від добутку jk:

QFT |j⟩ = (1/√N) Σ_{k=0}^{N-1} e^(2πi·jk/N) |k⟩ N = 2^n, j і k є n-бітними цілими числами від 0 до N-1 кожна амплітуда виходу має РІВНУ величину 1/√N - лише фаза змінюється Зверніть увагу, що кожна амплітуда виходу має однакову величину - вся інформація, яку несе перетворення, упакована повністю в фази, а не в ймовірності наївного вимірювання. Це як сила, так і обмеження QFT: пряме вимірювання перетвореного стану викидає майже всю цю фазну інформацію, тому QFT ніколи не використовується як самостійний інструмент "читання спектру" - він завжди є одним етапом всередині більшого алгоритму, який подальші зміни фаз перед будь-яким вимірюванням.

QFT |j⟩  =  (1/√N)  Σ_{k=0}^{N-1}  e^(2πi·jk/N)  |k⟩

N = 2^n,  j and k are n-bit integers 0 .. N-1
every output amplitude has EQUAL magnitude 1/√N - only the phase varies

Будуємо його з Hadamardів та керованих фаз

Схема, що реалізує QFT на n кубітах, є щільною, повторюваною: для кожного кубіта застосовуйте гейт Гадамарда, а потім ланцюг керованих фазових поворотів R_k = diag(1, e^(2πi/2^k)), керований кожним кубітом, який ще залишається, з кутовою відстанню повороту, що зменшується вдвічі кожного разу, коли ви переміщуєтесь далі від одного кубіта:

для кубіта q = 0 .. n-1: застосуйте гейт Гадамарда до кубіта q для кожного кубіта q', що йде після q (відстань d = q'-q): застосуйте керований поворот R_{d+1} від кубіта q' на кубіт q (додає фазу 2π / 2^(d+1), умовно, якщо q' дорівнює 1) нарешті: переверніть порядок кубітів за допомогою гейтів SWAP Кожен кубіт Гадамарда поміщає його в суперпозицію; керовані повороти, що йдуть після нього, виправляють фазу суперпозиції, використовуючи стан кожного кубіта, який ще залишається, точно закодований бінарне розширення вхідного j у ланцюговий малюнок кутових відстаней. Кількість лічильних гейтів: кубіт 0 потребує одного гейта Гадамарда та n-1 керованих поворотів, кубіт 1 потребує одного гейта Гадамарда та n-2 поворотів, і так далі вниз до останнього кубіта з одним гейтом Гадамарда - трикутна сума, яка в цілому становить O(n²) гейтів, плюс ⌊n/2⌋ обміни наприкінці для повернення кубітів у стандартний порядок.

for qubit q = 0 .. n-1:
    apply H to qubit q
    for each qubit q' after q (distance d = q'-q):
        apply controlled-R_{d+1} from qubit q' onto qubit q
            (adds a phase of 2π / 2^(d+1) conditioned on q' being 1)
finally: reverse the qubit order with SWAP gates

Як виникає швидкість і де вона зупиняється

Експоненційний проміжок між O(n²) та O(n·2ⁿ) здається безкоштовним обідом, але він має два умови, які тихо відновлюють баланс для звичайних застосувань. По-перше, вам потрібно завантажити N амплітуд вхідних даних у квантовий стан - якщо потрібно закодувати N класичних чисел на рівні кубіта за рівнем, цей етап завантаження сам по собі коштує O(N), стерши перевагу до того, як навіть почне працювати QFT. По-друге, і більш тонко, ви не можете прочитати N вихідних амплітуд назад: вимірювання колапсує суперпозицію в один єдиний результат, відібраний з ймовірністю, що дорівнює квадратному амплітуді цього результату. QFT стає прибутковим лише тоді, коли проблема структурована таким чином, щоб одне або кілька вимірювань трансформованого стану точно розкрили потрібну відповідь - зазвичай періодичність або власну фазу - без необхідності зберігати весь спектр в класичній пам'яті.

Квантова фазова оцінка: як вона працює

Квантова фазова оцінка - це алгоритм, який використовує квантову обчислювальну машину для визначення значень власних станів унітарного оператора. Це робиться за допомогою застосування квантового перетворення (QFT) до реєстру експонент, що дозволяє зчитувати відповідний власний фазний стан з точності n біт.

Основна ідея полягає в тому, що QFT концентрує ймовірність на результатах, близьких до кратних розміру реєстру, поділеного на r (період модульної експоненціальної функції a^x mod N). Після цього можна виконати класичний алгоритм з продовженням дробу на результаті, щоб отримати значення r з високою ймовірністю.

Квантова фазова оцінка є ключовим компонентом алгоритму Шора, а також використовується в квантовій хімії та інших лінійних алгебраїчних квантових алгоритмах.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Quantum Fourier Transform і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.