Алгоритм HHL

Алгоритм Харроу-Хассидима-Ллойда или алгоритм HHL — это квантовый алгоритм для численного решения системы линейных уравнений , разработанный Арамом Харроу , Авинатаном Хасидимом и Сетом Ллойдом . Алгоритм оценивает результат скалярного измерения вектора решения заданной линейной системы уравнений.

Алгоритм является одним из основных фундаментальных алгоритмов, который, как ожидается, обеспечит ускорение по сравнению со своими классическими аналогами, наряду с алгоритмом факторизации Шора , алгоритмом поиска Гровера и квантовым преобразованием Фурье . При условии, что линейная система разрежена и имеет низкий номер состояния $\kappa$, и что пользователя интересует результат скалярного измерения вектора решения, а не значения самого вектора решения, то время выполнения алгоритма равно $O(\log(N)\kappa ^{2})$, где $N$ – количество переменных в линейной системе. Это обеспечивает экспоненциальное ускорение по сравнению с самым быстрым классическим алгоритмом, который работает в $O(N\kappa )$ (или $O(N{\sqrt {\kappa }})$ для положительно-полуопределенных матриц).

Реализация квантового алгоритма для линейных систем уравнений была впервые продемонстрирована в 2013 году тремя независимыми публикациями. Демонстрации состояли из простых линейных уравнений на специально разработанных квантовых устройствах. Первая демонстрация универсальной версии алгоритма появилась в 2018 году.

Ввиду распространенности линейных систем практически во всех областях науки и техники квантовый алгоритм для линейных систем уравнений имеет потенциал широкого применения.

Процедура

Алгоритм HHL решает следующую проблему: учитывая $N\times N$ Эрмитова матрица $A$ и единичный вектор ${\vec {b}}\in \mathbb {R} ^{N}$, подготовьте квантовое состояние $|x\rangle$ соответствующий вектору ${\vec {x}}\in \mathbb {R} ^{N}$ которое решает линейную систему $A{\vec {x}}={\vec {b}}$. Точнее, цель – подготовить государство $|x\rangle$ амплитуды которого равны элементам ${\vec {x}}$. Это означает, в частности, что алгоритм не может быть использован для эффективного извлечения вектора ${\vec {x}}$ сам. Однако он позволяет эффективно вычислять средние значения формы $\langle x|M|x\rangle$ для некоторого наблюдаемого $M$.

Сначала алгоритм представляет вектор ${\vec {b}}$ как квантовое состояние вида:

$|b\rangle =\sum _{i\mathop {=} 1}^{N}b_{i}|i\rangle .$

Далее методы гамильтонового моделирования используются для применения унитарного оператора $e^{iAt}$ к $|b\rangle$ для суперпозиции разных времен $t$. Способность разлагаться $|b\rangle$ в собственный базис $A$ и найти соответствующие собственные значения $\lambda _{j}$ этому способствует использование квантовой оценки фазы .

Состояние системы после такой декомпозиции примерно следующее:

$\sum _{j\mathop {=} 1}^{N}\beta _{j}|u_{j}\rangle |\lambda _{j}\rangle ,$

где $u_{j}$ является базисом собственных векторов $A$, и $|b\rangle =\sum _{j\mathop {=} 1}^{N}\beta _{j}|u_{j}\rangle$.

Затем мы хотели бы выполнить линейное отображение, взяв $|\lambda _{j}\rangle$ к $C\lambda _{j}^{-1}|\lambda _{j}\rangle$, где $C$ является нормирующей константой. Операция линейного отображения не является унитарной и, следовательно, потребует нескольких повторений, поскольку существует некоторая вероятность неудачи. После того, как это удалось, мы не вычислили $|\lambda _{j}\rangle$ регистрируются и остаются с состоянием, пропорциональным:

$\sum _{i\mathop {=} 1}^{N}\beta _{i}\lambda _{j}^{-1}|u_{j}\rangle =A^{-1}|b\rangle =|x\rangle ,$

где $|x\rangle$ является квантовомеханическим представлением искомого вектора решения x . Чтобы считать все компоненты x, потребуется повторить процедуру как минимум N раз. Однако часто бывает так, что человека это не интересует. $x$ сам по себе, а скорее некоторое математическое ожидание линейного оператора M, действующего на x . Сопоставляя M с квантово-механическим оператором и выполняя квантовое измерение, соответствующее M , мы получаем оценку среднего значения $\langle x|M|x\rangle$. Это позволяет извлекать широкий спектр характеристик вектора x, включая нормализацию, веса в различных частях пространства состояний и моменты, без фактического вычисления всех значений вектора решения x .

