Основы квантовых вычислений
В классических вычислительных системах элементарной единицей информации является бит, принимающий значения 0 или 1. В квантовой механике аналогом бита выступает кубит — квантовая система, обладающая способностью находиться в линейной суперпозиции базисных состояний:
|ψ⟩ = α|0⟩ + β|1⟩, где α, β ∈ ℂ, |α|2+|β|2 = 1
Кубит может быть реализован на различных физических системах: спин электрона, поляризация фотона, уровни энергии ионов в ловушке и др. Его состояние описывается вектором в двумерном гильбертовом пространстве, где базисные состояния |0⟩ и |1⟩ аналогичны северному и южному полюсам сферы Блоха.
Суперпозиция — фундаментальное отличие квантовой информации от классической. В квантовых вычислениях это позволяет обрабатывать одновременно экспоненциальное число состояний. Однако измерение приводит к коллапсу волновой функции: наблюдается одно из возможных состояний с соответствующей вероятностью.
Интерференция используется для управления вероятностями результата вычислений: усиление амплитуд нужных состояний и подавление ненужных. Это ключевой механизм работы квантовых алгоритмов.
Квантовая спутанность (энтэнглмент) — нелокальное квантовое явление, при котором состояние одной части системы не может быть описано независимо от состояния другой, даже на расстоянии. Например:
$$ |\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle) $$
Такие состояния невозможно представить в виде тензорного произведения отдельных кубитов. Спутанность лежит в основе квантовой телепортации, квантовой криптографии и ускорения вычислений в некоторых алгоритмах.
Квантовые логические элементы — унитарные операторы. В отличие от классических логических вентилей, все операции в квантовой системе обратимы.
Наиболее распространённые квантовые гейты:
X-гейт (квантовый аналог NOT):
$$ X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \\ \end{pmatrix} $$
Hadamard-гейт:
$$ H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \\ \end{pmatrix} $$
Преобразует базисные состояния в суперпозиции: $H|0\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}},\quad H|1\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$
CNOT-гейт — двухкубитовый вентиль, управляющий инверсией второго кубита в зависимости от состояния первого:
CNOT(|a⟩⊗|b⟩) = |a⟩⊗|a ⊕ b⟩
Произвольная квантовая схема представляется последовательностью унитарных операций, действующих на множество кубитов.
Измерение разрушает квантовое состояние и сводит его к классическому результату. Оно описывается проекцией на базисные состояния. Например, измерение кубита в базисе {|0⟩,|1⟩} даёт результат 0 с вероятностью |α|2 и 1 с вероятностью |β|2.
Измерение — необратимая операция. При этом до измерения система может использоваться для параллельной обработки информации на множестве возможных путей.
Ключевое преимущество квантовых вычислений заключается в квантовом параллелизме. Применение унитарного преобразования ко всей суперпозиции состояний:
$$ \sum_x \alpha_x |x\rangle \xrightarrow{U_f} \sum_x \alpha_x |f(x)\rangle $$
При этом квантовый компьютер «одновременно» обрабатывает все x. Однако результат одного измерения выдаёт только один результат, поэтому нужно использовать интерференцию и дополнительные методы, чтобы «извлечь» полезную информацию.
Один из первых квантовых алгоритмов, демонстрирующий превосходство над классическими вычислениями. Пусть задана функция f : {0, 1} → {0, 1}, и требуется узнать, является ли она постоянной или сбалансированной (принимает 0 и 1 на разных входах).
Классически требуется два вычисления. Квантово — достаточно одно:
$$ |\psi\rangle \xrightarrow{H^{\otimes 2}} \frac{1}{2}(|0\rangle + |1\rangle)(|0\rangle - |1\rangle) \xrightarrow{U_f} \ldots \xrightarrow{H \otimes I} \ldots $$
В результате измерения первого кубита можно однозначно определить тип функции.
Позволяет эффективно разлагать целые числа на простые множители. Классическая сложность задачи — экспоненциальная. Квантовый алгоритм Шора использует квантовое преобразование Фурье (QFT) и находит период функции f(x) = ax mod N, что позволяет восстановить множители.
Основные этапы:
Квантовый алгоритм Шора имеет полиномиальную сложность и представляет собой угрозу для классических криптографических систем (RSA и др.).
Решает задачу поиска в неструктурированной базе данных. Классический алгоритм требует O(N) шагов, тогда как алгоритм Гровера — $O(\sqrt{N})$.
Алгоритм использует амплитудную амплификацию, чтобы повысить вероятность нужного состояния:
Метод применим для множества задач, включая оптимизацию, поиск и комбинаторику.
Квантовая вычислительная схема — аналог логической схемы, представляет собой комбинацию кубитов и квантовых гейтов. Существует набор универсальных квантовых гейтов, через которые можно реализовать любую унитарную операцию с заданной точностью. Примеры:
Такой набор позволяет построить произвольный квантовый алгоритм.
Квантовые системы подвержены декогеренции и ошибкам, возникающим из-за взаимодействия с внешней средой. Особенность: квантовое состояние нельзя клонировать (теорема о запрете клонирования), и значит, стандартные методы коррекции ошибок неприменимы.
Тем не менее, разработаны квантовые коды коррекции ошибок, основанные на избыточности и запутанности. Пример — код Шора, кодирующий один логический кубит в 9 физических:
Эти методы позволяют создать устойчивые квантовые вычисления, если уровень ошибок ниже некоторого порога.
Существует несколько эквивалентных моделей:
Существуют различные платформы:
Каждая технология имеет свои преимущества и ограничения: время когерентности, масштабируемость, точность операций и возможности интеграции.
Квантовое превосходство — демонстрация задачи, решаемой квантовым компьютером за разумное время, но недоступной для классических суперкомпьютеров. Эксперимент Google (2019) с задачей случайного сэмплирования стал первым примером такого превосходства.
Развитие квантовых вычислений открывает новые горизонты в области:
Однако путь к универсальному квантовому компьютеру требует ещё значительных инженерных и теоретических достижений.