Квантовый параллелизм и его ловушка
Квантовый компьютер действительно «считает на всех входах сразу» — но прочитать результат честно нельзя.
Квантовый параллелизм — вычисление функции сразу на суперпозиции всех входов; ограничение в том, что измерение возвращает значение лишь для одного случайного входа.
Как «посчитать всё сразу»
Возьмём n кубитов и применим Адамар к каждому. Из |00...0> получится равная суперпозиция всех 2^n входов с одинаковыми амплитудами. Если теперь обратимо вычислить функцию f, записав результат в дополнительный кубит, состояние будет содержать пары (x, f(x)) для всех x одновременно. Звучит как мечта: один проход — и функция вычислена на всём пространстве входов.
import math
n = 3 # 3 кубита -> 8 входов
N = 2 ** n
amp = 1 / math.sqrt(N) # равная амплитуда у каждого входа
# f(x) = x mod 2 (чётность). 'Вычислили' для всех x сразу:
state = [(x, x % 2, amp) for x in range(N)]
for x, fx, a in state:
print('x=%d f(x)=%d амплитуда=%.3f' % (x, fx, a))Вывод:
x=0 f(x)=0 амплитуда=0.354 x=1 f(x)=1 амплитуда=0.354 x=2 f(x)=0 амплитуда=0.354 x=3 f(x)=1 амплитуда=0.354 x=4 f(x)=0 амплитуда=0.354 x=5 f(x)=1 амплитуда=0.354 x=6 f(x)=0 амплитуда=0.354 x=7 f(x)=1 амплитуда=0.354
Ловушка: извлечь нельзя
А теперь плохая новость. Чтобы узнать значения, надо измерить. Измерение выдаст одну случайную пару (x, f(x)) — например, x=5, f(5)=1 — и разрушит всё остальное. Вы потратили один прогон и узнали ровно столько же, сколько узнали бы, вычислив f один раз на случайном входе. Никакого выигрыша! 2^n вычислений «есть», но достать их все невозможно: канал вывода — всего один бит-исход на измерение.
Как работает под капотом
Вот почему наивная картинка «квантовый компьютер — это 2^n параллельных процессоров» ложна. Правильная мысль: суперпозиция — это не результат, а заготовка. Настоящие квантовые алгоритмы не пытаются прочитать всё. Они задают вопрос об общем свойстве функции (например: «f постоянна или нет?», «где у f выделенный вход?») и с помощью интерференции добиваются, чтобы амплитуда нужного ответа стала большой, а ненужных — погасла. Параллелизм без интерференции бесполезен; вместе они и есть квантовый алгоритм.
Частые ошибки
- «Раз посчитали на всех входах — прочитаем таблицу значений». Нет: одно измерение — одна случайная строка.
- Считать параллелизм самостоятельным преимуществом. Без интерференции его не реализовать.
- Думать, что можно «измерить аккуратно» и не разрушить остальное. Нельзя.
Итог
- Адамар на n кубитах создаёт суперпозицию всех 2^n входов.
- Вычислить f на ней можно, но измерение вернёт лишь один случайный результат.
- Польза появляется, только если интерференция усилит нужный ответ.