Квантовые алгоритмы обещают необычайный выигрыш по сравнению с классическими алгоритмами. Но как на самом деле выглядит квантовое будущее?

Авторы: Тасмика Гокал (инженер по машинному обучению, Макс Келсен) Люк Камолс (стажер квантовых исследований, Макс Кельсен)

Вступление

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

Учитывая это, технологические гиганты быстро наращивали свой квантовый опыт. В конце 2019 года Amazon и Microsoft запустили собственные разработанные пакеты квантового программного обеспечения, в то время как Google добился« квантового превосходства . Однако квантовые физики и технические эксперты по-прежнему с осторожностью относятся к тому, как может выглядеть квантовое будущее.

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

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

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

Итак, учитывая присущие ограничения, на ум приходят вопросы, касающиеся возможной полезности квантовых алгоритмов:

«Можем ли мы решить проблемы с квантовым оборудованием?»

«Могут ли квантовые алгоритмы в конечном итоге стать полезными для отраслей, ориентированных на данные?»

В конце концов, квантовые физики так считают.

Создавая эффективные схемы, адаптированные для решения прикладных задач в эпоху NISQ, эксперты считают, что квантовые алгоритмы могут внести свой вклад в устоявшиеся отрасли, превзойдя классические аналоги в небольшом масштабе. Одна из отраслей, в которой квантовое ускорение выиграет, - это количественные финансы.

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

Однако квантовые алгоритмы могут обойти это.

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

Другие варианты оценки амплитуды (AE) включают оценку амплитуды максимального правдоподобия (MLAE) и, совсем недавно, итеративную квантовую оценку амплитуды (IQAE).

Ниже мы исследуем механику алгоритмов AE более подробно и предлагаем нашу критику и сравнение этих алгоритмов.

Квантовые алгоритмы

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

Для этого мы рассмотрим несколько различных квантовых алгоритмов для оценки амплитуды (AE). AE служит основой для других квантовых алгоритмов и может применяться, в частности, в финансовой отрасли. Ожидается, что эти квантовые алгоритмы обеспечат значительное ускорение времени выполнения по сравнению с классическими аналогами.

Наш пост довольно подробный и, как следствие, довольно длинный. Если вы хотите получить быстрый общий обзор каждого раздела, не стесняйтесь читать Сводка для каждого раздела.

Квантовые вычисления имеют некоторые неизбежные сложности. Мы имеем в виду кубиты (квантовые биты), обозначения бра-кета и основные квантовые вентили. Для быстрого ознакомления с этими концепциями см. Здесь. Также используется нотация Big-O, например, O (n²); big-O - это, по сути, верхняя граница. Понимание не принципиально, но объяснение смотрите здесь.

Наша работа основана на знаниях следующих источников: Брассар, Дж. и др., Йохичи Сузуки и др. и Дмитрий Гринько, и др. аль .

Если у вас есть аппетит к этой теме и вы хотите изучить ее дальше, вы можете проверить эту недавнюю статью.

Амплитудное усиление (AA)

Прежде чем рассматривать концепцию оценки амплитуды, давайте рассмотрим тесно связанный процесс, усиление амплитуды, на простом примере.

Схема А

Предположим, у нас есть четыре ключа (с обозначениями 0, 1, 2 и 3), один из которых открывает цифровой замок. Мы не знаем, какие ключи «хорошие» или «плохие», единственный способ узнать это - попробовать их по очереди. «Проблема черного ящика» требует от нас найти ключ, который подходит к замку.

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

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

Решение проблемы черного ящика в классическом мире потребовало бы случайного выбора ключей до тех пор, пока один из них не подходит к замку. Каждый выбранный ключ имеет вероятность (p = 1/4) открытия замка, поэтому мы ожидаем, что сделаем выборку 4 раза, прежде чем найдем «хороший» ключ.

Проблема с черным ящиком решена! А может и нет.

Давайте снова займемся проблемой, но с квантовой точки зрения. Мы возьмем классический черный ящик выше и создадим квантовый черный ящик, называемый оракул, O, который ведет себя следующим образом:

Что это означает: если мы подготовим наши первые n кубитов в состоянии, представляющем ключ, то после применения оракула последний (целевой) кубит будет содержать f (key) (1, если ключ был хорош, и 0, если ключ был плохим).

Фиолетовые и зеленые линии можно описать с помощью векторов состояния или «кетов». Комбинированная система может быть представлена ​​перечислением кета, связанного с фиолетовой линией, за которой следует зеленая. Затем этот оракул можно описать:

