Важные сведения о квантовом компьютере

Дмитрий Урбанович

Ижевск, 7—8 мая 2018

Обновлено 8 января 2021 (MathML)

В научпопе любят писать про квантовые компьютеры загадочно, используя хайповые словечки, и не понимая собственной речи. Чтобы немного разогнать туман, которым надышали в этой области всевозможные журналисты, привожу короткий список важных сведений о квантовых компьютерах.

1. Квантовый $n$-кубитный компьютер — это генератор случайных $n$-битных чисел.
2. Программирование квантового компьютера заключается в настройке параметров случайного распределения.
3. Настройка делается каждый раз непосредственно перед генерацией очередного числа при помощи последовательного применения элементарных воздействий.
4. Существуют наборы элементарных воздействий, с помощью которых можно задать любое распределение со сколь угодно малой погрешностью. Обычно этот набор состоит из двух операций, которые можно применять к любым кубитам.

5. — Зачем мне квантовый компьютер? Я и на обычном могу выдавать случайные числа с любыми распределениями.

   — Можешь, да не любые. Например, Питер Шор в 1994 году придумал, как при помощи $O\left({\log }^{3}n\right)$ квантовых операций с большой вероятностью получать числа, кратные периоду последовательности $x$, $x^2$, $x^3$... по модулю $n$. Как воспроизвести за разумное время такое же распределение на обычных компьютерах при $n$ порядка $2^{2048}$ — никто не знает. А для квантового компьютера это не сложнее, чем умножение матриц размера $2048\times 2048$.

6. Квантовые компьютеры не всесильны. Есть такие распределения, на которые вряд ли можно эффективно настроить даже их.
7. Квантовые компьютеры не работают ни с комплексными, ни с действительными числами. Унитарные преобразования в гильбертовом пространстве — это матмодель, которая точно (но неэффективно) предсказывает результат работы квантового компььютера. Чем оперируют реальные компьютеры, зависит от их физической реализации.