Объяснение

Инициализация

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

$\mathbf {C} ={\begin{bmatrix}0&A\\A^{\dagger }&0\end{bmatrix}}.$

Как $C$ является эрмитовым, алгоритм теперь можно использовать для решения $Cy={\begin{bmatrix}b\\0\end{bmatrix}}$ чтобы получить $y={\begin{bmatrix}0\\x\end{bmatrix}}$.

Во-вторых, алгоритм требует эффективной процедуры подготовки $|b\rangle$, квантовое представление b. Предполагается, что существует некоторый линейный оператор $B$ который может принимать произвольное квантовое состояние $|\mathrm {initial} \rangle$ к $|b\rangle$ эффективно или что этот алгоритм является подпрограммой в более крупном алгоритме и задан $|b\rangle$ в качестве ввода. Любая ошибка при составлении состояния $|b\rangle$ игнорируется.

Наконец, алгоритм предполагает, что состояние $|\psi _{0}\rangle$ может быть эффективно подготовлено там, где

$|\psi _{0}\rangle :={\sqrt {2/T}}\sum _{\tau \mathop {=} 0}^{T-1}\sin \pi \left({\tfrac {\tau +{\tfrac {1}{2}}}{T}}\right)|\tau \rangle$

для какого-то большого $T$. Коэффициенты $|\psi _{0}\rangle$ выбираются для минимизации определенной квадратичной функции потерь, которая вызывает ошибку в $U_{\mathrm {invert} }$ подпрограмма, описанная ниже.

моделирование

Гамильтонианское моделирование используется для преобразования эрмитовой матрицы. $A$ в унитарный оператор, который затем можно применять по желанию. Это возможно, если A является s -разреженным и эффективно вычислимым по строкам, что означает, что он имеет не более s ненулевых записей на строку и, учитывая индекс строки, эти записи могут быть вычислены за время O( s ). При этих предположениях квантовое гамильтоновое моделирование позволяет $e^{iAt}$ моделироваться во времени $O(\log(N)s^{2}t)$.

U _{инвертировать} подпрограмму

Ключевая подпрограмма алгоритма, обозначенная $U_{\mathrm {invert} }$, определяется следующим образом и включает подпрограмму оценки фазы :

1. Подготовьтесь $|\psi _{0}\rangle ^{C}$ в регистре С

2. Применить условную гамильтонову эволюцию (сумму)

Применить преобразование Фурье к регистру C. 3. Обозначим полученные базисные состояния через $|k\rangle$ для k = 0, ..., T − 1. Определим $\lambda _{k}:=2\pi k/t_{0}$.

4. Присоединить трехмерный регистр S в состоянии

$|h(\lambda _{k})\rangle ^{S}:={\sqrt {1-f(\lambda _{k})^{2}-g(\lambda _{k})^{2}}}|\mathrm {nothing} \rangle ^{S}+f(\lambda _{k})|\mathrm {well} \rangle ^{S}+g(\lambda _{k})|\mathrm {ill} \rangle ^{S},$

5. Выполните шаги 1–3 в обратном порядке, не вычисляя весь мусор, возникший на этом пути.

Процедура оценки фазы на этапах 1–3 позволяет оценить собственные значения A с точностью до ошибки. $\epsilon$.

Вспомогательный регистр на шаге 4 необходим для построения конечного состояния с инвертированными собственными значениями, соответствующими диагонализованному обратному A. значению В этом регистре функции f , g называются функциями фильтра. Состояния «ничего», «хорошо» и «плохо» используются для указания телу цикла, как действовать; «Ничего» указывает, что желаемая инверсия матрицы еще не произошла, «ну» указывает, что инверсия произошла и цикл должен остановиться, а «ill» указывает на то, что часть $|b\rangle$ находится в плохо обусловленном подпространстве A , и алгоритм не сможет произвести желаемую инверсию. Для создания состояния, пропорционального обратному значению A, необходимо измерить «колодец», после чего общее состояние системы схлопывается до желаемого состояния по расширенному правилу Борна .

Основной цикл

Тело алгоритма соответствует процедуре усиления амплитуды : начиная с $U_{\mathrm {invert} }B|\mathrm {initial} \rangle$, неоднократно применяется следующая операция:

$U_{\mathrm {invert} }BR_{\mathrm {init} }B^{\dagger }U_{\mathrm {invert} }^{\dagger }R_{\mathrm {succ} },$

где

$R_{\mathrm {succ} }=I-2|\mathrm {well} \rangle \langle \mathrm {well} |$

и

$R_{\mathrm {init} }=I-2|\mathrm {initial} \rangle \langle \mathrm {initial} |.$