Но мы не можем перевести Ключ 3 в квантовое состояние, наше квантовое состояние может быть только | 00⟩, | 01⟩, | 10⟩ или | 11⟩. Вместо этого, чтобы использовать квантовый компьютер, нам нужно закодировать наши данные. Пусть Key 0 будет | 00⟩, Key 1 будет | 01⟩, Key 2 будет | 10⟩, а Key 3 будет | 11⟩.

Также нам понадобится вентиль Адамара, который действует по уравнению:

Что это означает: после того, как кубит в состоянии | 0⟩ проходит через вентиль Адамара, он одновременно находится в обоих состояниях | 0⟩ и | 1⟩. При наблюдении кубит с вероятностью 50% будет | 0⟩ и с вероятностью 50% будет | 1⟩.

До этого наблюдения кубит каким-то образом находится в обоих состояниях одновременно. Этот противоречивый принцип называется квантовой суперпозицией и является одной из ключевых идей квантовых вычислений.

Используя наши два строительных блока, мы создаем квантовую схему, которую мы назовем A.

Состояние кубитов, лежащих в основе этого процесса, показано на диаграмме ниже:

Эти шаги можно разбить на следующие группы:

а) 3 кубита изначально подготовлены в состоянии | 000⟩.

б) вентили Адамара «загружают» равномерное распределение вероятностей. Первые два кубита теперь находятся в суперпозиции с равным количеством ключей 0, 1, 2 и 3.

c) Оракул одновременно пробует все ключи, переключая целевой кубит на хорошие ключи.

г) Делаем замер. Существует равная вероятность чтения | 000⟩, | 010⟩, | 110⟩ или | 101⟩, но только один результат, | 101⟩, является хорошим, что дает 1/4 шанса прочитать хороший ответ, мы обозначаем эту вероятность 'а'. Если мы читаем | 101⟩, мы знаем, что это хорошо, потому что целевой кубит равен 1, и он представляет ключ 2, поскольку первые два кубита равны 10.

Итак, у нас есть квантовая схема, которая, кажется, помещает в замок все ключи одновременно, потрясающе! Тем не менее, амплитуда успеха не отличается от классической вероятности успеха, a = p = 1/4. Это определенно похоже на долгую прогулку за одним и тем же напитком. Не волнуйтесь, мы скоро доберемся до Q и квантового преимущества. Но сначала несколько математических обозначений!

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

Однако в этом примере все коэффициенты положительны, поэтому работа с вероятностями безопасна. Вот почему у нас положительное √ (1/4) в уравнении 3.

Немного неизбежной математики

Для упрощения мы будем использовать два специальных нормализованных (величина один) вектора (kets), | Ψ_1⟩ (хорошее состояние) и | Ψ_0⟩ (плохое состояние).

| Ψ_1⟩ ket указывает в направлении всех хороших ключей (только ключ 2) и | Ψ_0⟩ ket указывает в направлении всех плохих ключей (ключи 0, 1 и 3).

Мы можем описать состояние кета после применения A как | Ψ⟩ (с «хорошим» компонентом и «плохим» компонентом):

Что это означает. Наше состояние | Ψ⟩ представляет собой линейную комбинацию двух компонентов. Первый компонент указывает в направлении хороших ключей, имеет целевой кубит 1 и коэффициент √ (1/4). Этот коэффициент возводится в квадрат, чтобы получить вероятность чтения 1, P (| 1⟩) = 1/4.

Второй компонент указывает в сторону плохих ключей, имеет целевой кубит 0 и коэффициент √ (3/4). Возведение этого коэффициента в квадрат дает вероятность чтения 0, P (| 0⟩) ​​= 3/4.

Что это означает. Аналогичным образом можно подойти к общей проблеме черного ящика. Независимо от того, насколько сложна система, ее можно упростить до «хорошего» и «плохого» компонентов с вероятностью успеха, определяемой a. На практике мы не знаем значений «хороших» или «плохих» векторов, но они существуют и могут быть использованы.

Работа с квадратными корнями может быть немного обременительной, поэтому вместо этого мы можем заменить их углом θ, таким образом, что sin² (θ) = a. Это позволяет нам легко конвертировать между a и θ и переписывать уравнение 4 как:

Это можно визуализировать с помощью единичного круга с хорошими и плохими компонентами в качестве осей x и y:

Вероятности чтения 1 или 0 в объективном кубите - это квадраты этих значений:

Вопрос и квантовое преимущество

