Сложность выборки (приближенно) преобразования Фурье булевой функции

Одна вещь, которую могут сделать квантовые компьютеры (возможно, даже с использованием только квантовых цепей с логарифмической глубиной BPP +), - это аппроксимировать выборку преобразования Фурье булевой -значной функции в P.$\pm 1$

Здесь и ниже, когда я говорю о выборке преобразования Фурье, я имею в виду выбор x в соответствии с . (Нормализуется при необходимости и приблизительно).$|\hat f(x)|^2$

Можем ли мы описать класс сложности, который мы можем назвать P-FOURIER SAMPLING, для приближенных выборочных булевых функций P? Есть ли проблемы, которые полны для этого класса?

Учитывая класс X булевых функций, что можно сказать о вычислительной сложности, которую мы можем назвать SAMPLING-X для аппроксимации выборки преобразования Фурье функций в X. (Я полагаю, что если X является BQP, то X-SAMPLING все еще во власти квантовых компьютеров.)

Каковы примеры X, где SAMPLING-X находится в P? Есть ли интересные примеры, где SAMPLING-X является NP-hard?

Есть несколько вариантов этой проблемы, которые также могут быть интересными. Со стороны Фурье мы можем говорить не о приближенной выборке, а о проблеме решения, которая возможна (вероятностно) с помощью приближенной выборки. В первую очередь, мы можем начать с класса X распределений вероятностей и спросить, какова связь между способностью приблизительно выбирать распределение D в X и приблизительно выбирать (нормализованное) преобразование Фурье.

Короче, что известно по этому вопросу.

Обновление: Мартин Шварц указал, что если все коэффициенты Фурье сосредоточены только на полиномиальном числе записей, то в BPP возможно приблизить эти большие коэффициенты (и, следовательно, также к примерной выборке). Это восходит к Голдрайху-Левину, и Кушилевиц-Мансур. Существуют ли интересные классы функций, где существует вероятностный полиномиальный алгоритм для приближенной выборки со стороны Фурье, где коэффициенты Фурье распределены по полиномиально большому числу коэффициентов?

Добавлено позже: позвольте мне упомянуть несколько конкретных проблем.

1) Насколько сложно приблизительно выбрать фурье-преобразование булевых функций в P.

a) Один вопрос, который Скотт Ааронсон упомянул в комментарии ниже, должен показать, что это не относится к BPP. Или что-то более слабое в том, что, если эта задача находится в BPP, происходит некоторый крах. (Скот Предполагает, что это так.)

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

2) Какие классы булевых функций таковы, что приближенная выборка их преобразования Фурлера находится в P. Мы знаем, что это тот случай, когда коэффициенты Фурье концентрируются на многочленных коэффициентах, но это кажется очень ограниченным.

3) Есть ли некоторый класс сложности X высоко в PH, что X-машина может приблизительно сэмплировать преобразование Фурье каждой функции, которую X-машина может вычислить.

4) Меня особенно интересовала проблема выборки преобразования Фурье события скрещивания для перколяции на n-n-гексагональной сетке.

Kushilevitz-Мансур алгоритм обучения теории устанавливает, что всякий раз , когда приблизительно разреженный, т.е. есть только -many больших коэффициенты Фурье по абсолютной величине , тогда мы можем найти их местоположения и приблизить их комплексные значения в . Конечно, вы также можете эффективно выбрать из этого списка. Точнее говоря , Кушилевиц-Мансур говорил только о преобразованиях Фурье над , но обобщение на ФТ над общими конечными абелевыми группами (см., Например , тезис Акавиа ) известно.О(ролу(п))Ω(1/ролу(п))ВPPZ$\hat{f}(x)$$O(poly(n))$$\Omega(1/poly(n))$$\sf{BPP}$$\mathbb{Z}_2$

В качестве приложения этого к квантовым вычислениям можно показать, что состояние выхода квантовых цепей, структурированных в блоках вентилей Адамара-Тоффили-Адамара, может быть эффективно аппроксимировано, учитывая обещание, что состояние вывода, записанное в вычислительной основе, является приблизительно разреженным (см. мой постер QIP'2010 здесь , а препринт здесь ). Если допущение разреженности будет отброшено, мы могли бы смоделировать алгоритм Саймона (или Шора), который имеет именно такую ​​структуру, что противоречит нижнему пределу запроса для задачи Саймона.$\Omega(2^{n/2})$