Эволюция численных методов: квантовые алгоритмы и алгоритм HHL для линейных систем
Квантовое превосходство в вычислительной линейной алгебре
Наш цикл из ста статей, посвященный классическим численным методам, логично завершить взглядом в будущее, где зарождается новая, революционная вычислительная парадигма — квантовые вычисления. Вся классическая математика, которую мы обсуждали (методы Гаусса, Крылова, многосеточные алгоритмы), опирается на архитектуру процессоров фон Неймана и детерминированные биты, принимающие значения 0 или 1. Как бы мы ни оптимизировали эти алгоритмы, решение системы из N линейных алгебраических уравнений (СЛАУ) всегда будет требовать времени, по меньшей мере пропорционального количеству неизвестных O(N). Компьютеру банально нужно время, чтобы просто прочитать все числа из памяти.
В 2009 году физики Арам Харроу, Авинатан Хасидим и Сет Ллойд опубликовали алгоритм HHL (Harrow-Hassidim-Lloyd algorithm), который вызвал настоящий шок в академическом мире. Этот квантовый алгоритм предназначен для решения систем линейных уравнений Ax = b. Его теоретическая вычислительная сложность составляет феноменальные O(log N)! Экспоненциальное ускорение означает, что система из триллиона уравнений, на которую лучшему классическому суперкомпьютеру потребовались бы годы работы, квантовый компьютер сможет решить за доли секунды. Как возможна такая математическая магия?
Суперпозиция, фазовая оценка и квантовое состояние
Квантовый компьютер работает не с обычными регистрами, а с кубитами, которые находятся в суперпозиции (одновременно во всех возможных состояниях от 0 до 1). Алгоритм HHL не вычисляет вектор решения x в виде обычного массива чисел. Он кодирует правую часть уравнения b в квантовое состояние регистра (амплитуды вероятностей), а затем с помощью квантовых вентилей трансформирует это состояние так, чтобы оно пропорционально отражало вектор решения x.
Главный математический механизм HHL основан на Квантовой оценке фазы (Quantum Phase Estimation, QPE). Алгоритм симулирует квантовую гамильтонову эволюцию матрицы A во времени (оператор exp(iAt)). Применяя квантовое преобразование Фурье (QFT), алгоритм «извлекает» собственные значения матрицы A в специальный вспомогательный регистр кубитов. Затем применяется контролируемый поворот кубита, который физически делит амплитуды на эти собственные значения (эквивалент инвертирования матрицы A^-1). Наконец, обратная фазовая оценка возвращает систему из спектрального пространства, выдавая готовое квантовое состояние |x> = A^-1 |b>.
Проблема извлечения данных и перспективы
Квантовое ускорение HHL содержит серьезные практические оговорки (caveats). Вы не можете просто «распечатать» полученный миллиономерный вектор решения на экран. Квантовая механика позволяет вам только произвести измерение состояния, что разрушит суперпозицию и выдаст лишь одно случайное число. Алгоритм HHL полезен не тогда, когда вам нужны все значения x, а тогда, когда вам нужно найти глобальное свойство решения (например, скалярное произведение x*M*x или среднюю кинетическую энергию системы).
Кроме того, матрица A должна быть разреженной (sparse) и хорошо обусловленной, а данные правой части b должны загружаться в компьютер с помощью сверхбыстрой квантовой памяти (QRAM), которая пока не существует на аппаратном уровне. Несмотря на эти технические преграды, алгоритм HHL заложил фундамент для Квантового Машинного Обучения (QML). Решение гигантских СЛАУ лежит в основе методов наименьших квадратов, обучения нейросетей и дифференциальных уравнений Навье-Стокса. Как только квантовые процессоры преодолеют барьер ошибок (Quantum Error Correction), алгоритмы типа HHL полностью перепишут правила игры в вычислительной физике, экономике и криптографии.