После каждого повторения $S$ измеряется и дает значение «ничего», «хорошо» или «плохо», как описано выше. Этот цикл повторяется до тех пор, пока $|\mathrm {well} \rangle$ измеряется, что происходит с вероятностью $p$. Вместо того, чтобы повторять ${\frac {1}{p}}$ раз, чтобы минимизировать ошибку, усиление амплитуды используется для достижения той же устойчивости к ошибкам, используя только $O\left({\frac {1}{\sqrt {p}}}\right)$ повторы.

Скалярное измерение

После успешного измерения «хорошо» на $S$ система будет находиться в состоянии, пропорциональном:

$\sum _{i\mathop {=} 1}^{N}\beta _{i}\lambda _{j}^{-1}|u_{j}\rangle =A^{-1}|b\rangle =|x\rangle .$

Наконец, выполним квантовомеханический оператор, соответствующий M, и получим оценку значения $\langle x|M|x\rangle$.

Анализ времени выполнения

эффективность

Лучший классический алгоритм, который создает фактический вектор решения ${\vec {x}}$ – это метод исключения Гаусса , который выполняется в $O(N^{3})$ время.

Если A является s -разреженным и положительно полуопределенным, то метод сопряженных градиентов . для нахождения вектора решения можно использовать ${\vec {x}}$, который можно найти в $O(Ns\kappa )$ время путем минимизации квадратичной функции $|A{\vec {x}}-{\vec {b}}|^{2}$.

Когда только сводная статистика вектора решения ${\vec {x}}$ необходимо, как и в случае с квантовым алгоритмом для линейных систем уравнений, классический компьютер может найти оценку ${\vec {x}}^{\dagger }M{\vec {x}}$ в $O(N{\sqrt {\kappa }})$.

эффективность

Время выполнения квантового алгоритма решения систем линейных уравнений, первоначально предложенного Харроу и др. было показано, что $O(\kappa ^{2}\log N/\varepsilon )$, где $\varepsilon >0$ является параметром ошибки и $\kappa$ является обусловленности числом $A$. Впоследствии это было улучшено до $O(\kappa \log ^{3}\kappa \log N/\varepsilon ^{3})$ Андрис Амбайнис и квантовый алгоритм с полиномом времени выполнения в $\log(1/\varepsilon )$ был разработан Чайлдсом и соавт. Поскольку алгоритм HHL сохраняет логарифмическое масштабирование в $N$ только для разреженных матриц или матриц низкого ранга, Воссниг и др. расширил алгоритм HHL, основанный на методе квантовой оценки сингулярных значений, и предоставил алгоритм линейной системы для плотных матриц, который работает в $O({\sqrt {N}}\log N\kappa ^{2})$ время по сравнению с $O(N\log N\kappa ^{2})$ стандартного алгоритма HHL.

Оптимальность

Важным фактором производительности алгоритма обращения матрицы является число обусловленности $\kappa$, который представляет собой соотношение $A$наибольшее и наименьшее собственные значения. По мере увеличения числа обусловленности легкость, с которой можно найти вектор решения с помощью методов градиентного спуска, таких как метод сопряженных градиентов, уменьшается, поскольку $A$ становится ближе к матрице, которую нельзя обратить, и вектор решения становится менее стабильным. Этот алгоритм предполагает, что все сингулярные значения матрицы $A$ лежать между ${\frac {1}{\kappa }}$ и 1, и в этом случае заявленное время работы пропорционально $\kappa ^{2}$ будет достигнуто. Следовательно, ускорение по сравнению с классическими алгоритмами еще больше увеличивается, когда $\kappa$ это $\mathrm {poly} (\log(N))$.

Если бы время выполнения алгоритма было сделано полилогарифмическим в $\kappa$ тогда проблемы, решаемые на n кубитах, могут быть решены за поли( n ) время, в результате чего класс сложности BQP будет равен PSPACE .

Анализ ошибок

Выполнение гамильтонового моделирования, которое является основным источником ошибок, осуществляется путем моделирования $e^{iAt}$. Предполагая, что $A$ является s-разреженным, это можно сделать с ошибкой, ограниченной константой $\varepsilon$, что будет преобразовано в аддитивную ошибку, достигнутую в выходном состоянии $|x\rangle$.

Шаг оценки фазы дает ошибку на $O\left({\frac {1}{t_{0}}}\right)$ в оценке $\lambda$, что приводит к относительной ошибке $O\left({\frac {1}{\lambda t_{0}}}\right)$ в $\lambda ^{-1}$. Если $\lambda \geq 1/\kappa$, принимая $t_{0}=O(\kappa \varepsilon )$ вызывает окончательную ошибку $\varepsilon$. Это требует, чтобы общая эффективность времени выполнения была увеличена пропорционально $O\left({\frac {1}{\varepsilon }}\right)$ чтобы минимизировать ошибку.