Сама по себе квантовая схема A не дает никаких преимуществ перед классическим подходом. Квантовое преимущество обеспечивается квантовым оператором Q, где:

Точная работа Q не имеет решающего значения для этого обсуждения, но желающие могут ознакомиться с этой статьей. Когда мы применяем этот оператор m раз, мы получаем следующее:

С вероятностями успеха:

Что это означает: каждый раз, когда мы применяем оператор Q, мы вращаемся вокруг хорошей / плохой единичной окружности, изменяя угол на 2θ.

Если мы применим Q один раз, нам гарантирован успех, так как вектор имеет только хороший компонент. Часто не бывает значения m, которое идеально лежит на «хорошей» оси, но выбор значения, близкого к хорошей оси, обеспечивает высокую вероятность считывания успешного ввода для проблемы черного ящика.

Усиление амплитуды асимптотически лучше, чем классический подход к проблеме черного ящика:

  • Классический подход предполагает выборку с вероятностью p. Повышение вероятности успеха примерно на постоянное значение на каждой итерации и требование в среднем 1 / p (1 / a) повторений.
  • Усиление амплитуды позволяет нам работать с θ, которое связано с √ a уравнением 6. Управление θ позволяет нам увеличить вероятность успеха амплитуду (√ a ) примерно на константу с каждой итерацией, требуя 1 / √ a повторений для успеха с высокой вероятностью.

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

Резюме

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

Если мы проведем квантовое измерение, мы получим хороший ответ (т.е. прочитаем 1 в объективном кубите) с вероятностью sin² (θ) и плохой ответ с вероятностью cos² (θ). Есть квантовый оператор Q, который при применении меняет угол. После м применения Q (обозначается Q ^ m) состояние изменяется на угол (2 м +1) θ.

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

Оценка амплитуды (AE)

Таким образом, квантовые компьютеры могут найти ключ, который подходит к замку, быстрее, чем классические компьютеры. Но что, если мы заменим ключи будущими спотовыми ценами (рыночными ценами активов), равномерную вероятность на будущие вероятности спотовых цен и блокировку «да / нет» на прибыль, основанную на этих спотовых ценах. Внезапно наша амплитуда a - это не просто шанс выбрать хороший ключ, она показывает, сколько денег мы ожидаем заработать!

Оценка амплитуды пытается оценить это значение a в уравнении:

В этом разделе N будет означать количество применений A. Как правило, лучший способ определения a - это повторение выборки. Это имеет верхнюю границу ошибки оценки O (N ^ -1 / 2). Теоретическая наилучшая верхняя граница для оценки амплитуды, известная как предел Гейзенберга, составляет O (N ^ -1), что является квадратичным (значительным) улучшением по сравнению с классическим подходом.

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

Резюме

Мы можем закодировать важную информацию в угле θ, например цену опциона. Оценка амплитуды - это процесс оценки θ. Теоретически квантовые вычисления допускают квадратичное ускорение по сравнению с классической оценкой.

Использование амплитудного усиления в оценке

Квантовые компьютеры, использующие усиление амплитуды, производят «квадратично более быстрые» оценки амплитуды, чем классические компьютеры, но как? Это квантовое преимущество проистекает из более глубоких схем Q ^ m, обеспечивающих более точные оценки… за счет введения дополнительных (неправильных) решений.

Давайте проведем эксперимент, используя схемы Q⁰ и Q¹.

  • В схеме Q⁰ P [| 1⟩] = sin² (θ) по уравнению (9)
  • В схеме Q¹ P [| 1⟩] = sin² (3θ) по уравнению (9)

Определение P [| 1⟩] требует многократной выборки целевого кубита. Даже если мы предположим, что квантовый компьютер отказоустойчив (без квантового шума), процесс выборки все равно будет иметь связанную ошибку. Наш эксперимент включает 100 испытаний каждой схемы (запуск схемы и измерение объективного кубита) и предполагает, что такое количество испытаний допускает симметричный доверительный интервал 6 °. Предположим, что истинное значение θ составляет 40 °.

