⚛️ Квантові обчислення
📅 Березень 2026⏱ 14 хв🔴 Просунутий · Останнє оновлення: 23 червня 2026 р.

Квантові алгоритми: Ґровер, Шор і квантова перевага

Класичний комп'ютер шукає в невпорядкованому списку з N елементів за час O(N). Квантовий алгоритм Ґровера робить це за O(√N). Алгоритм Шора розкладає число, факторизація якого класично має експоненційну складність, за поліноміальний час. Це не покращення — це принципово інші обчислювальні можливості, уможливлені квантовою суперпозицією та інтерференцією.

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

1. Модель квантової схеми

Квантовий комп'ютер оперує кубітами — дворівневими квантовими системами. На відміну від класичних бітів (0 або 1), кубіти можуть перебувати в довільних суперпозиціях:

Стан кубіта: |ψ⟩ = α|0⟩ + β|1⟩ α, β ∈ ℂ (комплексні амплітуди) Нормування: |α|² + |β|² = 1 Вимірювання: P(0) = |α|², P(1) = |β|² → колапсує до |0⟩ або |1⟩ n-кубітна система: Стан живе в гільбертовому просторі ℂ^(2ⁿ) (2ⁿ амплітуд) Приклад: 3 кубіти → 8 амплітуд: α₀₀₀|000⟩ + α₀₀₁|001⟩ + ... + α₁₁₁|111⟩ Ключові квантові вентилі: Адамар: H = (1/√2) [[1,1],[1,−1]] (створює рівну суперпозицію) Паулі-X: X = [[0,1],[1,0]] (вентиль NOT) Фазовий: S = [[1,0],[0,i]] (зсув фази на π/2) CNOT: інвертує цільовий кубіт, якщо керувальний = |1⟩ (заплутаність) Універсальність: {H, T, CNOT} є універсальним набором — будь-яку унітарну операцію можна наблизити з довільною точністю цими трьома вентилями.

2. Квантове перетворення Фур'є

Квантове перетворення Фур'є (QFT) — це квантовий аналог дискретного перетворення Фур'є, робоча конячка, що лежить в основі як алгоритму Шора, так і квантового оцінювання фази:

QFT на n кубітах: |j⟩ → (1/√N) Σ_{k=0}^{N-1} e^{2πijk/N} |k⟩ N = 2ⁿ Класичне DFT для N точок: O(N log N) з FFT Квантове QFT для N = 2ⁿ амплітуд: O(n²) = O((log N)²) вентилів Структура схеми: Застосувати Адамар до кубіта 1 (найстарший розряд) Застосувати вентилі керованого фазового повороту R_k = diag(1, e^{iπ/2^{k-1}}) Повторити для кожного кубіта Обернути порядок кубітів (вентилі SWAP) Усього: n(n+1)/2 однокубітних вентилів + n/2 вентилів SWAP Чому це швидше: QFT діє на 2ⁿ амплітуд одночасно через квантову суперпозицію. Класичне FFT має явно обчислити всі N виходів. QFT: O(n²) проти FFT: O(n·2ⁿ) — але вихід QFT не можна прочитати напряму → треба використовувати QFT як підпрограму, а не самостійний перетворювач.

3. Пошуковий алгоритм Ґровера

Лов Ґровер (1996) розробив алгоритм для пошуку позначеного елемента в невпорядкованій базі даних із N елементів. Класично це потребує в середньому O(N) запитів. Ґровер досягає O(√N):

Алгоритм Ґровера: 1. Ініціалізація: |ψ⟩ = H^⊗n |0⟩ᵑ (рівна суперпозиція всіх N станів) 2. Повторити O(√N) разів: a. Оракул: O|x⟩ = −|x⟩ якщо x збігається, +|x⟩ інакше (інвертує фазу амплітуди позначеного елемента) b. Дифузія: 2|ψ⟩⟨ψ| − I ("інверсія відносно середнього") (підсилює позначену амплітуду, зменшує інші) 3. Вимірювання → дає позначений елемент з імовірністю ≥ 1 − ε Геометрична картина: За ітерацію стан повертається на кут 2θ у напрямку позначеного стану, де sin θ = 1/√N. Оптимальна кількість ітерацій: t = (π/4) · √N N = 2²⁰ ≈ 10⁶: класично в середньому 500 000 запитів проти ~785 у Ґровера N = 2⁵⁶ ≈ 7×10¹⁶: класично в середньому 10¹⁷ запитів проти ~2×10⁸ у Ґровера Наслідок для безпеки: 128-бітний симетричний ключ (AES-128): класичний перебір 2¹²⁸ запитів Ґровер: 2⁶⁴ запитів → безпека AES-128 знижується до 64-бітної з квантом Рекомендація NIST: використовуйте AES-256, щоб зберегти 128-бітну квантову безпеку

4. Факторизаційний алгоритм Шора

Пітер Шор (1994) показав, що квантові комп'ютери можуть розкласти n-значне ціле число N на множники за O(n² log n log log n) вентилів — експоненційно швидше за найкращий відомий класичний алгоритм (загальне решето числового поля, субекспоненційне, але суперполіноміальне):

