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

19

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

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

Минков
источник

Ответы:

22

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

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

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

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

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

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

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

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

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

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

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

  • Удовлетворение более чем (но меньше чем(1(12-постояннаяD)N) ограничения задачи Макс E3LIN2. Как отметил Хуан Берего Вега в комментариях: теперь существует классический алгоритм для(1(12-122D3/4)N, который был мотивирован квантовым результатом. (Сообщение в блоге об этом результате,статья 1,бумага2)(12-постояннаяD)N
  • Системы рекомендаций ( более подробное объяснение см. В блоге Скотта Ааронсона ). Систему рекомендаций - а-ля Netflix / Amazon / и т. Д. - можно рассматривать как заполнение разреженной матрицы низкого ранга k с очень неполными данными. Известен классический алгоритм, где многочлен от m , n до k . Если матрица задается как оракул, Iordanis Kerenidis Anupam Пракаш нашли р уплотнительное л у ( K ) р о л у л о г ( т п )м×NКмNКpoly(k)polylog(mn)Квантовый алгоритм поиска образцов неизвестных элементов матрицы в 2016 году ( статья ). В 2018 году, пытаясь доказать, что такое масштабирование невозможно достичь с помощью классической машины, Эвин Танг фактически нашел классический алгоритм, обеспечивающий одинаковую производительность при одинаковых условиях (статья доступна здесь и здесь ).
Фредерик Гроссханс
источник
2
Это отличный ответ! Один комментарий: я только что заметил, что запись QAZ о ускорении Max E3LIN2 не актуальна из-за недавнего прогресса в классических алгоритмах [1 ], [2 ], [3 ]; Боюсь, что мы не знаем, существует ли суперполиномиальное ускорение для этой проблемы во время написания.
Хуан Бермехо Вега
1
@JuanBermejoVega: Я отредактировал ответ, чтобы учесть ваш комментарий
Фредерик Гроссханс
1
В твоем последнем пункте, constrant постоянная,
1
Одно обновление: теперь зоопарк также обновлен в этом отношении, ср. «Однако впоследствии был открыт эффективный классический алгоритм, обеспечивающий еще лучший коэффициент аппроксимации (фактически, коэффициент аппроксимации, насыщающий предел, установленный жесткостью аппроксимации) [260]. В настоящее время мощность квантовых приближенных алгоритмов оптимизации относительно классического алгоритмы остаются неясными и являются активной областью исследований. "
Хуан Бермехо Вега
1
Nω