алгоритм HHL

Алгоритм квантовой линейной алгебры, обеспечивающий экспоненциальное ускорение при определенных условиях

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

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

Реализация квантового алгоритма для линейных систем уравнений была впервые продемонстрирована в 2013 году тремя независимыми публикациями. ^{[3] [4] [5]} Демонстрации состояли из простых линейных уравнений на специально разработанных квантовых устройствах. ^{[3] [4] [5]} Первая демонстрация универсальной версии алгоритма появилась в 2018 году. ^[6]

В связи с распространенностью линейных систем практически во всех областях науки и техники квантовый алгоритм для линейных систем уравнений имеет потенциал для широкого применения. ^[7]

Процедура

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

Во-первых, алгоритм представляет вектор как квантовое состояние вида: ${\displaystyle {\vec {b}}}$

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

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

Состояние системы после этого разложения приблизительно такое:

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

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

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

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

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

Объяснение

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

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

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

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

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

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

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

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

Гамильтоново моделирование

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

U инвертировать подпрограмма

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

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

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

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

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

${\displaystyle |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 с точностью до погрешности . ${\displaystyle \epsilon }$

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

Основной контур

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

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

где

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

и

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

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

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

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

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

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

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

Классическая эффективность

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

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

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

Квантовая эффективность

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

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

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

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

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

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

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

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

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

Кай и др.

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

Барц и др.

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

Пан и др.

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

Вэнь и др.

Еще одна экспериментальная демонстрация использования ЯМР для решения системы 8*8 была представлена ​​Веном и др. ^[12] в 2018 году с использованием алгоритма, разработанного Субаши и др. ^[13].

Приложения

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

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

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

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

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

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

Две группы предложили ^[16] эффективные алгоритмы для численного интегрирования диссипативных нелинейных обыкновенных дифференциальных уравнений. Лю и др. ^[17] использовали метод линеаризации Карлемана для уравнений второго порядка, а Ллойд и др. ^[18] использовали метод линеаризации среднего поля, вдохновленный нелинейным уравнением Шредингера для нелинейностей общего порядка. Полученные линейные уравнения решаются с использованием квантовых алгоритмов для линейных дифференциальных уравнений.

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

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

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

Подгонка по методу наименьших квадратов

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

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

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

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

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

Финансы

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

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

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

Критика

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

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

Смотрите также

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

Ссылки

1. Harrow, Aram W; Hassidim, Avinatan; Lloyd, Seth (2008). "Квантовый алгоритм для линейных систем уравнений". Physical Review Letters . 103 (15): 150502. arXiv : 0811.3171 . Bibcode : 2009PhRvL.103o0502H. doi : 10.1103/PhysRevLett.103.150502. PMID  19905613. S2CID  5187993.
2. Джонстон, Эрик (2019-07-03). Программирование квантовых компьютеров: основные алгоритмы и примеры кода. O'Reilly Media . стр. 267. ISBN 9781492039655.
3. Cai, X.-D; Weedbrook, C; Su, Z.-E; Chen, M.-C; Gu, Mile; Zhu, M.-J; Li, Li; Liu, Nai-Le; Lu, Chao-Yang; Pan, Jian-Wei (2013). "Экспериментальные квантовые вычисления для решения систем линейных уравнений". Physical Review Letters . 110 (23): 230501. arXiv : 1302.4310 . Bibcode : 2013PhRvL.110w0501C. doi : 10.1103/PhysRevLett.110.230501. PMID  25167475. S2CID  20427454.
4. Barz, Stefanie; Kassal, Ivan; Ringbauer, Martin; Lipp, Yannick Ole; Dakić, Borivoje; Aspuru-Guzik, Alán; Walther, Philip (2014). "Двухкубитный фотонный квантовый процессор и его применение для решения систем линейных уравнений". Scientific Reports . 4 : 6115. arXiv : 1302.1210 . Bibcode :2014NatSR...4E6115B. doi :10.1038/srep06115. ISSN  2045-2322. PMC 4137340 . PMID  25135432. 
5. Pan, Jian; Cao, Yudong; Yao, Xiwei; Li, Zhaokai; Ju, Chenyong; Peng, Xinhua; Kais, Sabre; Du, Jiangfeng; Du, Jiangfeng (2014). "Экспериментальная реализация квантового алгоритма для решения линейных систем уравнений". Physical Review A. 89 ( 2): 022313. arXiv : 1302.1946 . Bibcode : 2014PhRvA..89b2313P. doi : 10.1103/PhysRevA.89.022313. S2CID  14303240.
6. Чжао, Чжикуань; Позас-Керстьенс, Алехандро; Ребентрост, Патрик; Виттек, Питер (2019). «Байесовское глубокое обучение на квантовом компьютере». Квантовый машинный интеллект . 1 (1–2): 41–51. arXiv : 1806.11463 . doi :10.1007/s42484-019-00004-7. S2CID  49554188.
7. Квантовый компьютер реализует наиболее практичный квантовый алгоритм, Лу и Пан.
8. Амбаинис, Андрис (2010). «Усиление амплитуды переменного времени и более быстрый квантовый алгоритм для решения систем линейных уравнений». arXiv : 1010.4458 [quant-ph].
9. Чайлдс, Эндрю М.; Котари, Робин; Сомма, Роландо Д. (2017). «Квантовый алгоритм для систем линейных уравнений с экспоненциально улучшенной зависимостью от точности». SIAM Journal on Computing . 46 (6): 1920–1950. arXiv : 1511.02306 . doi : 10.1137/16m1087072. ISSN  0097-5397. S2CID  3834959.
10. Воссниг, Леонард; Чжао, Чжикуань; Пракаш, Анупам (2018). «Квантовый линейный системный алгоритм для плотных матриц». Physical Review Letters . 120 (5): 050502. arXiv : 1704.06174 . Bibcode : 2018PhRvL.120e0502W. doi : 10.1103/PhysRevLett.120.050502. PMID  29481180. S2CID  3714239.
11. Cai, X. -D; Weedbrook, Christian; Su, Z. -E; Chen, M. -C; Gu, Mile; Zhu, M. -J; Li, L; Liu, N. -L; Lu, Chao-Yang; Pan, Jian-Wei (2013). "Экспериментальные квантовые вычисления для решения систем линейных уравнений". Physical Review Letters . 110 (23): 230501. arXiv : 1302.4310 . Bibcode : 2013PhRvL.110w0501C. doi : 10.1103/PhysRevLett.110.230501. PMID  25167475. S2CID  20427454.
12. Цзинвэй Вэнь, Сянъюй Кун, Шицзе Вэй, Биксю Ван, Тао Синь и Гуйлу Лонг (2019). «Экспериментальная реализация квантовых алгоритмов для линейной системы, вдохновленная адиабатическими квантовыми вычислениями». Phys. Rev. A 99 , 012320.
13. Субаши, Йигит; Сомма, Роландо Д.; Орсуччи, Давиде (2019-02-14). «Квантовые алгоритмы для систем линейных уравнений, вдохновленные адиабатическими квантовыми вычислениями». Physical Review Letters . 122 (6): 060504. arXiv : 1805.10549 . Bibcode : 2019PhRvL.122f0504S. doi : 10.1103/physrevlett.122.060504. ISSN  0031-9007. PMID  30822089. S2CID  73493666.
14. Clader, B. D; Jacobs, B. C; Sprouse, C. R (2013). "Предобусловленный квантовый линейный системный алгоритм". Physical Review Letters . 110 (25): 250504. arXiv : 1301.2340 . Bibcode : 2013PhRvL.110y0504C. doi : 10.1103/PhysRevLett.110.250504. PMID  23829722. S2CID  33391978.
15. Берри, Доминик В. (2010). «Квантовый алгоритм высокого порядка для решения линейных дифференциальных уравнений». Журнал физики A: Математическое и теоретическое . 47 (10): 105301. arXiv : 1010.2745 . Bibcode : 2014JPhA...47j5301B. doi : 10.1088/1751-8113/47/10/105301. S2CID  17623971.
16. Леви, Макс Г. (5 января 2021 г.). «Новые квантовые алгоритмы наконец-то расщепляют нелинейные уравнения». Журнал Quanta . Получено 31 декабря 2022 г.
17. Лю, Дж. П.; Колден, Х. О.; Крови, Х. К.; Лоурейро, Н. Ф.; Тривиса, К.; Чайлдс, А. М. (2021). «Эффективный квантовый алгоритм для диссипативных нелинейных дифференциальных уравнений». PNAS . 118 (35): e2026805118. arXiv : 2011.03185 . Bibcode : 2021PNAS..11826805L. doi : 10.1073/pnas.2026805118 . PMC 8536387 . PMID  34446548. 
18. Ллойд, С.; Де Пальма, Г.; Гоклер, К.; Киани, Б.; Лю, З.В.; Марвиан, М.; Тенни, Ф.; Палмер, Т. (2020). «Квантовый алгоритм для нелинейных дифференциальных уравнений». arXiv : 2011.06571 [quant-ph].
19. Монтанаро, Эшли; Паллистер, Сэм (2016). «Квантовые алгоритмы и метод конечных элементов». Physical Review A. 93 ( 3): 032324. arXiv : 1512.05903 . Bibcode : 2016PhRvA..93c2324M. doi : 10.1103/PhysRevA.93.032324. S2CID  44004935.
20. Вибе, Натан; Браун, Дэниел; Ллойд, Сет (2012). «Квантовая подгонка данных». Physical Review Letters . 109 (5): 050505. arXiv : 1204.5242 . Bibcode : 2012PhRvL.109e0505W. doi : 10.1103/PhysRevLett.109.050505. PMID  23006156. S2CID  118439810.
21. Ллойд, Сет; Мохсени, Масуд; Ребентрост, Патрик (2013). «Квантовые алгоритмы для контролируемого и неконтролируемого машинного обучения». arXiv : 1307.0411 [quant-ph].
22. Ребентрост, Патрик; Мохсени, Масуд; Ллойд, Сет (2013). «Квантовая машина опорных векторов для классификации больших признаков и больших данных». arXiv : 1307.0471v2 [quant-ph].
23. "apozas/bayesian-dl-quantum". GitLab . Получено 30 октября 2018 г.
24. Жакье, Антуан (2022-10-31). Квантовое машинное обучение и оптимизация в финансах: на пути к квантовому преимуществу. Packt . стр. 349. ISBN 9781801817875.
25. Баскаран, Н (2023). «Адаптация алгоритма Харроу-Хассидима-Ллойда к квантовой теории многих тел». Physical Review Research . 5 (4): 043113. Bibcode : 2023PhRvR...5d3113B. doi : 10.1103/PhysRevResearch.5.043113 .
26. Ааронсон, Скотт (2015). «Прочитайте мелкий шрифт». Nature Physics . 11 (4): 291–293. Bibcode : 2015NatPh..11..291A. doi : 10.1038/nphys3272. S2CID  122167250. Получено 09.05.2023 .
27. Шульд, Мария (2018). Контролируемое обучение с квантовыми компьютерами. Springer Publishing . стр. 218. ISBN 9783319964249.
28. Шульд, Мария (2018). Контролируемое обучение с квантовыми компьютерами. Springer Publishing . стр. 219. ISBN 9783319964249.