Проблемы в BQP, но предположительно находятся за пределами P

В Википедии перечислены четыре проблемы, которые есть в но предположительно находятся вне : целочисленная факторизация; Дискретный логарифм; Моделирование квантовых систем; Вычисление полинома Джонса на определенных корнях единства.$BQP$$P$

Есть ли еще такие проблемы?

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

Алгебраические и теоретико-числовые задачи

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

• факторизация
• Дискретный логарифм
• Уравнение Пелла . Факторинг сводится к уравнению Пелла.
• Главный идеал Идеальная проблема. Уравнение Пелла сводится к этой проблеме, которая, по крайней мере, так же сложна, как и факторинг.
• Проблема группы объектов
• Задача группы классов
• Gauß Sums оценка
• Матричные элементы представлений групп
• Групповой заказ и членство
• Абелева задача о скрытой подгруппе
• Некоторые (но не все) неабелевы проблемы скрытой подгруппы
• Некоторые (но не все) проблемы сформулированы как частные случаи проблемы скрытого сдвига
• Некоторые (но не все) проблемы скрытых нелинейных структур
• Изучение некоторых графиков (сварные деревья)
• Групповой изоморфизм, для абелевых и некоторых неабелевых групп
• Найдите некоторые свойства конечных колец и идеалов

Аппроксимация и моделирование

• Квантовое моделирование. Очевидно, -полный$BQP$
• Вычисление некоторых узловых инвариантов, включая полином HOMFLY, из которых полином Джонс является частным случаем. Некоторые из них -комплектные$BQP$
• Вычисление некоторых трехмерных инвариантов. Некоторые из них являются -комплектными.$BQP$
• Оценка термодинамической функции разбиения некоторых классических систем
• Вычисление дзета-функций над конечными полями
• Проблема перезаписи строки -полный$\mathit{PromiseBQP}$
• аппроксимирующие матричные элементы степеней экспоненциально больших разреженных матриц.

Алгоритм я не совсем понимаю.

Это в основном алгоритмы , где QAZ утверждает суперполиномиальное рост, но я не понимаю , почему исходная задача должна быть из . Тем не менее, я поставлю много своих денег на то, чтобы QAZ был прав, а я ошибаюсь в этом.$P$

• Сравнение шаблонов для достаточно больших ( ) шаблонов$>\log(n)$
• Некоторые линейные задачи системы, в , но имеющие р уплотнительное л у л о г квантового алгоритма , если линейная система задана в качестве оракула.$P$$\mathrm{polylog}$
• Вычисление электрического сопротивления графа, имеет квантовый алгоритм , если электрическая цепь дается как оракул$\mathrm{polylog}$
• Проблема с счетчиками веса. Нечто связанное с функциями кода и разделов, но я не понимаю, о чем это.

задачи 1-го оказались в B Q P, а затем в$P$$BQP$$P$

Вот некоторые проблемы, где эффективный квантовый алгоритм был опубликован раньше классического. Другими словами, когда-то предполагалось, что они находятся в но не в P , но теперь эта гипотеза недействительна.$BQP$$P$

• Удовлетворение более чем (но меньше чем($(\tfrac12-\tfrac{\text{constant}}{D})N$) ограничения задачи Макс E3LIN2. Как отметил Хуан Берего Вега в комментариях: теперь существует классический алгоритм для($\left(\tfrac12-\tfrac{1}{22D^{3/4}}\right)N$, который был мотивирован квантовым результатом. (Сообщение в блоге об этом результате,статья 1,бумага2)$(\tfrac12-\tfrac{\text{constant}}{\sqrt{D}})N$
• Системы рекомендаций ( более подробное объяснение см. В блоге Скотта Ааронсона ). Систему рекомендаций - а-ля Netflix / Amazon / и т. Д. - можно рассматривать как заполнение разреженной матрицы низкого ранга k с очень неполными данными. Известен классический алгоритм, где многочлен от m , n до k . Если матрица задается как оракул, Iordanis Kerenidis Anupam Пракаш нашли р уплотнительное л у ( K ) р о л у л о г ( т п $m×n$$k$$m$$n$$k$$\mathrm{poly}(k)\mathrm{polylog}(mn)$Квантовый алгоритм поиска образцов неизвестных элементов матрицы в 2016 году ( статья ). В 2018 году, пытаясь доказать, что такое масштабирование невозможно достичь с помощью классической машины, Эвин Танг фактически нашел классический алгоритм, обеспечивающий одинаковую производительность при одинаковых условиях (статья доступна здесь и здесь ).