Могут ли квантовые алгоритмы с экспоненциальным ускорением быть переизобретены с использованием программ span?

Известно, что нижняя граница общего противника характеризует сложность квантового запроса благодаря прорывной работе Reichardt et al. Та же самая линия работы также устанавливает связи со структурой программы span для разработки квантовых алгоритмов.

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

Есть ли работа, показывающая нижние границы для этих алгоритмов в общей модели противника? Есть ли какая-нибудь работа по восстановлению алгоритмов Саймона или Шора в рамках программы span?

По-видимому, только квантовые алгоритмы с полиномиальным ускорением, такие как Гровер, были восстановлены с использованием программы на основе span-программ (или графа обучения Белова).

Есть работа Korian et al. показаны нижние оценки для Саймона с использованием полиномиального метода, но, по-видимому, нет известного способа перевода нижних оценок полиномиального метода в общие противные нижние оценки.

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

Вопрос в заголовке: можно ли пересоздать квантовые алгоритмы с экспоненциальным ускорением с помощью span-программ?

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

Есть ли какая-нибудь работа по восстановлению алгоритмов Саймона или Шора в рамках программы span?

Я не слышал о таких результатах. Я не знаю ни одной программы для проблем с Саймоном или других AHSP.

Есть ли способ перевести нижние оценки полиномиального метода в нижние оценки общего противника?

Да, я верю, что есть. Кажется, я не могу найти статью с таким результатом, но могу дать вам ссылку на выступление Джереми Ролана . В аннотации доклада он говорит следующее:

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

Обновление : статья теперь доступна онлайн: явная связь между всеми методами нижней границы для сложности квантовых запросов. Автор Loïck Magnin и Jérémie Roland.