Экспериментальная реализация

Хотя еще не существует квантового компьютера, который действительно мог бы обеспечить ускорение по сравнению с классическим компьютером, реализация «доказательства концепции» остается важной вехой в разработке нового квантового алгоритма. Демонстрация квантового алгоритма для линейных систем уравнений оставалась сложной задачей в течение многих лет после его предложения до 2013 года, когда он был продемонстрирован Кай и др., Барз и др. и Пан и др. параллельно.

Цай и др.

Опубликовано в Physical Review Letters 110, 230501 (2013), Cai et al. сообщил об экспериментальной демонстрации простейшего значимого примера этого алгоритма, то есть решения $2\times 2$ линейные уравнения для различных входных векторов. Квантовая схема оптимизирована и скомпилирована в линейную оптическую сеть с четырьмя фотонными квантовыми битами (кубитами) и четырьмя управляемыми логическими вентилями, которая используется для последовательной реализации каждой подпрограммы этого алгоритма. Для различных входных векторов квантовый компьютер дает решения линейных уравнений с достаточно высокой точностью — от 0,825 до 0,993.

Барз и др.

5 февраля 2013 года Стефани Барз и ее коллеги продемонстрировали квантовый алгоритм для линейных систем уравнений в архитектуре фотонных квантовых вычислений. В этой реализации использовались два последовательных спутывающих вентиля на одной и той же паре кубитов с поляризационным кодированием. Были реализованы два отдельно управляемых вентиля НЕ, причем успешная работа первого была подтверждена измерением двух вспомогательных фотонов. Барз и др. обнаружили, что точность полученного выходного состояния варьируется от 64,7% до 98,1% из-за влияния излучений более высокого порядка в результате спонтанного параметрического преобразования с понижением частоты.

Пан и др.

8 февраля 2013 г. Пан и др. сообщил об экспериментальной демонстрации концепции квантового алгоритма с использованием 4-кубитного процессора квантовой информации ядерного магнитного резонанса. Реализация была протестирована с использованием простых линейных систем всего с двумя переменными. В ходе трех экспериментов они получили вектор решения с точностью более 96%.

Вен и др.

О другой экспериментальной демонстрации использования ЯМР для решения системы 8*8 сообщили Wen et al. в 2018 году с использованием алгоритма, разработанного Субаши и др.

Приложения

Квантовые компьютеры — это устройства, которые используют квантовую механику для выполнения вычислений способами, недоступными классическим компьютерам. Для решения определенных задач квантовые алгоритмы обеспечивают экспоненциальное ускорение по сравнению со своими классическими аналогами, наиболее известным примером является алгоритм факторизации Шора. Известно немного таких экспоненциальных ускорений, а те, которые есть (например, использование квантовых компьютеров для моделирования других квантовых систем), до сих пор нашли ограниченное практическое применение из-за нынешнего небольшого размера квантовых компьютеров. Этот алгоритм обеспечивает экспоненциально более быстрый метод оценки особенностей решения системы линейных уравнений, которая является проблемой, повсеместно встречающейся в науке и технике, как сама по себе, так и в качестве подпрограммы в более сложных задачах.

Электромагнитное рассеяние

Кладер и др. предоставил заранее обусловленную версию алгоритма линейных систем, которая обеспечила два усовершенствования. Во-первых, они продемонстрировали, как предобуславливатель можно включить в квантовый алгоритм. Это расширяет класс задач, с помощью которых можно добиться обещанного экспоненциального ускорения, поскольку масштабирование HHL и лучшие классические алгоритмы полиномиальны по числу обусловленности . Вторым достижением стала демонстрация того, как использовать HHL для расчета поперечного сечения радара сложной формы. Это был один из первых сквозных примеров того, как использовать HHL для решения конкретной проблемы экспоненциально быстрее, чем самый известный классический алгоритм.

Решение линейных дифференциальных уравнений

Доминик Берри предложил новый алгоритм решения линейных дифференциальных уравнений, зависящих от времени, как расширение квантового алгоритма решения линейных систем уравнений. Берри предлагает эффективный алгоритм для решения полной эволюции в рамках разреженных линейных дифференциальных уравнений на квантовом компьютере.

Метод конечных элементов

