В чем сложность отличить истинные спектры Фурье от поддельных?

26

Машине PH предоставляется оракулу доступ к случайной булевой функции f:{0,1}n{1,1} и двум спектрам Фурье g и h .

Спектры Фурье функции f определяются как F:{0,1}nR :

F(s)=x{0,1}n(1)(sxmod 2)f(x)

Один из или является истинным спектром Фурье для а другой - просто фиктивным спектром Фурье, принадлежащим неизвестной случайной булевой функции.ghf

Нетрудно показать, что машина не может даже приблизить для любых .PHF(s)s

Какова сложность запроса в определении с высокой вероятностью успеха, какой из них является истинным?

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

Мирмойтаба Гариби
источник
5
@Mirmojtaba: Хотя я знаю проблему и мотивацию, было бы неплохо, если бы вы могли отредактировать свой вопрос и определить «спектры Фурье» и объяснить мотивацию для читателей, которые не знакомы с этой проблемой (или только с терминологией, которую вы использовали). Таким образом, вы можете получить больше ответов от людей. Кроме того, обычно предпочтительнее, если вы редактируете вопрос, добавляя дополнительные комментарии, а не публикуете их в ветке комментариев. (Так что читателям нужно только прочитать ваш вопрос, а не комментарии.)
Робин Котари
4
Может быть, я неправильно понял проблему, но кажется, что эта проблема слишком сложна. Если g и h очень близки (скажем, они различаются только на 1 бит), как машина BQP решает, какой из них является правильным спектром Фурье для f? Разве нижняя граница проблемы поиска не должна означать, что это трудно для квантовых компьютеров?
Робин Котари
7
У меня есть более простой вопрос. с учетом произвольной функции, легко ли определить, действительно ли это спектр Фурье булевой функции?
Суреш Венкат
4
кроме того, поскольку он ждал два дня перед кросспостингом, и это тоже после получения ответа здесь, я думаю, что это совершенно нормально сделать. См. Также решение, достигнутое здесь: meta.cstheory.stackexchange.com/questions/673/…
Суреш Венкат
2
Что такое машина PH? На самом деле, это кажется неуместным, если вас интересует только сложность запросов, верно? В этом случае проблема, кажется, сводится к простой задаче линейной алгебры, которая, вероятно, дает экспоненциальную сложность запроса.
Домоторп

Ответы:

10

Извините, я опоздал - это замечательный вопрос! Как уже отмечали другие, именно поэтому я задал вопрос в своей статье BQP vs. PH , и поэтому я потратил 4 или 5 месяцев, работая над этим безуспешно, еще в 2008 году. Одним из способов ответить на этот вопрос было бы доказать гораздо более общее утверждение, которое я назвал «Обобщенной гипотезой Линиала-Нисана», но, к сожалению, эта гипотеза оказалась ложной , по крайней мере, для контуров глубины 3 и выше. (Я все еще думаю, что это, вероятно, верно для схем глубины 2, которые, по крайней мере, привели бы к разделению оракула между BQP и AM.) Для более поздних идей (самых последних, насколько я знаю) к разделению оракула между BQP и PH, посмотрите хорошую статью Феффермана, Шалтиэля, Уманса,

Скотт Ааронсон
источник
1
Приведенное выше утверждение вопроса Гариби идентично или немного отличается? это ваша релятивизированная версия?
vzn
1
Это небольшой вариант, но я считаю, что нетрудно доказать эквивалентность. Во-первых, конечно, если вы можете решить проверку Фурье, то вы также можете решить проблему Гариби (просто запустите алгоритм FC отдельно для g и h). И наоборот, если вы можете решить проблему Гариби, то с учетом экземпляра FC назовите вторую функцию FC "g" или "h" равномерно случайным образом и задайте другую из двух (соответственно h или g) как случайная функция. Если алгоритм Gharibi всегда выбирает исходную функцию из экземпляра FC, это свидетельствует о том, что экземпляр был связан, а не случайный.
Скотт Ааронсон
1
Более известно, когда f в P?
Гил Калай
Гил: Не совсем! Затем в BQP вы получите проблему с нерелятивизированными обещаниями, о которой мы не знаем, что это будет в PH. Конечно, вы могли бы смоделировать «случайный» случай проблемы оракула, заменив f и g псевдослучайными функциями (вычисленные во времени, которые являются большим полиномом, чем машина PH). Сложная часть состоит в том, как вы моделируете «взаимосвязанный» случай проблемы оракула (где f близко к преобразованию Фурье от g)? Т.е. как вы предоставляете небольшие схемы для таких f и g, которые не "отдают всю игру"? (Подобная проблема возникает с проблемой Саймона.)
Скотт Ааронсон
1

Скотт Ааронсон может быть лучшим человеком в мире, чтобы ответить на этот вопрос, возможно, у него будет лучший ответ после того, как этот вопрос будет опубликован. он предложил исходную проблему, о которой этот опубликованный вопрос, кажется, очень слабый вариант, так называемая проблема проверки Фурье (более подробно об этом в комментариях). проблема тесно связана / почти эквивалентна разделению двух важных классов сложности PH и BQP, что является ключевой открытой проблемой теории сложности КМ, и, по-видимому, она очень сложна. Похоже, что до сих пор кто-то, кроме Ааронсона, и, возможно, даже не он, провел много прямых / дальнейших исследований этой проблемы по этой проблеме (по-видимому, ей чуть больше двух лет).

однако здесь есть по крайней мере одна статья, написанная кем-то кроме Ааронсона, которая фокусируется / строит на гипотезе / проблеме с некоторыми новыми результатами.

Экспоненциальные ускорения являются общими для Фернандо GSL Brandão и Михаила Городецкого

В нашей работе [4] мы обобщаем задачу проверки Фурье [1] и показываем, что преобразование Фурье, как в определении задачи, так и в ее квантовом алгоритме, может быть заменено большим классом квантовых цепей. Они включают в себя как преобразование Фурье над любой (возможно, неабелевой) конечной группой, так и почти любую достаточно длинную квантовую цепь из естественного распределения на множестве квантовых схем. Мы получим экспоненциальное разделение квантовых и отобранных классических сложностей запросов для всех таких схем.

ВЗН
источник
Приложение: Ааронсон сформулировал проблему проверки Фурье конкретно как возможный / правдоподобный путь к решению в [1] из . BQPPH
2013 года