Квантове перетворення Фур'є (КПФ) — це квантовий аналог класичного дискретного перетворення Фур'є: воно відображає базисний стан обчислення в рівномірну за величиною суперпозицію всіх базисних станів із фазами, що залежать від стану. Це одна з найважливіших підпрограм квантових обчислень: вона є рушієм алгоритму факторизації Шора та оцінювання квантової фази, тому швидкі й надійні схеми КПФ важливі для майбутніх квантових алгоритмів, здатних зламати сучасну криптографію.
КПФ|j⟩ = (1/√N) Σ_k e^(2πijk/N) |k⟩, де N = 8 у
цій симуляції. Обернене КПФ використовує спряжений показник,
e^(−2πijk/N), обертаючи кожну фазу у зворотному напрямку.
КПФ можна реалізувати лише за допомогою O((log N)²) квантових вентилів — експоненційно менше, ніж O(N log N) операцій, потрібних класичному швидкому перетворенню Фур'є. Але ви не можете просто «зчитати» перетворені амплітуди класично. Саме тому КПФ використовується як підпрограма всередині більших алгоритмів, таких як алгоритм Шора, а не як самостійний інструмент фур'є-аналізу.
Квантове перетворення Фур'є (КПФ) — квантовий аналог класичного дискретного перетворення Фур'є. Замість розкладання сигналу на частоти воно відображає базисний стан обчислення |j⟩ регістра кубітів у рівномірну за величиною суперпозицію кожного базисного стану |k⟩, де кожен доданок несе власну фазу e^(2πijk/N). Ця симуляція фіксує регістр із 3 кубітів (N = 8 станів), тож можна обрати будь-який вхід j, виконати перетворення в прямому чи зворотному напрямку та побачити точний розподіл вихідних фаз.
Оберіть вхідний стан за допомогою кнопок j = 0…7, натисніть перемикач режиму, щоб перейти між прямим і оберненим КПФ, і наведіть курсор (або клацніть) на стовпець вихідної амплітуди, щоб побачити її точну фазу на діаграмі фазора та в рядку показників знизу. Діаграма схеми праворуч показує, як послідовність вентилів Адамара та контрольованих фазових обертань реалізує перетворення.
КПФ — ключова підпрограма алгоритму факторизації Шора та оцінювання квантової фази, які лежать в основі багатьох інших квантових алгоритмів. Через це ефективна реалізація КПФ на реальному апаратному забезпеченні вважається однією з причин, чому квантові комп'ютери розглядають як майбутню загрозу для криптографії з відкритим ключем, як-от RSA.
Квантове перетворення Фур'є — це аналог класичного дискретного перетворення Фур'є у квантових обчисленнях. Замість розкладання сигналу на частоти воно відображає базисний стан обчислення |j⟩ регістра кубітів у суперпозицію однакової величини кожного базисного стану |k⟩, де кожен доданок несе власну фазу e^(2πijk/N). Ця симуляція фіксує регістр із 3 кубітів (N = 8 станів), тож можна обрати будь-який вхід j, виконати перетворення в прямому чи зворотному напрямку та побачити, як саме розподіляються вихідні фази.
КПФ рідко застосовується самостійно — його справжня цінність полягає в тому, що це будівельний блок. Це ключова підпрограма алгоритму Шора для факторизації великих чисел та оцінювання квантової фази, яке лежить в основі багатьох інших квантових алгоритмів. Оскільки факторизація є математичною основою шифрування RSA, ефективне, стійке до похибок КПФ — одна з причин, чому квантові комп'ютери сприймають як серйозну майбутню загрозу для сучасної криптографії.
Для чого використовується квантове перетворення Фур'є?
Це базова підпрограма алгоритму факторизації Шора та оцінювання квантової фази, яке саме живить алгоритми для симуляції хімії, задач власних значень та інших. Воно рідко застосовується самостійно — майже завжди є частиною більшого квантового алгоритму.
Чому всі вихідні стовпці мають однакову висоту?
Тому що КПФ відображає будь-який базисний стан у рівномірну суперпозицію: кожна вихідна амплітуда має точно однакову величину, 1/√8 ≈ 0,354, для цього регістру з 3 кубітів. Відрізняється лише фаза між вихідними станами, тому стовпці зафарбовані по-різному, але ніколи не мають різного розміру.
У чому різниця між прямим і оберненим КПФ?
Пряме КПФ використовує фазу e^(2πijk/N); обернене КПФ⁻¹ використовує комплексно спряжену величину, e^(−2πijk/N). Величини залишаються однаковими в обох випадках — змінюється лише напрямок обертання кожної фази, що є саме тим, що потрібно для «скасування» перетворення.
Ця сторінка обчислює точні амплітуди КПФ аналітично за наведеною вище формулою — це математично точний результат, а не наближення. Вона не симулює колапс квантового вимірювання чи шумове апаратне забезпечення; вона показує чисті, ідеальні амплітуди, які видав би ідеальний квантовий комп'ютер.
Три кубіти (N = 8 базисних станів) — це достатньо велике число, щоб побачити справді різні фази між виходами, але водночас достатньо мале, щоб чітко намалювати кожен стовпець, фазу та вентиль на екрані. Та сама формула масштабується до будь-якого N = 2^n; більші регістри означають лише дрібніші кроки фази та більше кубітів на діаграмі схеми.
Схема — це стандартне розкладання КПФ на вентилі Адамара (які створюють суперпозицію) та контрольовані фазові обертання R₂, R₃ (які застосовують фазу, залежну від j·k, біт за бітом), що завершується свопами, які відновлюють природний порядок кубітів. Перемноживши цю послідовність вентилів, отримуємо точно формулу КПФ.
Вимірювання квантового регістра колапсує його до одного базисного стану з імовірністю, що дорівнює квадрату величини його амплітуди — а оскільки кожен |k⟩ тут має однакову величину, пряме вимірювання взагалі не дає інформації про фази. Саме тому КПФ використовують усередині алгоритмів, заснованих на інтерференції, а не як спосіб безпосередньо отримати фур'є-спектр.
Ні. Для будь-якого вхідного стану |j⟩ усі 8 вихідних амплітуд зберігають точно однакову величину, 1/√8. Зміна j лише перерозподіляє, який вихідний стан отримує яку фазу — по суті зсуваючи патерн фази на 2πj/8 між сусідніми значеннями k — вона ніколи не робить один вихід більш чи менш імовірним за інший.
Квантове перетворення Фур'є (КПФ) — квантовий аналог класичного дискретного перетворення Фур'є. Замість розкладання сигналу на частоти воно відображає базисний стан обчислення |j⟩ регістра кубітів у суперпозицію однакової величини кожного базисного стану |k⟩, де кожен доданок несе власну фазу e^(2πijk/N). Ця симуляція фіксує регістр із 3 кубітів (N = 8 станів), тож можна обрати будь-який вхід j, виконати перетворення в прямому чи зворотному напрямку та побачити, як саме розподіляються вихідні фази. КПФ рідко застосовується самостійно — його справжня цінність у тому, що це будівельний блок усередині алгоритму Шора для факторизації великих чисел та оцінювання квантової фази, яке лежить в основі багатьох інших квантових алгоритмів.
Симуляція фіксує регістр із 3 кубітів, тож існує N = 8 базисних станів від |0⟩ до |7⟩. Вибір вхідного стану j та вихідного стану k задає фазу θ = 2πjk/N (пряме перетворення) або −2πjk/N (обернене). Кожна вихідна амплітуда має однакову величину 1/√8 — рівномірна суперпозиція — змінюється лише фаза, яка на діаграмі стовпців показана кольором (відтінком) залежно від j і k.
Кнопки j = 0…7 обирають вхідний базисний стан, що перетворюється. Перемикач у верхній панелі перемикає між прямим КПФ і оберненим КПФ⁻¹. Наведіть курсор або клацніть по стовпцю вихідної амплітуди, щоб перевірити точну фазу цього стану |k⟩ на діаграмі фазора та в рядку показників, а діаграма схеми праворуч показує вентилі Адамара й контрольовані фазові обертання, з яких складається перетворення.
КПФ можна реалізувати лише за допомогою O((log N)²) квантових вентилів — експоненційно менше, ніж O(N log N) операцій, потрібних класичному швидкому перетворенню Фур'є. Але зчитати перетворені амплітуди класично неможливо: вимірювання руйнує суперпозицію, зберігаючи лише ймовірність, пропорційну квадрату величини амплітуди. Саме тому КПФ використовують як підпрограму всередині більших алгоритмів, як-от алгоритм Шора, а не як самостійний інструмент фур'є-аналізу.
Це базова підпрограма алгоритму факторизації Шора та оцінювання квантової фази, яке саме живить алгоритми для симуляції хімії, задач власних значень та інших. Воно рідко застосовується самостійно — майже завжди є частиною більшого квантового алгоритму.
Тому що КПФ відображає будь-який базисний стан у рівномірну суперпозицію: кожна вихідна амплітуда має точно однакову величину, 1/√8 ≈ 0,354, для цього регістру з 3 кубітів. Відрізняється лише фаза між вихідними станами, тому стовпці зафарбовані по-різному, але ніколи не мають різного розміру.
Пряме КПФ використовує фазу e^(2πijk/N); обернене КПФ⁻¹ використовує комплексно спряжену величину, e^(−2πijk/N). Величини залишаються однаковими в обох випадках — змінюється лише напрямок обертання кожної фази, що є саме тим, що потрібно для «скасування» перетворення.
Ця сторінка обчислює точні амплітуди КПФ аналітично за наведеною вище формулою — це математично точний результат, а не наближення. Вона не симулює колапс квантового вимірювання чи шумове апаратне забезпечення; вона показує чисті, ідеальні амплітуди, які видав би ідеальний квантовий комп'ютер.
Три кубіти (N = 8 базисних станів) — це достатньо велике число, щоб побачити справді різні фази між виходами, але водночас достатньо мале, щоб чітко намалювати кожен стовпець, фазу та вентиль на екрані. Та сама формула масштабується до будь-якого N = 2^n; більші регістри означають лише дрібніші кроки фази та більше кубітів на діаграмі схеми.
Схема — це стандартне розкладання КПФ на вентилі Адамара (які створюють суперпозицію) та контрольовані фазові обертання R₂, R₃ (які застосовують фазу, залежну від j·k, біт за бітом), що завершується свопами, які відновлюють природний порядок кубітів. Перемноживши цю послідовність вентилів, отримуємо точно формулу КПФ.
Вимірювання квантового регістра колапсує його до одного базисного стану з імовірністю, що дорівнює квадрату величини його амплітуди — а оскільки кожен |k⟩ тут має однакову величину, пряме вимірювання взагалі не дає інформації про фази. Саме тому КПФ використовують усередині алгоритмів, заснованих на інтерференції, а не як спосіб безпосередньо отримати фур'є-спектр.
Ні. Для будь-якого вхідного стану |j⟩ усі 8 вихідних амплітуд зберігають точно однакову величину, 1/√8. Зміна j лише перерозподіляє, який вихідний стан отримує яку фазу — по суті зсуваючи патерн фази на 2πj/8 між сусідніми значеннями k — вона ніколи не робить один вихід більш чи менш імовірним за інший.