Конспект: кубит, интерференция, алгоритмы Гровера и Шора

СОСТОЯНИЕ И ИЗМЕРЕНИЕ
(a₀, a₁),  a₀² + a₁² = 1      измерение: 0 с вероятностью a₀²,
                              1 с вероятностью a₁²
(0,6; 0,8) и (0,6; −0,8):  статистика измерений одна - 0,36 и 0,64;
                           знак виден только операциям
n кубитов - 2ⁿ амплитуд, измерение - одна строка из n бит

моделирование по 8 байт на амплитуду:   30 кубитов - 8 ГБ;
                    40 - 8 тысяч ГБ;   50 - 8 миллионов ГБ
вычислимо то же, что на машине Тьюринга;  вопрос только в скорости

ВЕНТИЛИ И ИНТЕРФЕРЕНЦИЯ
«не»:      (a₀, a₁) → (a₁, a₀)
Адамар:    (a₀, a₁) → ( (a₀ + a₁)/√2,  (a₀ − a₁)/√2 )
           (1, 0) → (0,7071; 0,7071)      (0, 1) → (0,7071; −0,7071)

два вентиля Адамара подряд:   к нулю    +1/2 + 1/2 = 1
                              к единице +1/2 − 1/2 = 0
                              возврат в исходное состояние
два случайных подбрасывания:  0,5 и 0,5 навсегда -
                              вероятностям нечем гаситься

запутанная пара:  00  →  Адамар на первый  →  управляемое «не»
                  →  (00 + 11)/√2
                  из 1000 измерений: 492 раза 00, 508 раз 11,
                  остальное - ни разу

ДОЙЧ: одно обращение
(1, 0) → Адамар → оракул меняет знак при f(x) = 1 → Адамар → измерить
f(0) = f(1)  →  0          f(0) ≠ f(1)  →  1
значений функции алгоритм не узнаёт

n бит: постоянная - строка из нулей наверняка;   «поровну» - никогда;
       иначе - что угодно (0,5625)
детерминированной программе 2ⁿ⁻¹ + 1 обращение;
случайной - два-три десятка с ошибкой 2⁻¹⁹

ГРОВЕР: поиск за корень
шаг:  сменить знак у отмеченного;
      каждую амплитуду a заменить на 2 · среднее − a
N = 4:  0,5 0,5 0,5 0,5  →  0,5 0,5 −0,5 0,5  →  0 0 1 0     один шаг
N = 64, вероятность по шагам:
      0,016  0,13  0,34  0,59  0,82  0,96  0,997  0,91  0,72 …  0,0001
шагов  (π/4) · √N:     N      16    64    256    1024
                       шагов   3     6     12      25      перебор: N / 2
лишние шаги портят;   быстрее √N нельзя - доказано;
2ⁿ → 2 в степени n/2: всё ещё экспонента
ключ 128 бит → 10¹⁹ шагов;   защита - ключ 256 бит

ШОР: разложение через период
1. выбрать a;  НОД(a, N) > 1 - готово
2. период r:  наименьшее r, при котором a в степени r даёт остаток 1
              ← квантовый шаг
3. r нечётный - другое a
4. h = a в степени r/2;  h = N − 1 - другое a;
   иначе НОД(h − 1, N) и НОД(h + 1, N)

N = 15, a = 7:   остатки 1, 7, 4, 13, 1 …   r = 4,   h = 4,
                 НОД(3, 15) = 3,   НОД(5, 15) = 5
период растёт с числом:   221 → 24;   3127 → 1508;   47897 → 23730
ключ 2048 бит:  перебор степеней - 2²⁰⁰⁰;
                квантовая часть - порядка 2048³ операций

на устройствах честно разложены 15 и 21;
для ключа нужно порядка миллиона кубитов (оценка 2025 года)
стандарты устойчивых шифров приняты в 2024 году;
отказ от прежних - к 2035 году

ЧТО УСКОРЯЕТСЯ
экспоненциально   разложение, дискретный логарифм,
                  моделирование квантовых систем
квадратично       поиск без структуры, перебор ключей
не ускоряется     NP-полные задачи (известен только корень),
                  сортировка, обычная арифметика
P ⊆ BQP ⊆ PSPACE;    NP в BQP, по общему ожиданию, не содержится