Квантовый алгоритм для линейных систем уравнений - Quantum algorithm for linear systems of equations

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

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

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

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

Процедура

Проблема, которую мы пытаемся решить: учитывая Эрмитова матрица и единичный вектор , найти вектор решения удовлетворение . Этот алгоритм предполагает, что пользователя не интересуют значения сам, а скорее результат применения некоторого оператора на x, .

Во-первых, алгоритм представляет вектор как квантовое состояние формы:

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

Состояние системы после этой декомпозиции примерно:

куда является базисом собственных векторов , и .

Затем мы хотели бы выполнить линейное отображение к , куда - нормализующая постоянная. Операция линейного отображения не является унитарной и, следовательно, потребует нескольких повторений, поскольку имеет некоторую вероятность неудачи. После успеха мы не вычисляем регистр и остаются в состоянии, пропорциональном:

куда квантово-механическое представление искомого вектора решенияИкс. Считать все компоненты Икс потребует повторения процедуры не менее N раз. Однако часто бывает так, что никто не интересуется сам, а скорее некоторое математическое ожидание линейного оператора M действующий наИкс. Путем сопоставления M к квантово-механическому оператору и выполнение квантового измерения, соответствующего M, получаем оценку математического ожидания . Это позволяет использовать широкий спектр функций вектора. Икс для извлечения, включая нормализацию, веса в разных частях пространства состояний и моменты, без фактического вычисления всех значений вектора решенияИкс.

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

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

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

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

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

Наконец, алгоритм предполагает, что состояние можно приготовить качественно. Где

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

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

Гамильтоново моделирование используется для преобразования эрмитовой матрицы в унитарный оператор, который затем можно применять по желанию. Это возможно, если А является s- разреженный и эффективно вычисляемый по строкам, то есть он имеет не более s ненулевых записей на строку и с учетом индекса строки эти записи могут быть вычислены за время O (s). При этих предположениях квантовое гамильтоново моделирование позволяет быть смоделированным во времени .

подпрограмма

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

1. Подготовить в реестре C

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

3. Примените преобразование Фурье к регистру.C. Обозначим полученные базисные состояния через за k = 0, ..., Т - 1. Определить .

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

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

Процедура оценки фазы на этапах 1-3 позволяет оценить собственные значения А до ошибки .

Вспомогательный регистр на шаге 4 необходим для построения конечного состояния с инвертированными собственными значениями, соответствующими диагонализованной инверсии А. В этом регистре функции ж, грамм, называются функциями фильтрации. Состояния «ничего», «хорошо» и «плохо» используются для указания телу цикла, как действовать; «ничего» указывает, что желаемая инверсия матрицы еще не произошла, «хорошо» указывает, что инверсия произошла и цикл должен быть остановлен, а «ill» указывает, что часть находится в плохо обусловленном подпространстве А и алгоритм не сможет произвести желаемую инверсию. Создание состояния, пропорционального обратной величине А требует измерения «колодца», после чего общее состояние системы коллапсирует до желаемого состояния посредством расширенного Родившееся правило.

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

Тело алгоритма следует усиление амплитуды процедура: начиная с , повторно применяется следующая операция:

куда

и

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

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

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

Наконец, мы выполняем квантово-механический оператор, соответствующий M, и получаем оценку значения .

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

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

Лучший классический алгоритм, который дает реальный вектор решения является Гауссово исключение, который работает в время.

Если А является s-разреженный и положительный полуопределенный, то Метод сопряженного градиента можно использовать для нахождения вектора решения , который можно найти в время, минимизируя квадратичную функцию .

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

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

Время выполнения квантового алгоритма решения систем линейных уравнений, первоначально предложенного Харроу и др. был показан , куда параметр ошибки и это номер условия из . Впоследствии это было улучшено до Андрис Амбайнис[7] и квантовый алгоритм с полиномом времени выполнения от был разработан Childs et al.[8] Поскольку алгоритм HHL сохраняет логарифмическое масштабирование в только для разреженных матриц или матриц низкого ранга Wossnig et al.[9] расширил алгоритм HHL, основанный на методе квантовой оценки сингулярных значений, и предоставил алгоритм линейной системы для плотных матриц, который работает в время по сравнению с стандартного алгоритма HHL.

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

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