Метод конечных элементов использует большие системы линейных уравнений для поиска приближенных решений различных физических и математических моделей. Монтанаро и Паллистер демонстрируют, что алгоритм HHL, примененный к определенным задачам FEM, может достичь полиномиального квантового ускорения. Они предполагают, что экспоненциальное ускорение невозможно в задачах с фиксированными размерами, решение которых удовлетворяет определенным условиям гладкости.

Квантовое ускорение метода конечных элементов выше для задач, которые включают решения с производными более высокого порядка и большими пространственными размерами. Например, проблемы динамики многих тел требуют решения уравнений, содержащих производные на порядках, масштабируемых с количеством тел, а некоторые проблемы вычислительного финансирования , такие как модели Блэка-Шоулза , требуют больших пространственных измерений.

Подбор методом наименьших квадратов

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

Машинное обучение и анализ больших данных

Основная статья: Квантовое машинное обучение

Машинное обучение — это исследование систем, которые могут определять тенденции в данных. Задачи машинного обучения часто включают манипулирование и классификацию большого объема данных в многомерных векторных пространствах. Время работы классических алгоритмов машинного обучения ограничено полиномиальной зависимостью как от объема данных, так и от размеров пространства. Квантовые компьютеры способны манипулировать многомерными векторами, используя тензорные пространства произведений, и поэтому являются хорошо подходящими платформами для алгоритмов машинного обучения.

Квантовый алгоритм для линейных систем уравнений был применен к машине опорных векторов, которая представляет собой оптимизированный линейный или нелинейный двоичный классификатор. Машина опорных векторов может использоваться для машинного обучения с учителем, при котором доступен обучающий набор уже классифицированных данных, или для машинного обучения без учителя, при котором все данные, передаваемые в систему, неклассифицированы. Ребентрост и др. показать, что квантовую машину опорных векторов можно использовать для классификации больших данных и добиться экспоненциального ускорения по сравнению с классическими компьютерами.

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

Финансы

Предложения по использованию HHL в финансах включают решение уравнений в частных производных для уравнения Блэка – Шоулза и определение оптимизации портфеля с помощью решения Марковица .

Квантовая химия

В 2023 году Баскаран и др. предложил использовать алгоритм HHL для квантово-химических расчетов с помощью метода линеаризованных связанных кластеров (LCC). Связь алгоритма HHL и метода LCC обусловлена ​​тем, что последний можно переписать в виде системы линейных уравнений. Ключевым фактором, который делает этот подход полезным для квантовой химии, является то, что количество кубитов регистра состояния является натуральным логарифмом числа возбуждений, что обеспечивает экспоненциальное подавление количества требуемых кубитов по сравнению с вариационным квантовым собственным решателем или квантовым фазовым решателем. алгоритмы оценки . Это приводит к «сосуществованию в разных масштабах», когда в данную эпоху квантовых вычислений HHL-LCC можно было бы применять к гораздо более крупным системам, тогда как QPE- CASCI можно было бы использовать для более мелких молекулярных систем, но с большей точностью в предсказании молекулярных свойств. Что касается алгоритма, авторы представляют подход «AdaptHHL», который позволяет избежать необходимости тратить ~Ο(N ³ ) классические накладные расходы, связанные с фиксацией значения параметра «c» в модуле управляемого вращения алгоритма.

Обзор

Признавая важность алгоритма HHL в области квантового машинного обучения , Скотт Ааронсон анализирует предостережения и факторы, которые могут ограничить фактическое квантовое преимущество алгоритма.

1. вектор решения, $|b\rangle$, должен быть эффективно подготовлен в квантовом состоянии. Если вектор не близок к единообразному, государственная подготовка, скорее всего, будет дорогостоящей, а если она потребует $O(n^{c})$ шагов, экспоненциальное преимущество HHL исчезнет.
2. Фазы QPE требуют создания унитарного $e^{iAt}$и его контролируемое применение. Эффективность этого этапа зависит от $A$ матрица разрежена и «хорошо кондиционирована» (низкая $\kappa$). В противном случае применение $e^{iAt}$ будет расти как $O(n^{c})$ и снова квантовое преимущество алгоритма исчезнет.
3. наконец, вектор, $|x\rangle$, не является легкодоступным. Алгоритм HHL позволяет изучить «сводку» вектора, а именно результат измерения ожидания оператора. $\langle x|M|x\rangle$. Если фактические значения ${\vec {x}}$ необходимы, то HHL необходимо будет повторить $O(n)$ раз, убивая экспоненциальное ускорение. Однако были предложены три способа избежать получения фактических значений: во-первых, если необходимы только некоторые свойства решения; во-вторых, если результаты необходимы только для подачи последующих матричных операций; в-третьих, если нужен только образец раствора.

См. также

• Дифференцируемое программирование