Ошибка выборки связана с измерением, то есть измерения 3θ (Q¹) или θ (Q⁰) будут иметь аналогичные ошибки. Но деление оценки 3θ на 3 уменьшает ошибку, давая схеме Q¹ более «точную» оценку θ, показанную зеленым цветом. Схема Q¹ использует в 3 раза больше приложений A, чем схема Q⁰ (3 против 1 на испытание), и дает доверительный интервал в одну треть размера (4 ° против 12 °). Это определенно похоже на отношения 1 / N, о которых говорил Гейзенберг.

  • Только Q⁰: дает одну оценку с низкой точностью.
  • Только Q¹: дает оценку с большей точностью, но имеет 2 дополнительных решения (20 ° и 80 °), которые мы не можем исключить.
  • Объединение Q⁰ и Q¹ вместе позволяет нам использовать оценку с низкой точностью из схемы Q⁰, чтобы исключить дополнительные решения (20 ° и 80 ° ) схемы Q¹. Тогда мы сможем извлечь выгоду из дополнительной точности Q¹, не беспокоясь о дополнительных решениях.

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

Резюме

Изменение глубины схемы Q ^ m изменяет угол и, следовательно, вероятность чтения 1 или 0 в целевом кубите. Можно провести несколько испытаний, чтобы экспериментально определить эти вероятности и перевести их в оценки θ.

Более глубокие схемы Q ^ m обеспечивают более точные оценки с меньшими доверительными интервалами. Однако они делают это за счет добавления дополнительных (неправильных) решений. Чем глубже схема, тем точнее оценка, но тем больше неверных решений она добавляет.

Оценка амплитуды с оценкой фазы (QAE)

Первый подход к оценке квантовой амплитуды (QAE) заключался в использовании подпрограммы, известной как квантовая оценка фазы. На рисунке 6 видно, что каждый раз, когда применяется Q, вектор вращается по окружности со скоростью вращения, зависящей от θ.

Чтобы оценить θ, мы можем оценить скорость вращения; это делается путем оценки собственных значений (свойство матрицы) Q, которыми являются e ^ (i2θ) и e ^ (- i2θ). Оценка фазы - это квантовая подпрограмма, используемая для вычисления собственных значений квантовых матричных операторов, таких как Q.

QAE использует схему такой формы:

Оценка считывается как целое число из верхних m кубитов, затем отображается на оценку θ, что позволяет получить 2 ^ m возможных дискретных решений. Из этого дискретного набора лучшая оценка имеет наивысшую вероятность быть измеренной. Можно использовать несколько прогонов, чтобы гарантировать, что «лучшее» из этих решений будет найдено с высокой вероятностью. Оценка максимального правдоподобия может быть выполнена по результатам нескольких испытаний, чтобы учесть ответы, не ограниченные этими 2 мкм дискретными решениями.

Этот процесс достигает предела Гейзенберга с верхней границей ошибки оценки O (1 / N).

Почему бы не остановиться здесь?

QAE обеспечивает квадратичное ускорение по сравнению с классическим подходом, что теоретически максимально хорошо. Так почему бы нам не остановиться на этом, не запустить QAE и не найти ключ быстрее, чем когда-либо делал любой компьютер? Что ж, нашего оборудования пока недостаточно.

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

Резюме

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

Были предложены другие подходы, направленные на получение квантового преимущества с использованием более мелких схем. Эти другие подходы могли быть реализованы на квантовых компьютерах намного раньше.

Оценка амплитуды максимального правдоподобия (MLAE)

Оценка амплитуды максимального правдоподобия может быть представлена ​​в виде следующей диаграммы:

MLAE проводит эксперименты с несколькими схемами Q ^ m (первый столбец на рис. 11) и спрашивает: «Какой θ даст мне эти результаты?». Результаты из различных схем представлены в виде функций правдоподобия (насколько вероятно, что θ будет давать зарегистрированные результаты), показанные во втором столбце рисунка 11.

Как обсуждалось выше в разделе «Использование амплитудного усиления в оценке», более глубокие схемы имеют более точные оценки (более узкие пики), но больше решений (несколько пиков). Затем MLAE объединяет эти функции правдоподобия и выполняет оценку максимального правдоподобия (классически), чтобы сделать оценку θ (третий столбец на рисунке 11). При этом используются более мелкие схемы Q ^ m, чтобы отточить решение и помочь отбросить неправильные решения, представленные более точными и глубокими схемами Q ^ m.

Следующий вопрос, который следует задать: какую последовательность значений m следует использовать? Два предложения:

  • Линейный: 0, 1, 2, 3, 4…: нижняя граница ошибки оценки Ω (N ^ -3 / 4). Это обеспечивает асимптотическое преимущество перед классической выборкой (хотя и не так хорошо, как QAE) при использовании только неглубоких схем.
  • Экспонента: 0, 1, 2, 4, 8…: нижняя граница ошибки оценки Ω (N ^ -1). Эта нижняя граница является пределом Гейзенберга, потенциально обеспечивающим квадратичное улучшение классической выборки. Однако он использует значительно более глубокие схемы, чем линейный подход.

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