Огляд алгоритму Шора: Задача: розкласти N на множники (RSA-2048 використовує N із 617 десяткових цифр) Класична редукція (не квантова): 1. Якщо N парне → множник 2. 2. Перевірити, чи N = a^b для цілих a, b. 3. Обрати випадкове a < N з gcd(a, N) = 1. 4. Знайти r = період f(x) = aˣ mod N ← КВАНТОВА ПІДПРОГРАМА 5. Якщо r парне і a^(r/2) ≢ −1 (mod N): Множники: gcd(a^(r/2) ± 1, N) Квантова підпрограма знаходження періоду: a. Створити суперпозицію {|x⟩|f(x)⟩} для x = 0..2ⁿ−1 b. Виміряти другий регістр → колапс до одного значення f(x₀) = y c. Перший регістр: сума по всіх x із f(x) = y → періодичний стан d. Застосувати QFT → піки на кратних 2ⁿ/r e. Прочитати r з вимірювання Наслідки для RSA: Безпека RSA-2048 спирається на класичну складність факторизації. Відмовостійкий квантовий комп'ютер із ~4 000 "логічних" кубітів (що потребує мільйонів фізичних кубітів для корекції помилок) міг би зламати RSA-2048 за години. Постквантова криптографія (стандарти NIST PQC, 2024): CRYSTALS-Kyber (ML-KEM): ґраткова інкапсуляція ключів CRYSTALS-Dilithium (ML-DSA): ґраткові цифрові підписи FALCON: менший розмір підпису
Поточний стан (2024-2025): процесор IBM Heron r2 має 156 кубітів із покращеною зв'язністю. Чип Google Willow продемонстрував експоненційне зменшення помилок із масштабуванням поверхневого коду. Однак злам RSA-2048 потребував би мільйонів фізичних кубітів із корекцією помилок — мети, яка за нинішніми прогнозами лишається за ~10-15 років. Загроза Q-Day реальна, але не нагальна.

5. Варіаційні алгоритми: VQE і QAOA

Варіаційні квантові алгоритми — це гібридні квантово-класичні підходи, розроблені для близькочасного обладнання NISQ: вони толерують помірний шум і потребують менше кубітів, ніж відмовостійкі алгоритми:

Варіаційний квантовий розв'язувач власних значень (VQE): Мета: знайти енергію основного стану E₀ молекулярного гамільтоніана H. Класично: точна діагоналізація масштабується як O(2^{2N}) для N орбіталей. VQE: 1. Параметризована квантова схема |ψ(θ)⟩ = U(θ)|0⟩ 2. Виміряти E(θ) = ⟨ψ(θ)|H|ψ(θ)⟩ на квантовому обладнанні 3. Класичний оптимізатор (градієнтний спуск, COBYLA) → оновити θ 4. Повторювати до збіжності → E₀ ≈ E(θ*) Варіаційний принцип: E(θ) ≥ E₀ для всіх θ Застосування: розробка ліків (молекулярні енергії), матеріали для акумуляторів, проєктування каталізаторів фіксації азоту QAOA (Квантовий наближений алгоритм оптимізації): Мета: наближена комбінаторна оптимізація (MaxCut, TSP, згортання білків) QAOA з p шарами: чергування гамільтоніана задачі H_C та змішувача H_B: |γ,β⟩ = e^{-iβ_p H_B} e^{-iγ_p H_C} ··· e^{-iβ₁H_B} e^{-iγ₁H_C} |+⟩^⊗n Класично оптимізувати γ, β → максимізувати ⟨H_C⟩ Коефіцієнт наближення MaxCut: p→∞ → точно; p=1 → доведено > 0.6924 (класичний SDP Ґоманса-Вільямсона досягає 0.878)

6. Класи квантової складності

Ландшафт складності: P = задачі, розв'язні класично за поліноміальний час NP = задачі, перевірні класично за поліноміальний час BPP = класичний рандомізований поліноміальний час (практична класична межа) BQP = квантовий поліноміальний час (з обмеженою похибкою < 1/3) QMA = квантовий NP (квантовий аналог NP) Відомі розділення та вкладення: P ⊆ BPP ⊆ BQP ⊆ PSPACE P ⊆ NP; BPP ⊆ BQP NP і BQP: імовірно непорівнянні (жоден не є підмножиною іншого) Факторизація: Безперечно в BQP (поліноміальна квантово). Імовірно не в P (немає відомого поліноміального класичного алгоритму). Не NP-повна (факторизація в NP ∩ co-NP; NP-повнота означала б колапс). Ґровер: Неструктурований пошук: класично Ω(N) → квантово Θ(√N) Квадратичне прискорення. Не може розв'язати NP-повні задачі за поліноміальний час. (Це потребувало б поліноміальної кількості ітерацій × поліноміальної глибини схеми)

7. Епоха NISQ: шум, межі та реальність найближчого часу

Сьогоднішні квантові комп'ютери — це пристрої «зашумлених квантових систем проміжного масштабу» (NISQ) — термін Джона Прескілла для систем із 50-1000 кубітів, що працюють без повної відмовостійкості. Розуміння їхніх меж необхідне для реалістичних очікувань:

Перехід до постквантової криптографії: математичні прискорення від Шора в принципі певні, навіть якщо апаратна реалізація далека. Стандартизація постквантової криптографії NIST (2024) дала перші квантово-стійкі стандарти шифрування на основі ґраткових задач (ML-KEM, ML-DSA), підписів на основі хешів (SPHINCS+). Міграція інтернет-інфраструктури вже триває для довговічних секретів, які мають лишатися захищеними 25+ років — загроза «зібрати зараз, розшифрувати пізніше» існує ще до того, як квантове обладнання дозріє.