Квантовый алгоритм для линейных систем уравнений

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

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

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

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

Процедура [ править ]

Проблема, которую мы пытаемся решить, заключается в следующем: по эрмитовой матрице и единичному вектору найти удовлетворяющий вектор решения . Этот алгоритм предполагает , что пользователь не заинтересован в ценности сам по себе, а результат применения некоторого оператора на х .${\displaystyle N\times N}$ ${\displaystyle A}$ ${\displaystyle {\overrightarrow {b}}}$${\displaystyle {\overrightarrow {x}}}$${\displaystyle A{\overrightarrow {x}}={\overrightarrow {b}}}$${\displaystyle {\overrightarrow {x}}}$${\displaystyle M}$${\displaystyle \langle x|M|x\rangle }$

Во-первых, алгоритм представляет вектор как квантовое состояние вида:${\displaystyle {\overrightarrow {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${\displaystyle |x\rangle }$${\displaystyle x}$${\displaystyle \langle x|M|x\rangle }$для извлечения, включая нормализацию, веса в различных частях пространства состояний и моменты, без фактического вычисления всех значений вектора решения  x .

Объяснение алгоритма [ править ]

Инициализация [ править ]

Во-первых, алгоритм требует, чтобы матрица была эрмитовой, чтобы ее можно было преобразовать в унитарный оператор . В случае, когда не эрмитово, определим ${\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)}$

${\displaystyle U_{\mathrm {invert} }}$подпрограмма [ править ]

Обозначенная ключевая подпрограмма алгоритма определяется следующим образом и включает подпрограмму оценки фазы :${\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 необходимо построить конечное состояние с инвертированных собственных значений , соответствующих диагонализуется обратной А . В этом регистре функции f , g называются функциями фильтрации. Состояния «ничего», «хорошо» и «плохо» используются для указания телу цикла, как действовать; «ничего» указывает, что желаемая инверсия матрицы еще не произошла, «хорошо» указывает, что инверсия произошла и цикл должен остановиться, а «ill» указывает, что часть находится в плохо обусловленном подпространстве 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 {\overrightarrow {x}}}$${\displaystyle O(N^{3})}$

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

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

Квантовая эффективность [ править ]

Время выполнения квантового алгоритма решения систем линейных уравнений, первоначально предложенного Харроу и др. Было показано, что , когда это параметр ошибки и это условие номер из . Впоследствии это было улучшено Андрисом Амбайнисом ^[7], а Чайлдс и др. Разработали квантовый алгоритм с полиномом времени выполнения in . ^[8] Поскольку алгоритм HHL поддерживает логарифмическое масштабирование только для разреженных матриц или матриц низкого ранга, Wossnig et al. ^[9] расширил алгоритм 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})}$ стандартного алгоритма HHL.

Оптимальность [ править ]

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

Если время выполнения алгоритма сделать полилогарифмическим, тогда задачи, решаемые на n кубитах, могут быть решены за poly ( 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. в параллели.

Cai et al. [ редактировать ]

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

Barz et al. [ редактировать ]

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

Pan et al. [ редактировать ]

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

Wen et al. [ редактировать ]

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

Приложения [ править ]

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

Электромагнитное рассеяние [ править ]

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

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

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

Метод конечных элементов [ править ]

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

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

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

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

Машинное обучение и анализ больших данных [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]