Резюме

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

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

Итеративная оценка амплитуды (IQAE)

IQAE - это новичок в блоке, использующий усиление амплитуды так же, как и MLAE. Как обсуждалось в разделе «Использование амплитудного усиления в оценке», существует компромисс при использовании более глубоких схем Q ^ m, получение точности за счет введения посторонних решений. MLAE заранее выбирает схемы, чтобы сбалансировать этот компромисс, в то время как IQAE адаптивно выбирает схемы, которые должны обеспечивать наибольшую ценность.

IQAE отслеживает доверительный интервал [θ_l, θ_h], начиная с [0 °, 90 °], и уточняет его в направлении окончательной оценки. Используя тригонометрические тождества и основываясь на приведенном выше уравнении (9), вероятность измерения 1 в цепи Q ^ m можно записать с помощью функции cos:

Понимание значения θ получено в результате экспериментального тестирования P [| 1⟩]. Для определения θ из экспериментальных результатов используется обратная функция cos. Обратный cos имеет бесконечные решения и уникален только в том случае, если мы ограничиваем ответ нижней или верхней полуплоскостью единичной окружности.

Допустим, мы уверены, что θ находится в [θ_l, θ_h] и [(4 m + 2) θ_l, (4 m + 2) θ_h] попадает в любой верхняя или нижняя полуплоскость. Когда мы запускаем эксперимент Q ^ m, мы можем быть уверены, что решение обратной функции cos находится в той полуплоскости. Это отфильтровывает неправильные решения, представленные более глубокими схемами Q ^ m, при этом используя повышенную точность, которую обеспечивают более глубокие схемы.

Начало этого процесса показано на этой диаграмме:

Сначала проводятся эксперименты с использованием схемы Q⁰, которая уточняет доверительный интервал. Затем алгоритм FindNextK используется для поиска следующего m такого, что [(4 m + 2) θ_l, (4 m + 2) θ_h ] попадает в любую из полуплоскостей. Затем с этой схемой Q ^ m проводятся эксперименты для дальнейшего уточнения доверительного интервала. Это продолжается до тех пор, пока не будет достигнут достаточно малый доверительный интервал.

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

Резюме

Проведение экспериментов с более глубокими схемами Q ^ m обеспечивает повышенную точность оценки θ за счет введения нескольких неверных решений. IQAE начинается с неглубокой схемы Q⁰, которая имеет одно решение с низкой точностью и использует его, чтобы сообщить, какое решение принять от более глубокой и высокоточной схемы (например, схемы Q¹).

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

Математически доказано, что IQAE является оптимальным (квадратичное ускорение по сравнению с классическим подходом) с точностью до (относительно небольшого) фактора.

Сравнение

Для сравнения этих алгоритмов используются три основные переменные: оценка точности, максимальная глубина схемы и количество используемых кубитов. Ниже приведено примерное сравнение этих алгоритмов. Это не абсолютное сравнение и несколько субъективное, так что относитесь к нему с недоверием.

Что следует учитывать:

  • Трудно полностью сравнить точность оценки между экспоненциальным MLAE и IQAE, поскольку они доказаны только как нижняя и верхняя границы соответственно.
  • Глубина схемы IQAE не является детерминированной, поэтому ее нельзя предсказать. Некоторые элементарные экспериментальные результаты показывают, что это разумное место для его размещения.
  • MLAE можно распараллелить, что позволяет еще быстрее выполнять его при наличии нескольких квантовых компьютеров. Сомнительно, будут ли достаточные квантовые ресурсы для реализации этого преимущества.

Итак, какой алгоритм AE лучший? QAE конечно. Ну, кроме тех случаев, когда лучше IQAE или MLAE ... Короче говоря, на этот вопрос нет правильного ответа. Если бы это было так, эта статья была бы намного лаконичнее!

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

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

В будущем предпочтительным оружием, вероятно, станет экспоненциальный MLAE или IQAE. Какой из них зависит от сценария, но оба обещают лучшие оценки, чем линейный MLAE. Когда у нас появятся действительно хорошие квантовые компьютеры, мы, вероятно, вернемся к первому подходу, QAE. Это можно представить в виде приблизительной временной шкалы (опять же, не забывайте о крупицах соли):

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

Заключительное резюме

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

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

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