Если бы время выполнения алгоритма было сделано полилогарифмическим в тогда проблемы решаются на п кубиты могут быть решены в поли (п) время, в результате чего класс сложности BQP быть равным PSPACE.[1]

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

Гамильтоново моделирование, которое является основным источником ошибок, выполняется путем моделирования . При условии, что является s-разреженным, это можно сделать с ошибкой, ограниченной константой , что приведет к аддитивной ошибке, достигаемой в состоянии вывода .

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

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

Хотя еще не существует квантового компьютера, который действительно мог бы предложить ускорение по сравнению с классическим компьютером, реализация «доказательства концепции» остается важной вехой в разработке нового квантового алгоритма. Демонстрация квантового алгоритма для линейных систем уравнений оставалась сложной задачей в течение многих лет после его предложения до 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]

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]

Рекомендации

  1. ^ а б c Харроу, Арам В; Хасидим, Авинатан; Ллойд, Сет (2008). «Квантовый алгоритм решения линейных систем уравнений». Письма с физическими проверками. 103 (15): 150502. arXiv:0811.3171. Bibcode:2009PhRvL.103o0502H. Дои:10.1103 / PhysRevLett.103.150502. PMID  19905613.
  2. ^ Цай, X.-D; Уидбрук, С; Вс, З.-Э; Chen, M.-C; Гу, Миля; Чжу, М.-Дж; Ли, Ли; Лю, Най-Ле; Лу, Чао-Ян; Пан, Цзянь-Вэй (2013). «Экспериментальные квантовые вычисления для решения систем линейных уравнений». Письма с физическими проверками. 110 (23): 230501. arXiv:1302.4310. Bibcode:2013PhRvL.110w0501C. Дои:10.1103 / PhysRevLett.110.230501. PMID  25167475.
  3. ^ а б Барз, Стефани; Кассал, Иван; Рингбауэр, Мартин; Липп, Янник Оле; Дакич, Боривое; Аспуру-Гузик, Алан; Вальтер, Филип (2014). «Двухкубитовый фотонный квантовый процессор и его применение для решения систем линейных уравнений». Научные отчеты. 4: 6115. arXiv:1302.1210. Bibcode:2014НатСР ... 4Э6115Б. Дои:10.1038 / srep06115. ISSN  2045-2322. ЧВК  4137340. PMID  25135432.
  4. ^ а б Пан, Цзянь; Цао, Юдун; Яо, Сивэй; Ли, Чжаокай; Джу, Ченьонг; Пэн, Синьхуа; Кайс, Сэйбер; Ду, Цзянфэн; Ду, Цзянфэн (2014). «Экспериментальная реализация квантового алгоритма решения линейных систем уравнений». Физический обзор A. 89 (2): 022313. arXiv:1302.1946. Bibcode:2014PhRvA..89b2313P. Дои:10.1103 / PhysRevA.89.022313.
  5. ^ а б Чжао, Чжикуань; Позас-Керстьенс, Алехандро; Ребентрост, Патрик; Виттек, Питер (2019). «Байесовское глубокое обучение на квантовом компьютере». Квантовый машинный интеллект. 1 (1–2): 41–51. arXiv:1806.11463. Дои:10.1007 / s42484-019-00004-7.
  6. ^ Квантовый компьютер запускает наиболее практичный квантовый алгоритм, Лу и Пан.
  7. ^ Амбаинис, Андрис (2010). «Усиление амплитуды с переменным временем и более быстрый квантовый алгоритм для решения систем линейных уравнений». arXiv:1010.4458 [Quant-ph ].
  8. ^ Чайлдс, Эндрю М .; Котари, Робин; Сомма, Роландо Д. (2017). «Квантовый алгоритм для систем линейных уравнений с экспоненциально улучшенной зависимостью от точности». SIAM Журнал по вычислениям. 46 (6): 1920–1950. arXiv:1511.02306. Дои:10.1137 / 16m1087072. ISSN  0097-5397.
  9. ^ Wossnig, Леонард; Чжао, Чжикуань; Пракаш, Анупам (2018). «Алгоритм квантовой линейной системы для плотных матриц». Письма с физическими проверками. 120 (5): 050502. arXiv:1704.06174. Bibcode:2018PhRvL.120e0502W. Дои:10.1103 / PhysRevLett.120.050502. PMID  29481180.
  10. ^ Цай, X. -D; Видбрук, Кристиан; Вс, З. -Е; Чен, М. -С; Гу, Миля; Zhu, M. -J; Ли, Л; Лю, Н. -Л; Лу, Чао-Ян; Пан, Цзянь-Вэй (2013). «Экспериментальные квантовые вычисления для решения систем линейных уравнений». Письма с физическими проверками. 110 (23): 230501. arXiv:1302.4310. Bibcode:2013PhRvL.110w0501C. Дои:10.1103 / PhysRevLett.110.230501. PMID  25167475.
  11. ^ Цзинвэй Вэнь, Сяньюй Конг, Шицзе Вэй, Бисуэ Ван, Тао Синь и Гуйлу Лун (2019). «Экспериментальная реализация квантовых алгоритмов для линейной системы, вдохновленная адиабатическими квантовыми вычислениями». Phys. Ред. А 99, 012320.
  12. ^ Субаши, Йигит; Somma, Rolando D .; Орсуччи, Давиде (14 февраля 2019 г.). «Квантовые алгоритмы для систем линейных уравнений, вдохновленные адиабатическими квантовыми вычислениями». Письма с физическими проверками. 122 (6): 060504. arXiv:1805.10549. Дои:10.1103 / Physrevlett.122.060504. ISSN  0031-9007. PMID  30822089.
  13. ^ Clader, B.D; Джейкобс, Б. С.; Спроус, С. Р. (2013). «Предварительно обусловленный алгоритм квантовой линейной системы». Письма с физическими проверками. 110 (25): 250504. arXiv:1301.2340. Bibcode:2013PhRvL.110y0504C. Дои:10.1103 / PhysRevLett.110.250504. PMID  23829722.
  14. ^ Берри, Доминик В. (2010). «Квантовый алгоритм высокого порядка для решения линейных дифференциальных уравнений». Журнал физики A: математический и теоретический. 47 (10): 105301. arXiv:1010.2745. Bibcode:2014JPhA ... 47j5301B. Дои:10.1088/1751-8113/47/10/105301.
  15. ^ Монтанаро, Эшли; Паллистер, Сэм (2016). «Квантовые алгоритмы и метод конечных элементов». Физический обзор A. 93 (3): 032324. arXiv:1512.05903. Дои:10.1103 / PhysRevA.93.032324.
  16. ^ Вибе, Натан; Браун, Даниэль; Ллойд, Сет (2012). «Подгонка квантовых данных». Письма с физическими проверками. 109 (5): 050505. arXiv:1204.5242. Bibcode:2012PhRvL.109e0505W. Дои:10.1103 / PhysRevLett.109.050505. PMID  23006156.
  17. ^ Ллойд, Сет; Мохсени, Масуд; Ребентрост, Патрик (2013). «Квантовые алгоритмы машинного обучения с учителем и без учителя». arXiv:1307.0411 [Quant-ph ].
  18. ^ Ребентрост, Патрик; Мохсени, Масуд; Ллойд, Сет (2013). «Квантовая опорная векторная машина для классификации больших функций и больших данных». arXiv:1307.0471v2 [Quant-ph ].
  19. ^ "апозас / байесовский-дл-квант". GitLab. Получено 30 октября 2018.